Wednesday, May 3, 2017

Summary of Open Cup 2016-2017

Sorry for the long break. I returned here. This post is just about analysis of my personal performance.

Last Sunday, the last Open Cup round of this season has finished. Except for GP of Japan (I chose some problems from old AtCoder and translated them), there were 17 rounds and 191 problems in total. That's a lot of problems, given that few problems are very easy. I solved 143 of them. That means I couldn't solve 48 tasks - let's take a close look at those 48 tasks.

First, I define "objective difficulty". When N teams participate and x teams solve a certain task, the AC ratio is x/N. However, it seems when small number of teams participate, the average level is higher. Thus, I defined the difficulty as x * sqrt(100 / N). Usually the number of teams is around 100, so this value should be close to the number of ACs.

My results are:

Difficulty Problems
[50, inf) 95 / 95
[40, 50) 8 / 10
[30, 40) 17 / 21
[20, 30) 8 / 13
[10, 20) 11 / 20
[5, 10) 4 / 9
[0, 5) 0 / 23

Not surprisingly, it shows a very strong correlation.

And here's the complete list of those 48 problems. From left to right, it shows contest ID, contest name, task ID, task name, number of ACs, number of participants, difficulty, topic, and "the room of improvement". Topics may be inaccurate because I don't know the solutions of some of the tasks. Three or more stars mean that I feel "I should have solved it during the contest!" (five-star tasks are the most serious ones).

14 Tatarstan I Minimum Prefix 42 76 48.18 strings, flow ☆☆☆☆☆
16 America G Apple Market 41 95 42.07 flow ☆☆☆☆
12 Wroclaw C Game 34 79 38.25 graph theory ☆☆
17 Moscow Workshop B Completely Multiplicative Function 34 89 36.04 number theory ☆☆☆☆☆
17 Moscow Workshop C Even and Odd 33 89 34.98 graph theory ☆☆
18 Ural M Maximal Paths 32 88 34.11 tree DP, implementation ☆☆
15 Three Capitals B Book Pages 34 136 29.15 ad hoc ☆☆☆
14 Tatarstan B White Triangle 22 76 25.24 geometry
4 Eastern K GCD on the Segments 26 108 25.02 data structure ☆☆☆
10 Gomel E Exclusive Training 26 112 24.57 data structure
11 China I Prime Tree 31 192 22.37 graph theory ☆☆
15 Three Capitals I Puzzle with Tables 21 136 18.01 constructive ☆☆☆
9 Peterhof E Maharajah 17 90 17.92 brute force ☆☆
3 Spb C Number of Solutions 19 161 14.97 exponential ☆☆
16 America B Stars in a Can 13 95 13.34 geometry
15 Three Capitals E Cross on a Plane 15 136 12.86 geometry
13 Poland H Matching 11 80 12.3 graph theory ☆☆☆
2 Eurasia H Multiplier 21 313 11.87 brute force ☆☆
2 Eurasia A Maximum Sum with Swaps 18 313 10.17 DP ☆☆☆☆☆
12 Wroclaw J Explosions 9 79 10.13 math ☆☆☆☆
18 Ural I Intricate path 8 88 8.53 constructive ☆☆☆
10 Gomel A Ascent Sequences 9 112 8.5 combinatorics ☆☆☆
16 America F Incremental Double Free Strings 6 95 6.16 DP, implementation ☆☆
11 China H Order-Preserving Partition 8 192 5.77 combinatorics ☆☆☆☆
13 Poland A CNF-SAT 5 80 5.59 strings
17 Moscow Workshop F Online LCS 4 89 4.24 strings
11 China C Power of Power Partition Function 5 192 3.61 combinatorics ☆☆☆☆
14 Tatarstan G Milkland 3 76 3.44 geometry
15 Three Capitals G Pigeonhole Principle 4 136 3.43 interactive
13 Poland B Almost pattern matching 3 80 3.35 strings
18 Ural F Flight Trip 3 88 3.2 interactive, geometry
8 Europe D Dancing Disks 3 98 3.03 constructive
11 China A Almost Bobo Number 3 192 2.17 strings
10 Gomel I Inversions in Lexicographical Order 2 112 1.89 FFT
2 Eurasia D Park Trails 3 313 1.7 data structure
2 Eurasia L Give the Parabellum away 3 313 1.7 geometry ☆☆
11 China D Line Counting 2 192 1.44 number theory ☆☆
12 Wroclaw E Inconvenient Blockade 1 79 1.13 graph theory
16 America I Ski Resort 1 95 1.03 graph theory
8 Europe G Geohash Grid 1 98 1.01 implementation
10 Gomel C Cyclic Shifts 1 112 0.94 strings
5 Siberia J Battle City Online 1 119 0.92 brute force
3 Spb I Double Shuffle 1 161 0.79 ad hoc ☆☆
4 Eastern J Votter and Paul de Mort 0 108 0 geometry
8 Europe I Invisible Integers 0 98 0 DP
9 Peterhof D C-plus-minus 0 90 0 data structure
12 Wroclaw K Bridges 0 79 0 ad hoc
13 Poland D Mushrooms after rain strike back 0 80 0 data structure


