### ivan100sic's blog

By ivan100sic, history, 23 months ago,

Tonight, I will pick twelve 3000 rated problems I haven't solved yet, try solving them, and track my progress. As usual, I will not look at editorials. Hopefully I will be able to solve them all before the year ends. I will not make this my highest priority and I won't try too hard. I will keep solving other problems in the meantime.

The problems are:

1. 341E - Candies Game (solved Jan 14, 12 days)
2. 843E - Maximum Flow
3. 1250D - Conference Problem (solved Jan 5, 3 days)
4. 573D - Bear and Cavalry (solved Jan 6, 4 days)
5. 1290D - Coffee Varieties (hard version) (solved Jan 8, 6 days)
6. 568E - Longest Increasing Subsequence
7. 788D - Finding lines (solved Jan 14, 12 days)
8. 698F - Coprime Permutation (solved Jan 3, 1 day)
9. 1342F - Make It Ascending (solved Jan 4, 2 days)
10. 1236F - Alice and the Cactus (solved Jan 3, 1 day)
11. 533A - Berland Miners (solved Jan 16, 14 days)
12. 1411F - The Thorny Path (solved Jan 22, 20 days)

My thoughts on the problems I have solved:

Problem 1
Problem 3
Problem 4
Problem 5
Problem 7

More coming soon!

• +197

 » 23 months ago, # |   0 wow! there is a div-1 A problem rated 3000
•  » » 23 months ago, # ^ |   +35 But the score distribution for this contest was "A-3000, B-750, C-250, D-3000, E-500, F-1500" !
•  » » » 23 months ago, # ^ |   +81 Yes, there were a few rounds with "dynamic scoring", the score of problems was based on the number of people who solve them, and problems were given in random order.
 » 23 months ago, # |   +13 Good luck!
 » 23 months ago, # | ← Rev. 16 →   +80 Thank you for sharing, I will try the same problems in the following days/weeks and will keep this comment updated with those I solve. Problem 2: Solved in the past. Problem 3: Solved on the 4th of January. Challenge: solve the problem for $n \le 5000$. Comment (in white): I read balbit's comment and I disagree with him. For me this was clean, nice and hard dp problem. My implementation is straightforward, but I had to think a lot (and my first solution was wrong). Problem 4: Solved on the 4th of January. Comment: My solution is O(nq) and gets accepted without any optimization. Problem 7: Solved on the 5th of January. Problem 1: Solved on the 5th of January. Comment: This one is cool. The hardest for me among the ones I have solved. Problem 5: Solved on the 5th of January. Comment: Not very interesting problem. The question is interesting, the solution not so much. My solution is different from the official one and I had to suffer to reduce enough the number of queries. Problem 6: Solved on the 5th of January. Problem 9: Solved on the 5th of January. Comment: Coming up with the dp is easy, implementing it and optimizing it not so easy. I did not like this one, not recommended. Problem 8: Solved on the 6th of January. Problem 11: Solved on the 6th of January. Problem 12: Solved on the 6th of January. Comment: I don't see the point of this kind of problems: a greedy (which is screaming greedy) which involves a gazillion cases. One day I'll start appreciating these kind of problems, or at least I'll learn how to solve them in a reasonably short amount of time. Problem 10: 16th of January. Comment: By far the hardest for me. I did not think of using the Euler characteristic formula to count the connected components (I read this in the editorial after getting AC) and went on a totally different path. I had never decomposed a cactus in its components and that was educational. I had to summon all my perseverance to resist the urge to read the editorial before I realized how to solve the problem.
•  » » 23 months ago, # ^ |   +23 Challenge completed! It was fun and I feel like I improved a little bit.This list was perfect as it forced me to think about and solve problems which were not particularly attractive to me and so I learnt tricks and ideas which I would have never encountered if not forced.
•  » » 23 months ago, # ^ |   +3 So incredible to solve all problems without editorial!
 » 23 months ago, # |   +38 Funnily enough, there is a Prime New Year Contest right now ;) You can try your luck there as well, I always have a lot of fun with it
 » 23 months ago, # |   +16 Look at his heatmap! :-O
 » 23 months ago, # | ← Rev. 13 →   +46 Looks fun! I'd like to join too. Problem 1: Solved Jan 5Fun-ness: Spoiler8/10, would recommendProblem 2: Solved Jan 15Fun-ness: Spoiler4/10, maybe it'll be more fun if you solve it properly SpoilerAs someone inexperienced with flows, I was stuck on this problem for super super long (I spent approximately the same amount of time on this one problem as all the other ones combined...), so I decided to adopt the strategy of "try random stuff, find counterexamples, and improve the solution." 3 hours and 19 submissions later, I was finally able to get it to pass. :(Problem 3: Solved Jan 5Fun-ness: Spoiler3/10, there's more to it than meets the eye, but it's still a fairly boring problem with somewhat annoying implementationProblem 4: Solved Jan 5Fun-ness: Spoiler5/10, it doesn't seem hard enough to warrant a 3000* rating (?) SpoilerOnce you have an O(nq) solution, it's quite easy to see how to optimize it to a O(qlogn), but I'm glad I saw dario's comment and didn't bother implementing the optimization :PProblem 5: Solved beforeProblem 6: Solved Jan 7Fun-ness: Spoiler5/10, not all that fun... ? It could've been a nice and cute problem had they simply asked for the LIS instead of making you construct one. SpoilerI guess I'm really bad at estimating how fast a program runs... I'm still not sure how > 2e8 operations on pairs of pairs were able to run in only ~1.5 seconds.Also, implementation details are kind of annoying...Problem 7: Solved Jan 6Fun-ness: Spoiler6/10, eh SpoilerIt would've been more fun if the query limit were slightly less tight... Problem 8: Solved Jan 6Fun-ness: Spoiler5/10, I don't really like number theory-style analysis problems SpoilerAlso, I feel kinda bad because I solved it by running brute force, finding patterns, and trying random stuff...Problem 9: Solved Jan 10Fun-ness: Spoiler2/10, WTF??? SpoilerI thought for a long time and couldn't come up with anything better than a simple O(n^2 * 3^n), so I coded it up (with pruning) and it passed...???Very bad problem. The input constraints are also hard to understand. Not even educational. Problem 10: Solved Jan 8Fun-ness: Spoiler8/10, Pretty cool problem! Would recommend... if you can get past the complicated statement. SpoilerActually I'm just relieved that it didn't end up becoming some disgusting BCC-dp hahaWould've been nicer if they just asked for E[X^2] instead of variance thoughProblem 11: Solved Jan 10Fun-ness: Spoiler7/10, Ok I guess. I like these kinds of graph/range analysis problems. SpoilerAlthough I feel a little bad because I solved it with 2 log factors :PProblem 12: Solved Jan 10Fun-ness: Spoiler1/10, AAaaAAaaaaAAAAAaaaAAAhh I hate casework problems :(((( aaaaa SpoilerI actually tried this problem ~1 year ago using some greedy approach and then rage quit... This time I ran brute force DFS on small cases instead and was able to finally pass
