Wednesday, February 1, 2017

January Contests

ピカピカの本のキャラクターNo, I didn't forget this blog. I was just too lazy to write new posts. Anyway, after the last post I was not very active - I participated only in one SRM and Facebook Hacker Cup's rounds (and SnarkNews Series, though I gave up after having trouble with understanding the Russian statements).

In SRM 706, the first two tasks were relatively easy. My idea for the Hard was as follows. In this task you want to find a family of subsets of {1, ..., N}, where no subset contains two consecutive numbers and for each non-consecutive pair (p, q), at least one subset contains both. First add a subset that contains all even numbers, and add another subset that contains all odd numbers. Now we only need to care about pairs with different parities. In my construction, for example when N = 15, add three sets: {2, 4, 6, 9, 11, 13, 15}, {1, 3, 5, 7, 10, 12, 14}, and {1, 3, 5, 8, 11, 13, 15}. Then do the same thing recursively for {1, ..., 7} and {9, ..., 15} (like divide-and-conquer). This way we only need about 3 * lg N sets but it turned out that the numbers can be as large as 10^25. Maybe we can do it with 2 * lg N sets? I still don't know the answer, let's add it to "Upsolving" section.

My rating slightly increased after the contest and it became 3615. It seems this is the 4th in TopCoder's history. However it's far away from the three legends - Petr (3924), ACRush (3902), and tourist (3836).

Do you understand what the picture above means? Facebook. There were four elimination rounds in this year's FHC. The first three rounds were relatively easy. The second task in Round 1 was notable - at first it looked like a very tedious task where you have to find all subsets of points that can be enclosed by a circle, but there's a significantly simpler solution: you only need to consider the union of two squares.

Last Sunday I participated in Round 3, the last elimination round. I knew problem A so I solved it quickly. After that I read everything and decided to solve B first - it's tricky and requires careful coding, but I'm good at counting tasks and it looked like the easiest one. After that the choice was between C and E. D looked overwhelming at that time. I chose C mainly because it looked very easy to do stress-testing and believed that correct A+B+C can qualify (which turned out to be wrong and I was quite close to the cutoff due to too big penalty). Maybe careful A+B+E was a better strategy. (However, I have to admit that I made a small mistake and my E failed during upsolving).

My solution for C was as follows. First for each non-center vertex i, compute two values x[i] and y[i]. x[i] is the position along the cycle and y[i] is the shortest path from the center. Now the problem asks to compute the sum of min{x[j] - x[i], X - (x[j] - x[i]), y[i] + y[j]}, where X is the total cycle length. In my solution I assumed that the arrays x and y are arbitrary. This leads to a solution with BIT. But x and y are not arbitrary arrays and these satisfy triangle inequalities of a certain graph. If we use this fact, we can prove that for a fixed i we can split the cycle into three consecutive parts and in each part we can determine which of x[j] - x[i], X - (x[j] - x[i]), y[i] + y[j] is the smallest. This leads to a simpler linear solution.

During the contest, my first idea for D was as follows. Consider two numbers x and y, and two masks (the set of non-broken positions) mask1 and mask2. We can't distinguish two states (x, mask1) and (y, mask2) after t seconds if ((x + t) & mask1) and ((y + t) & mask2) are the same. For each bit there are several cases: it is broken in both states, broken in one state and off in another, ... and so on. And looked completely unapproachable. Indeed I missed a very simple thing: when the position i is 0 in the input, we can always assume that the display is broken at this position. This observation greatly simplifies the problem and now we know mask1 and mask2 - now we can concentrate on x and y. After that it's still tricky, but quite solvable task.

How should we solve it during the contest? One possible approach is to consider various cases, but I don't prefer it with such weak examples. Digit DP is also possible but it's fairly complicated. Here's a very simple solution: we can prove that in the optimal solution x and y differ in only two bits. Fix two positions p and q - at position p, x is 0 and y is 1, and at position q, vice versa. And in other positions x and y are the same. In this case, we can prove that there's some r such that the bits at positions [r, N) doesn't matter at all, and we want to minimize the numbers in the least-significant r bits. If we fix these three numbers (p, q, r), we can solve the task without considering various cases. This will lead to a very simple O(N^4) solution. Source code in ideone.

Anyway, I managed to qualify to the Finals. If you also qualified, see you in Seattle!



