ivan100sic's blog

By ivan100sic, history, 2 weeks 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

My thoughts on the problems I have solved:

Problem 1
Problem 3
Problem 4
Problem 5
Problem 7

More coming soon!

• +197

 » 2 weeks ago, # |   0 wow! there is a div-1 A problem rated 3000
•  » » 2 weeks ago, # ^ |   +35 But the score distribution for this contest was "A-3000, B-750, C-250, D-3000, E-500, F-1500" !
•  » » » 2 weeks 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.
 » 2 weeks ago, # |   +13 Good luck!
 » 2 weeks 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.
•  » » 36 hours 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.
•  » » 35 hours ago, # ^ |   +3 So incredible to solve all problems without editorial!
 » 2 weeks 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
 » 2 weeks ago, # |   +16 Look at his heatmap! :-O
 » 10 days 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.