### balbit's blog

By balbit, history, 10 days ago,

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
2. Sorcerers 2015
3. 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 :)

pow, odz, eni, abh,

• +149

 » 10 days ago, # |   0 Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
 » 9 days ago, # |   +5 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!
•  » » 9 days ago, # ^ |   0 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
•  » » » 9 days ago, # ^ |   0 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
•  » » » » 9 days ago, # ^ |   +15 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
•  » » » 9 days ago, # ^ |   +25 Yeah I've solved Dlugie Podoze before and remember it being pretty easy :)n/10 just looks too sus for normal algorithms
 » 9 days ago, # | ← Rev. 4 →   +10 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 wellAnd 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 TriinformathlonIf I have to subjectively rate funness of my own problems then it would be:10/10: Direction signs9/10: Interplanetary communication8/10: Crossroads of Parity7/10: Amusing journeys, Solar lamps 6/10: Bank, Messenger5/10: Dilligent John, Integrated circuit, Visits4/10: Metro
•  » » 9 days ago, # ^ |   0 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 :)
 » 9 days ago, # |   0 Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
 » 9 days ago, # |   0 Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
 » 8 days ago, # | ← Rev. 12 →   +26 I'm looking forward to this challenge! Although unfortunately I have a bit less free time for this one. 1. Multidrink. Solved on Jan 17Good problem, I liked it. The funniest part was when I realized that we have to go from 1 to $n$ and not between two arbitrary vertices. Instead of fixing a decent chunk of code I added 14 additional vertices and it was a pretty fun little trick. 2. Snake. Solved on Jan 19Well there goes my day... Really glad to be done with it. I think there might be an easier solution that uses the fact that the snake always exists, it would be nice to hear it. I didn't use it and just did a full $n^2$ dp, which I think had around 40 transitions. It was bearable during the first half when I implemented everything but in the second half I was fixing TLE on 1 single test case with .10s time limit for 3 or 4 hours straight and this part was incredibly frustrating. I already had a similar problem on Trips, but this one was much worse. This is what I really don't like about this platform. I'm almost confident they had a testcase with large $n$ and a small time limit just because it probably had a lot of solutions or a simple snake structure and I don't like not knowing the limits before I submit. Tried everything to optimize it but in the end I couldn't fit the full dp in tl for this testcase and had to run dp in dfs order and stop once I reach the end successfully. 3. Arkanoid. Solved on Jan 17Pretty good implementation problem. Feels nice "being forced" to do it and then somewhat enjoy doing it cleanly. 4. Strikes. Solved on Jan 17Yeah probably shouldn't be on the list :) For some reason I did $O(n \sqrt n)$ without thinking instead of linear but I was pretty sure it would pass anyway. 5. Rally. Solved on Jan 16Another easy problem, but a very good one. 6. Trips. Solved on Jan 18 I don't know if solved is the correct word but I AC'ed it. I REALLY struggled with this problem, it's actually the first problem out of the list I started implementing, spent 3 days and 30 submissions. I quickly got rid of all exponential cases and then spent a lot of time trying to force it with berlekamp-massey and/or polynomial interpolation on proper subsequences or by vertex. Then I finally realized how to do proper matrix multiplication to count all paths of length $<=l$ instead of just length $l$, but after that I was still frustratingly struggling with TLE on several small testcases. I finally made it work but I wouldn't have solved it yet on codeforces with the same time limits. 7. Panini. Solved on Jan 18Really cool dp with interesting greedy transitions and very short code. codeconst int A = 3003; ll d[A]; const ll INF = 1e18; int main() { int n, k, len; scanf("%d %d %d", &n, &k, &len); vector t(n+1,0); forn(i,1,n+1) scanf("%lld", &t[i]); t.pb(1e10); n += 2; forn(i,0,n+1) d[i] = INF; d[0] = 0; forn(r,0,n) { ll rb = t[r]; ll cand = 0; deque q; ll sumq = 0; int keep = 1; forn(nr,r+1,n) { q.pb(t[nr]); sumq += t[nr]; while(keep && rb + 2 * len <= t[nr]) { rb += len; int lef = k; while(q[0] <= rb && lef > 0) { lef--; sumq -= q[0]; cand += rb - q[0]; q.pop_front(); } if(lef == k) keep = 0; } if(t[nr] >= t[r] + len && q.size() <= k) d[nr] = min(d[nr], d[r] + cand + (ll)q.size() * t[nr] - sumq); } } cout<
•  » » 6 days ago, # ^ |   +20 Regarding Direction SignsHmmm... The intended solution was $O(50 \cdot (nm + n^2 + \frac{n^2m}{64}))$. I reckon was unaware of solutions in complexities that you mention.But now that I think about this problem from a bit different angle than I did these years ago... I see how $O(n^3/6)$ could be achieved. Not sure about /128 though.I think that I was fixated on an idea where I choose one particular sign that I hope belongs to the solution and I transform the whole instance to the equivalent one where it has all zeroes and other relevant signs have only 0 or 1. If the solution is big enough then I can guess such sign randomly (hence 50 in the initial complexity from the 50 guesses), but now I see it could be done in a smarter way, where at the very beginning I transform each sign so that it has 0 at the first coordinate and for each pair I record min and max difference after subtracting one from the another. If all such coordinates differences are between 0 and 1 then I put an edge from the smaller one to the larger one and I never have to examine that pair carefully again (i.e. I don't have to loop over these m coordinate).I guess situations like these can happen when an author suggests a problem with some specific constraints and everyone involved in its preparation is skewed because of them and is satisfied after getting a solution that meets them and another better approach may slip by unnoticed.
•  » » » 6 days ago, # ^ |   +10 Thanks for the answer!Yeah the statement obviously heavily suggested the randomized solution but I just couldn't see how it can improve the complexity. And you got pretty much everything right. Just a small note, probably more of a personal preference: Instead of making the first coordinate 0 we can subtract the minimum coordinate from each sign. I think it is just a bit nicer because now, when we sort the signs by the sum of coordinates, we can only consider edges from left to right (condition for the edge is the same) and now we just have to find the longest path with start and end connected by a direct edge. That's what I actually really liked about the problem — how magically it turned from a scary and messy input data to a very clean and concise task.Also you made me think more carefully about /128 optimizations and the idea I had in mind was indeed wrong. I still think there is a chance it might be possible but at least it's not that simple.
•  » » 6 days ago, # ^ |   +20 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
•  » » 5 days ago, # ^ |   +10 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 :)
•  » » » 4 days ago, # ^ |   0 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 :-|
 » 7 days ago, # |   0 Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
 » 7 days ago, # |   0 Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
 » 6 days ago, # |   0 Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
 » 6 days ago, # |   0 Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
 » 6 days ago, # | ← Rev. 3 →   +31 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
 » 5 days ago, # |   0 Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
 » 3 days ago, # |   0 Auto comment: topic has been updated by balbit (previous revision, new revision, compare).