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:

- 341E - Candies Game (solved Jan 14, 12 days)
- 843E - Maximum Flow
- 1250D - Conference Problem (solved Jan 5, 3 days)
- 573D - Bear and Cavalry (solved Jan 6, 4 days)
- 1290D - Coffee Varieties (hard version) (solved Jan 8, 6 days)
- 568E - Longest Increasing Subsequence
- 788D - Finding lines (solved Jan 14, 12 days)
- 698F - Coprime Permutation (solved Jan 3, 1 day)
- 1342F - Make It Ascending (solved Jan 4, 2 days)
- 1236F - Alice and the Cactus (solved Jan 3, 1 day)
- 533A - Berland Miners (solved Jan 16, 14 days)
- 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!

wow! there is a div-1 A problem rated 3000

But the score distribution for this contest was "A-3000, B-750, C-250, D-3000, E-500, F-1500" !

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.

Good luck!

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.

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).Comment: My solution is O(nq) and gets accepted without any optimization.Comment: This one is cool. The hardest for me among the ones I have solved.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.Comment: Coming up with the dp is easy, implementing it and optimizing it not so easy. I did not like this one, not recommended.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.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.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.

So incredible to solve all problems without editorial!

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

Look at his heatmap! :-O

Looks fun! I'd like to join too.

Problem 1: Solved Jan 5

Fun-ness:

Spoiler8/10, would recommend

Problem 2: Solved Jan 15

Fun-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 5

Fun-ness:

Spoiler3/10, there's more to it than meets the eye, but it's still a fairly boring problem with somewhat annoying implementation

Problem 4: Solved Jan 5

Fun-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 :P

Problem 5: Solved before

Problem 6: Solved Jan 7

Fun-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 6

Fun-ness:

Spoiler6/10, eh

SpoilerIt would've been more fun if the query limit were slightly less tight...

Problem 8: Solved Jan 6

Fun-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 10

Fun-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 8

Fun-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 haha

Would've been nicer if they just asked for E[X^2] instead of variance though

Problem 11: Solved Jan 10

Fun-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 :P

Problem 12: Solved Jan 10

Fun-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

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!

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!

List

UPD: It seems the problems maybe too hard for me, maybe I can't solve them, but I will try my best.I solved 341E - Игра с конфетами!

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.

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 :)

Congrats! I'm only halfway there

533A Rated 3000 !!!!!!!!!!!!!!!!!!!!!!!!!!