7 comments:

  1. I NEED MY EX LOVER BACK Contact: Unityspelltemple@gmail.com ,Is certainly the best spell caster online, and his result is 100% guarantee. My Names is Julie Collins from United states. After 12years of marriage, me and my husband has been into one quarrel or the other until he finally left me and moved to California to be with another woman. I felt my life was over and my kids thought they would never see their father again. i tried to be strong just for the kids but i could not control the pains that torments my heart, my heart was filled with sorrows and pains because i was really in love with my husband. Every day and night i think of him and always wish he would come back to me, I was really upset and i needed help, so i searched for help online and I came across a website that suggested that Dr Unity can help get ex back fast. So, I felt I should give him a try. I contacted him and he told me what to do and i did it then he did a (Love spell) for me. 28 hours later, my husband really called me and told me that he miss me and the kids so much, So Amazing!! So that was how he came back that same day,with lots of love and joy,and he apologized for his mistake,and for the pain he caused me and the kids. Then from that day,our Marriage was now stronger than how it were before, All thanks to Dr Unity. he is so powerful and i decided to share my story on the internet that Dr.Unity real and powerful spell caster who i will always pray to live long to help his children in the time of trouble, if you are here and you need your Ex back or your husband moved to another woman, do not cry anymore, contact this powerful spell caster now. Here’s his contact: Email him at: Unityspelltemple@gmail.com , you can also call him or add him on Whats-app: +2348071622464 , you can also visit his website: https://urgentspell.blogspot.com .

    ReplyDelete
  2. How to get your ex back and save your relationship or marriage! contact: Unityspelltemple@gmail.com , Is certainly the best spell caster online, and his result is 100% guarantee. I'm so excited my boyfriend is back after he left me for another girl. After 4 years of relationship with my boyfriend, he broke up me and brought in another Girl, i did all i could to get him back but all proved abortive, I was really upset and i needed help, so i searched for help online and I came across a website that suggested that Dr Unity can help get ex back fast. So, I felt I should give him a try. I contacted him and he told me what to do and i did it then he did a (Love spell) for me. 28 hours later, my boyfriend really called me and told me that he miss me so much, So Amazing!! So that was how he came back that same day,with lots of love and joy,and he apologized for his mistake, and for the pain he caused me . Then from that day, Our relationship was now stronger than how it were before, All thanks to Dr Unity. he is so powerful and i decided to share my story on the internet that Dr.Unity real and powerful spell caster who i will always pray to live long to help his children in the time of trouble, if you are here and you need your Ex back or your husband moved to another woman, do not cry anymore, contact this powerful spell caster now. Here’s his contact: Email him at: Unityspelltemple@gmail.com , you can also call him or add him on Whats-app: +2348071622464 , you can also visit his website: https://urgentspell.blogspot.com.

    ReplyDelete
  3. Excited, My Girlfriend Is Back Contact Happylovespell2@gmail.com.. My Ex and I have been getting into little arguments which then later escalated. A lot of which are my fault but I never thought I would lose her because we are in love. She told me yesterday that she loves me but she done. That the fights keep hurting her too much. I can’t believe I hurt her like that and would love nothing more than another chance to prove to her and myself that I will cut out my insecurities that I’ve brought into this relationship. I did all i could to end this fight between us, didn’t work so i had to seek the help of a spell caster who i met online and promised to help me bring her back into my life in 2 days time. i wasn’t really sure about this, but i was really desperate that i had to do all that the spell caster asked me. it was on the second day at 5pm on Friday, i had a knock on the door and to my greatest surprise, it was my girlfriend, the first thing she said, was that she has forgiven me and she will never leave me again, Am so full of joy for what this spell caster and to this product page and graphic love spell coz it really help and work for me, i also want the world to benefit from this. if you need his help you can reach him for any thing on relationship problem, getting your ex back save and protect your marriage life with your soul mate contact him now for he is so powerful and real. Urgently email him now
    @.... happylovespell2@gmail.com
    You can also view on his Blogs site... https://happylovespell2.blogspot.com.ng/
    Also for quick option on how to help with a love spell add him up on Whats-app +2348133873774

    ReplyDelete
  4. URGENT EFFECTIVE LOVE SPELL TO GET YOUR EX BOYFRIEND/GIRLFRIEND BACK FAST! Contact: Unityspelltemple@gmail.com is certainly the best spell caster online and his result is 100% guarantee.. My husband breakup with me and left me to be with another woman, and i wanted him back. I was so frustrated and i could not know what next to do again, I love my husband so much but he was cheating on me with another woman and this makes him break up with me so that he can be able to get married to the other lady and this lady i think use witchcraft on my husband to make him hate me and my kids and this was so critical and uncalled-for,I cry all day and night for God to send me a helper to get back my husband!! I was really upset and i needed help, so i searched for help online and I came across a website that suggested that Dr Unity can help get ex back fast. So, I felt I should give him a try. I contacted him and he told me what to do and i did it then he did a love-spell for me. 28 hours later, my husband really called me and told me that he miss me so much, Oh My God! i was so happy, and today i am happy with my man again and we are joyfully living together as one big family and i thank the powerful spell caster Dr.Unity, he is so powerful and i decided to share my story on the internet that Dr.Unity is best spell caster online who i will always pray to live long to help his children in the time of trouble, if you are here and your lover is turning you down, or your husband moved to another woman, do not cry anymore, contact this powerful spell caster Dr.Unity on his email: Unityspelltemple@gmail.com ,you can also call him or add him on Whats-app: +2348071622464 ,you can also visit his website: https://urgentspell.blogspot.com ,
    Olivia Stephen
    from North Carolina .

    ReplyDelete
  5. How to get your ex lover back & save your marriage fast "I suggest you read this."?
    I got a divorce from my husband when I was six months pregnant with my second child. We had been arguing and quarreling nonstop since the day our first child was conceived, no love nor trust from him anymore so he divorced me. And all these whiles, I have been trying all different means to get him back, I also tried some different spell casters here in the United States, but none of them could bring Richard back to me. It was only Dr. Unity who guaranteed me an urgent 28 hours spell casting, and he assure me that my husband will be with me again. I am writing to offer my thanks and deep gratitude to you for keeping your promises, and for using your gifted and great powers to bring him back home. I was thrilled to know that you are specialized in reuniting Lovers. Thank you Sir, for helping me through the worst times of my life, for being such a great spell caster, and for giving me a love spell that has brought me so much joy in my marriage. My husband is back and promise never to leave me again. If you doubt his ability, trust me. You should take a chance. It pays off in ways you could never even imagine. If you are thier right now and you need a powerful and urgent love spell to bring back your ex kindly contact Dr. Unity right now he is the only answer to restore your broken relationship or marriage. Here’s his contact: Email him at: Unityspelltemple@gmail.com ,Call/WhatsApp: : +2348071622464 , his website: https://urgentspell.blogspot.com .

    ReplyDelete
  6. I want to use this opportunity I have to say a big thanks to Dr Great for getting back my ex husband. I'm Linda Gibson from USA, after 7 years of marriage my husband left me for another woman I did whatever I could to get him back but all I did was in vain I was sad, but I didn't lose hope of getting him back because I had faith in God. So I search online on how to get my husband back, and I came across a post of Dr Great of how he helped a lady to get back her ex I felt I should give him a try, I contacted him and told him the pain I was going through, he told me what to do and I did it then he casted a love spell for me 48 hours later my husband called me and told me he is sorry for what he did and that he misses me very much later that day he came back home and he hugged me and that how our relationship became stronger. For the marvelous things Dr Great has done for me it will be unfair for me no to let the whole world know that such a powerful spell caster do live. If you want to get back your ex fast email Dr Great at infinitylovespell@gmail.com

    ReplyDelete
  7. Urgent effective love Spell caster to help you bring back ex lover & save you marriage fast Unityspelltemple@gmail.com is certainly the best spell caster online and his result is 100% guarantee!.
    My Name Olivia Stephen form Tx,USA. After 12years of marriage, me and my husband has been into one quarrel or the other until he finally left me and moved to California to be with another woman. I felt my life was over and my kids thought they would never see their father again. i tried to be strong just for the kids but i could not control the pains that torments my heart, my heart was filled with sorrows and pains because i was really in love with my husband. Every day and night i think of him and always wish he would come back to me, I was really upset and i needed help, so i searched for help online and I came across a website that suggested that Dr Unity can help get ex back fast. So, I felt I should give him a try. I contacted him and he told me what to do and i did it then he did a (Urgent effective Love spell) for me. 28 hours later, my husband really called me and told me that he miss me and the kids so much, So Amazing!! So that was how he came back that same day,with lots of love and joy,and he apologized for his mistake,and for the pain he caused me and the kids. Then from that day,our Marriage was now stronger than how it were before, All thanks to Dr Unity. he is so powerful and i decided to share my story on the internet that Dr.Unity real and powerful spell caster who i will always pray to live long to help his children in the time of trouble, if you are here and you need your Ex back or your husband moved to another woman, do not cry anymore, contact this powerful spell caster now. Here’s his contact:Email him at: Unityspelltemple@gmail.com ,or Call/WhatsApp him on:+2348071622464 ,his website:https://urgenteffectivespell.blogspot.com.

    ReplyDelete