balbit's blog

By balbit, history, 3 years ago, In English

Inspired by ivan100sic's problem list blog, I'll pick 10 nontrivial-seeming recent POI (Polish Olympiad in Informatics) problems that I haven't solved and track my progress here.

It seems to me that POI is better suited for this format as their editorials are quite difficult to find (if possible at all).

While Ivan's original challenge was supposed to last an entire year, I'm not nearly as patient, so I won't look for editorials only until February 1st (in just over 2 weeks). Hopefully I'll have completed at least 80% by that time. Until then, GLHF!!!

The List:

  1. Multidrink 2013 [Solved Jan 15]
Fun-ness:
  1. Snake 2014
  2. Arkanoid 2016 [Solved Jan 16]
Fun-ness:
  1. Strikes 2017 [Solved Jan 16]
Oops
  1. Rally 2014 [By the way, I've been stuck on this one for super long. Currently getting wrong answer on one test case (89 pts) for unknown reason.] [UPD: I ACed this problem, but my solution is wrong. It's just very hard to block with a random generator. I'll try to think of & write a proper solution when I have some more time.]
Current Spaghetti Code (with brute force checker and generator...)
  1. Trips 2015 [Solved Jan 18]
Fun-ness:
Help
  1. Panini 2017 [Solved Jan 19]
Fun-ness
  1. Crossroads of Parity 2017 [Solved Jan 19]
Fun-ness
  1. Hydrocontest 2016 [Solved Jan 30]
Fun-ness
  1. Sorcerers 2015 [Solved Jan 31]
Fun-ness
  1. Direction Signs 2015 [Solved Jan 20]
Fun-ness

Note: I'll also leave comments/hints here in case I manage to solve them or (unfortunately) have to dig around CSDN for their solutions :)

Tags pow, odz, eni, abh, ai
  • Vote: I like it
  • +149
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by balbit (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

You'll probably be able to solve all from here if you are sufficiently motivated, I have looked at all of them in the past and none of them is ultra hard.

Consider Klubowicze (aka Club players? ) from POI 23 final 2nd day, Tablice Kierunkowe (road signs?) from POI 22 day1 final and Dlugie Podróże (long routes?) from POI 26 day2 final, they should be plenty of fun!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The fact that nobody has solved Dlugie Podroze is some misunderstanding, it had difficulty level 1/5 in an internal document (I would give it higher note, but that's what it got there) and I am positive I would solve it within 10 minutes on a contest xd

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      True!!! As an author of that problem I was completely astonished to see it had like 5 solves overall. I would understand it in a contest with ranking available (nobody is solving because nobody else is solving), but in POI?

      Perhaps it's a standard trick for ICPC but not so common among higj schoolers

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        Oh, I must have misremembered. I thought it was solved by absolutely nobody, but it was actually solved by 8 people, which makes more sense. Now I remember the original thing I noted was that "nobody from Polish IOI team has solved it" instead of "nobody has solved it". A cool problem anyway, I was advocating for its inclusion at the time

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      Yeah I've solved Dlugie Podoze before and remember it being pretty easy :)

      n/10 just looks too sus for normal algorithms

»
3 years ago, # |
Rev. 4   Vote: I like it +10 Vote: I do not like it

Happy to see Crossroads of Parity here cause that's mine problem :D. I actually got very good feedback from competitors about it, they all seemed to have loved it. However my personal favourites out of ones by me are Direction signs and Interplanetaty communication (But I am not sure if we want to use this set for some international team competition? So I won't link it here and please don't investigate yet :P). Funnily enough, both got quite terrible feedback from contestants xD (for direction signs it was more of an issue of weak tests allowing for heuristic solutions, not the problem itself). Amusing journeys is quite decent as well

And have fun with Snake, that's the biggest shit I have ever seen (it got accepted by two contestants during the first stage and code of one of them got over 3 thousand lines xD)

Some of the most fun one that are not on your list also include Cook and Triinformathlon

If I have to subjectively rate funness of my own problems then it would be:

10/10: Direction signs

9/10: Interplanetary communication

8/10: Crossroads of Parity

7/10: Amusing journeys, Solar lamps

6/10: Bank, Messenger

5/10: Dilligent John, Integrated circuit, Visits

4/10: Metro

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the recommendations!

    I've solved cook and triinformathlon before and liked both of them a lot (I think triinformathlon appeared again in a recent opencup).

    I've been analyzing the structure of the snake for a few hours and... it looks super scary :P Maybe I'll save it for last?

    I'll make sure to check out direction signs later too :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by balbit (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by balbit (previous revision, new revision, compare).

»
3 years ago, # |
Rev. 12   Vote: I like it +26 Vote: I do not like it

I'm looking forward to this challenge! Although unfortunately I have a bit less free time for this one.

1. Multidrink. Solved on Jan 17
2. Snake. Solved on Jan 19
3. Arkanoid. Solved on Jan 17
4. Strikes. Solved on Jan 17
5. Rally. Solved on Jan 16
6. Trips. Solved on Jan 18
7. Panini. Solved on Jan 18
8. Crossroads of Parity. Solved on Jan 18
9. Hydrocontest. Solved on Jan 20
10. Sorcerers. Solved on Jan 17
11. Direction Signs. Solved on Jan 18
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it
    Regarding Direction Signs
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it
      Thanks for the answer!
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Regarding Snake and your struggle. I feel you, we had examples in the past, where contestants got lower points because some moron decided to set TLs to Constant*(model solution) where sometimes model solution was unusually fast because of structural properties of tests with big size, what basically forces you to get exactly the same solution as the model one instead of any with right complexity. Fortunately these were not historically often. And respect for getting at ACed xd

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Done with the challenge! This set was significantly more implementation heavy than the last one (which is expected because of the different type of source competitions) but it also had a lot of beautiful problems I really enjoyed. And as for the implementation part of the set — this is exactly the type of problems I usually lack the motivation to practice or upsolve so I feel like I've actually improved on that side for quite a bit.

    Thanks balbit for great problem selection and I will keep following this post to read your feedback on the remaining problems :)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Whoa, congratulations!

      I hope I can complete the challenge in time as well :)

      Unfortunately szkopul seems to be down right now... hopefully it won't take too long :-|

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by balbit (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by balbit (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by balbit (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by balbit (previous revision, new revision, compare).

»
3 years ago, # |
Rev. 3   Vote: I like it +31 Vote: I do not like it

Regarding Panini, you must have gotten a pretty serious bug if it costed you 16 points ;p. This was sadly probably the worst prepared problem ever on POI, where literally nobody has solved it during contest, but tons of people got 92pts with some shitty super simple greedy.

Btw you don't need multitests to remedy this. Tests are usually partitioned into packages and you get points for a particular package only if all your answers on this package were correct

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by balbit (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by balbit (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by balbit (previous revision, new revision, compare).