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!



13 comments:

  1. 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
  2. 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
  3. 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
  4. I am blessed, is about my marriage, when Dr. SHARAJA brought back my husband, who separated from me for 6 months. Am SANDRA by name. Although my mouth would be all over my body, is not enough to thank Dr. SHARAJA for his help in my life. My husband has divorced with me for six months and have been in pain and agony without him. So, I'm looking for help everywhere, until i came across a blog about Dr. SHARAJA, I contacted him online. I explained my situation to him and he promised that my husband comes back to me 24-48 hours, if only my heart still beats for him. I believed him, and he promise to prepare a spell for me and my husband.my husand called me exactly when Dr. SHARAJA said. He apologies and said that he needs me back and now we live happily again over the last 9 months...please everyone reading my article out there who needs help should contact Dr Sharaja sid by E-mail. sharajasid@gmail.com for more information
    If you are there, go through this
    The problems listed below he is also perfect in these Areas...
    (1) Do you want your ex back?
    (2) Do you always have bad dreams?
    (3) Do you want to promote your office?
    (4) Do you want that the women / men running after you?
    (5) Do you want a child?
    (6) Do you want to be rich?
    (7) Do you want to tie your husband / wife to be?
    yours forever?
    (8) Need financial support?
    (9) Have you been scammed and you want to
    return the lost money?

    If you need information or want to love or
    money spells you can get that problem solved
    today Spell Of Temple Solution ...
    How to be happier the marriage unexpectedly change your spouse

    ReplyDelete
  5. I am blessed, is about my marriage, when Dr. SHARAJA brought back my husband, who separated from me for 6 months. Am SANDRA by name. Although my mouth would be all over my body, is not enough to thank Dr. SHARAJA for his help in my life. My husband has divorced with me for six months and have been in pain and agony without him. So, I'm looking for help everywhere, until i came across a blog about Dr. SHARAJA, I contacted him online. I explained my situation to him and he promised that my husband comes back to me 24-48 hours, if only my heart still beats for him. I believed him, and he promise to prepare a spell for me and my husband.my husand called me exactly when Dr. SHARAJA said. He apologies and said that he needs me back and now we live happily again over the last 9 months...please everyone reading my article out there who needs help should contact Dr Sharaja sid by E-mail. sharajasid@outlook.com for more information
    If you are there, go through this
    The problems listed below he is also perfect in these Areas...
    (1) Do you want your ex back?
    (2) Do you always have bad dreams?
    (3) Do you want to promote your office?
    (4) Do you want that the women / men running after you?
    (5) Do you want a child?
    (6) Do you want to be rich?
    (7) Do you want to tie your husband / wife to be?
    yours forever?
    (8) Need financial support?
    (9) Have you been scammed and you want to
    return the lost money?

    If you need information or want to love or
    money spells you can get that problem solved
    today Spell Of Temple Solution ...
    How to be happier the marriage unexpectedly change your spouse

    ReplyDelete
  6. Get Your Wife Back, Perfect Urgent Love Spell. Am Karen Renee from FL Usa All Thanks To Dr Osasu Who Brought Back The Love Of My Life. my girlfriend cheated on me and asked for a breakup. I don't believe at first i try to get back with her but all she told me was she’s with someone else. that she is no longer interested in marrying me at that point i was heart broken because i love my girlfriend so much that i could not let go off her all of a sudden she left me, i really love her and never can imagine my life without her. not until i came across a powerful real spell caster Dr Osasu who promise me 24hours urgent love spell to get back with my girlfriend, good twenty-four {24} hours. hmm-mm, it was a good night time at 11:pm within the days that Dr Osasu told me that my girlfriend will be back, at first i heard the bell rings getting close to my door i heard someone saying honey!!!, it sound familiar i opened the door and i saw my girlfriend standing and weeping in front of me. i was not surprised because its all i have been praying for her to come back home. Guess what 2 weeks after she noticed her system and her body temperature was changed and i took her to clinic for check up and the doctor told me that there is life in her which means she was pregnant i really wants to use this opportunity to thanks Dr Osasu so much and the love page that directed me to Dr Osasu if you have any problem getting your ex back, or predicament that is worse or exactly like this you have been into, contact Dr Osasu on drosasu25@gmail.com You can add him up on Whats-app/ Or call +2347064365391

    ReplyDelete
  7. best spell caster 2019 is Dr Ehis Love Spell And Lotto Spell the great wizard from African I want to use this medium to thank him for bringing my my ex lover back to me he only told me to provide the items needed for the spell and which I did and he told me that after he got the items in 24 hours I will start seeing the result and truly is a man of his words contact him today and get your problem solve
    drehis60@gmail. com
    Whatasapp +2347057467980

    ReplyDelete
  8. am writing this because I want to testify how great you are Dr Sam for what you have done for me. Everyone needs to know! I am a very satisfied and happy customer. I can’t tell how long it’s been since I’ve bought spells online, but none of them had the same results than yours. Fuller definitely moved in with me 3 weeks ago. It was just a few days after you cast your spell. I know I should have messaged you before, but I was a bit scared that he could find out about the spell you did so I removed all your emails. Anyway, I can tell all your future customers who are reading this that they are doing the right choice to go with you for a spell. It was always great communicate with you and all the services you offer are just excellent. Thank you for everything you did for me!” Fully CONTACT Dr Sam on +2349060421250

    ReplyDelete
  9. HOW I WON £4,369,877.00 WITH DR ALLI LOTTERY MAGIC SPELL

    I am  SARA KIM From the UK...I had to write back and say what an amazing experience I had with Dr Alli's powerful lottery spell. My Heart is fill with joy and happiness after Dr Alli cast the Lottery spell for me, And i won £4,369,877.00 His spell change my life into riches, I'm now out of debts and experiencing the most amazing good luck with lottery after i won a huge amount of money. My life has really changed for good. I won (Four million three hundred and sixty nine thousand Eight hundred and seventy seven thousand pounds)Your Lottery spell is so real and pure. Thank you very much Dr. Alli for the lottery spell that changed my life”I am totally grateful for the lottery spell Dr Alli did for me. You can email him for your own lottery number,because these is the only secret to winning the lottery.
    Email him:  Allispellhelp1@gmail.com Whats App him: +2348100772528

    ReplyDelete
  10. GREAT MOTHER IS REAL. PLEASE BELIEVE HER. I am Lucy Jones and i want to share my testimony on how real Great Mother is and how she helped me to get  my ex husband back to me. when my husband left me, i thought it was all over until i saw testimonies of Great mother how she has helped so many people. I never believed but i gave it a try since i had no option. I contacted her and i told her everything. She told me what to do and to my Greatest surprise, my man came back to me in 3 days time just as Great Mother said. Thank you Great mother. Thank you very much. If you need help please contact the Great Mother now on her Email: Greatmotherofsolutiontemple1@gmail.com  and you can also reach her on her whatsapp no: +17025514367  you can also check her out on her website: Greatmotherofpowers.blogspot.com

    ReplyDelete
  11. My husband and I have been married for about 7 yrs now. We were happily married with two kids, a boy and a girl. 3 months ago, I started to notice some strange behavior from him and a few weeks later I found out that my husband is seeing someone. He started coming home late from work, he hardly cared about me or the kids anymore, Sometimes he goes out and doesn't even come back home for about 2-3 days. I did all I could to rectify this problem but all to no avail. I became very worried and needed help. As I was browsing through the Internet one day, I came across a website that suggested that Dr OKU can help solve marital problems, restore broken relationships and so on. So, I felt I should give him a try. I contacted him and he did a spell for me. Two days later, my husband came to me and apologized for the wrongs he did and promised never to do it again. Ever since then, everything has returned back to normal. My family and I are living together happily again.. All thanks to Dr OKU. If you need a spell caster that can cast a spell that truly works, I suggest you contact him. He will not disappoint you. This is his Email: (okutemple@gmail.com) or WhatsApp him (+2348163425519)

    ReplyDelete
  12. There aren’t enough words to describe or explain my wonderful experience with CYBERCREDITGURU a US based Russian h a c k e r s. In 2018, I had 205 BTC in my blockchain wallet but out of my carelessness I misplaced my password and recovery phrase. I really don’t know how to go about it until early this year, I came across a 5star review about them in a forum online by one Mrs. Kimberly and I reached out to them via text: +1 (650) 439 0624 and CYBERCREDITGURU (AT) GMAIL DOT COM. They responded immediately and helped recovered my lost BTC wallet within 4 days. Thanks to Team CyberGuru. I also had an extremely poor credit report of 403 with derogatory; late payment, repossession, collections and foreclosure. They also cleared all negative items from my credit report and upgraded my FICO score to 810 across all three major bureaus. Now with no doubts I can say 2022 is a great year for me as I am a proud owner of a new house and a car. All thanks to CYBERCREDITGURU once again. They are my messiah! I confidently recommend them to you.

    ReplyDelete
  13. When my boyfriend broke up with me 4 weeks ago..

    I did everything to get my boyfriend back but nothing worked.

    I contacted a relationship doctor i saw online.

    I told the relationship doctor everything,

    He promised to fix my relationship problem.

    I am the happiest lady on earth right now,

    Never too late to fix your broken heart.

    You can still get your lover back...

    Fix broken relationship/marriage...

    My relationship was restored as promised,

    My Ex-boyfriend came back,

    He promised never to leave me again

    Everything happened just in 3 days..

    Thanks_________________________________ Robinsonbuckler11 (@) gmail com

    ❤️❤️❤️❤️❤️❤️🌹🌹🌹🌹🌹

    ReplyDelete