I know I'm bad at several types of tasks - for example, long implementation, advanced knowledge, etc. However it seems I failed quite a bit of problems of my strength - math, combinatorics, DP, etc. My skill of competitive programming has plateaued 6.5 years ago, but still there's lots of room for improvement.

I'll upsolve all tasks with 3 or more stars, and hopefully some of 2-star tasks.










12 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Thanks for the analysis.

    I wish so, so much I could participate in these contests... How can I do so? Thanks!

    ReplyDelete
    Replies
    1. As far as I know, you can't without an account at http://opencup.snarknews.info/~ejudge from a registered university sector.

      Delete
    2. And how do I get one? :)

      Delete
    3. If you can go to one of the existing sectors, it's easy to participate. Otherwise I think you need to contact them with email (you can find the email address at opencup.ru).

      Delete
  3. Would you like to give me hint or approaches or solution to solve above problems ?

    ReplyDelete
  4. 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
  5. I must say 2016 & 2017 was the years of me trying so hard beyond many desperate measures to gain back love, trust and happiness from my better half after he left. After trying so hard beyond desperate measures to unite with my husband throughout the years, I became confused, frustrated for all the goals, hopes and ardent wishes of uniting my family. I thought maybe he is not really meant for me.
    Unfortunately, I almost accepted my fate before meeting dr. Wakina sometimes in January 2018 through: dr.wakinalovetemple@gmail.com to also become part of my life journey. With little or no fate, I pleaded and begged ardently for spiritual guidance and help he has been rendering to his numerous followers. Just as I pleaded, my request was accorded, my husband came back the exact date and time he predicted after the love spell.
    Now I realize that I can have everything through spiritual doctor like Wakina. Wakina was an eye opener after uniting my family. My destiny, goals, hopes, family were established through him and his powerful love spell.

    ReplyDelete
  6. Email Dr Sambo for real love spell: divinespellhome@gmail.com

    Hello viewers, I living in South Africa My name is Charlotte Keagan I am very happy to share this amazing testimony, i was hurt and heart broken when my husband left me with our two children, i was confused and didn't know what to do, i loved him so much, i tried all i could to bring him back but to no avail, on one faithfully day as i was coming from work i met a friend of mine whom i explain my problem to, and she told me of a spell caster called "Dr Sambo" whom also make her pregnant when she was looking for a child, i contacted the spell caster through the email she gave to me, and the spell caster told me what to do and i did exactly as i was told, to my grates surprise, my husband who has not called me for a very long time, called me and start apologizing for all the wrongs he did to me, and now he loved me more than ever before, brothers and sisters if you are passing through any kind problem contact him and i give you 100% guarantee that he will solve your problems. this is his contacts divinespellhome@gmail.com or contact him on his whatsapp mobile line +2348145810121

    ReplyDelete
  7. 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
  8. 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
  9. Pardon me for dropping this here, I see this platform as a medium and opportunity to clapback at some fellas that took sides during a crossroad moment in my life. Their negative energy thought me some valuable lesson that eventually lead me to the best healer (Dr. Wakina via dr.wakinalovetemple@gmail.com) that brought back my wife. I want them to know that I am back into her life after 2 years in exiled. A great spell work was done by Dr. Wkina, I was able to comprehend the reasons why my marriage was ruined by trusted fellas. I have taken several precaution measures ever since I returned back to my family as advised by Dr. Wakina to avoid future occurrence. It is amazing to say that over 5 months after the love spell our love has been stronger and better, we have also established our personal business across three countries. Guess my last laugh was the best. All thanks to great healer for giving me the best laugh.

    ReplyDelete