### Ritwin's blog

By Ritwin, 3 years ago,

This was a fun contest, and I solved all the problems except G.

### Thoughts

• A: Nice and simple problem A. Not much to say here
• B: Nice problem on sorting, but it may have been a bit too hard for a problem B. Also, as 4dh4r5h said, it's possible that there was cheating in B.
• C: Not a bad solution idea, but it's very easy to mess up the implementation. That's probably why it was the hardest out of [A...E1]
• D: Nice problem, but it was very similar to a previous one. Good difficulty level for a Div3 D though.
• E1: Very misplaced. Not much else to say here.
• E2: Nice problem with an interesting solution idea.
• F: Nice problem, although I'm not sure another adhoc problem was the best choice for a problem F.
• G: I didn't solve it given time, but according to yash_daga, it's a 2d dp problem.

### Solutions

A
B
C
D
E1
E2
F
G
• +39

| Write comment?
 » 3 years ago, # |   0 Another one here. for A to F https://codeforces.com/blog/entry/95352?#comment-844267
 » 3 years ago, # |   0 In the solution for F can you please tell why are you putting a upper bound of $2$ on $loops$? If I am able to understand correctly the loop variable helps in counting the number of times we have looped over the array ( number of times passed or reached the starting index). However I am confused as to why the upper bound of 2 is working for the variable.
•  » » 3 years ago, # ^ |   0 Also note that the longest streak might start from the end of the positions and loop back to the start, but we can easily remedy this by iterating twice. That just saves us from wrapping the loop in a for (int it = 0; it < 2; ++it)
•  » » » 3 years ago, # ^ |   0 Thanks for explaining. I completely overlooked this point.
 » 3 years ago, # | ← Rev. 2 →   +1 How do you prove that's the solution for D?
•  » » 3 years ago, # ^ |   0 I believe there's a proof by contradiction. If I can prove it I'll add it here.
 » 3 years ago, # | ← Rev. 2 →   +9 In E2, not many people know this i guess, but instead of using pair to form multiset, you can change less to less_equal. That gives the same result.You can check my code for reference.
•  » » 3 years ago, # ^ |   0 I didn't want to put that, because it causes problems when you have to remove elements. Using pair works in that case as well.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 You can erase elements like this if you need too.indexed_set.erase(indexed_set.find_by_order(indexed_set.order_of_key(key)));
•  » » 3 years ago, # ^ |   0 You have no idea how much you can get messed up with less_equal in pbds. It is a usual practice to not have this less_equal in pbds
•  » » » 3 years ago, # ^ |   0 yes I have encountered same problems as given in those comments. But also, it only has issues with erasing, which has an alternative(by erasing the pointer to it) and also with lower_bound, which can be thought of as, lower_bound gives upper_bound and vice-versa.Anyways, its like you can use #define int long long as it is convenient but obviously, it is a bad practice and care must be taken.you do you