•  » » 23 months ago, # ^ |   +41 Challenge complete! I greatly enjoyed tackling this list with others, and I would love to join (or create?) a second round (maybe a level 2 round with 3100s???) soon!One thing I think this challenge could benefit from is either more problems or a shorter time span. It can be frustrating to have only one problem left on the list that you can't read the tutorial for until the end of the year. But overall, I found this challenge very fun, so thank you ivan100sic again for the initiative!
 » 23 months ago, # | ← Rev. 3 →   0 I'd like to join too.I copied this one to another website. However, I do not have enough time, so maybe I can't solve them in a short time. And maybe I will read the solutions.Good luck!ListUPD: It seems the problems maybe too hard for me, maybe I can't solve them, but I will try my best.
•  » » 23 months ago, # ^ |   +3 I solved 341E - Candies Game!
 » 23 months ago, # | ← Rev. 8 →   +18 Thank you for the post, this is a great idea and I'm in! ;) I will split the problems into 3 categories.Main category: 1. Problem 2: Solved on Jan 7I liked this problem a lot. It looked very easy at first sight and I thought I solved it in 1 minute, but after implementing it, for 30 minutes I thought that I can't write a dfs properly. Turned out I was missing a small detail which actually made the problem very enjoyable and also made it much easier to implement. The solution is very clean and nice to code. 2. Problem 4: Solved on Jan 8Not a big fan but not a terrible problem either. Maybe just a coincidence but I've seen a lot of very similar problems lately. Actually solved it yesterday as well but didn't want to implement it right away. 3. Problem 6: Solved on Jan 7Didn't like the problem at all. Felt like a straightforward solution will pass, wrote it and it passed after fixing some bugs. Although it passed barely there was a lot of room for constant optimizations I haven't really started doing any. 4. Problem 10: Solved on Jan 7Great problem! Looked impossible for a long time with some dark and horrible dp ideas, but the solution is actually very nice and feels great to come up with. Definitely recommend it. 5. Problem 11: Solved on Jan 10Mixed feelings but more to the good side. I had a $O(n\cdot(\log n)^2)$ solution which was obviously meant to be cut, but the idea was really interesting to me and quite fun to code, and the constant factor was pretty good so I thought there were some chances to fit it. After I upgraded it to $O(n log n)$ with segtree it became more standard, not that fun, and judging by the runtime my constant is now shit :) Problems from contests I have not virtually participated in before this post. Will do so when I have time: 1. Problem 1: Didn't get it on the virtual contest, solved on Jan 11This was by far the hardest problem out of the list for me, even though I usually really like this kind of problems. It's cool to see an actually hard problem with a pretty natural and simply describable operation. I was actively thinking about it for 3 days, my first solutions were very vague and theoretically had around $1\textrm{-} 2 \cdot10^7$ operations in the worst case (probably much less in fact), and my final solution (which is much cleaner and doesn't have a ton of modular logarithms) had the upper bound of I think 2,000,000 in the simple form or ~1,050,000 with the optimization. Clear form passed with 800000 operations on what looks like a hack (actually close, I thought it had a larger practical margin) and the optimization went below 100000. 2. Problem 3: Did the virtual contest, solved it in time. Jan 10Just a good problem no more no less. Final solution is pretty clean and nice and my solution also works in $O(n^2)$ like dario2994's. 3. Problem 9: Did the virtual contest, solved it in time. Jan 7Not a bad problem, somewhat liked it. The only thing I didn't like is that it's hard to estimate the running time and you kind of have to rely on problem setters to do that for you. But at the same time it was on a full feedback contest and it's also pretty clear that this is the intended complexity so it's not that bad.Problems I solved before: Problem 5: Upsolved after a virtual contest. Problem 7: Upsolved after a contest. Problem 8: Solved on a contest. Problem 12: Solved on a virtual contest.
•  » » 23 months ago, # ^ |   +34 Done with the challenge. I had a lot of fun, thanks again to ivan100sic and all fellow solvers! It was cool reading the comments of the others after solving the problem. Would be glad to join something like this again in the future :)
•  » » » 23 months ago, # ^ | ← Rev. 2 →   +8 Congrats! I'm only halfway there
 » 23 months ago, # |   -19 533A Rated 3000 !!!!!!!!!!!!!!!!!!!!!!!!!!
 » 11 months ago, # | ← Rev. 2 →   +11 Will you do another one this year?
•  » » 11 months ago, # ^ |   0 I would love to but I'm currently kind of low on energy for these hard problems