Блог пользователя Ritwin

Автор Ritwin, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится 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 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

How do you prove that's the solution for D?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I believe there's a proof by contradiction. If I can prove it I'll add it here.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

In E2, not many people know this i guess, but instead of using pair to form multiset, you can change less<int> to less_equal<int>. That gives the same result.

You can check my code for reference.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I didn't want to put that, because it causes problems when you have to remove elements. Using pair<int, int> works in that case as well.

    • »
      »
      »
      3 года назад, # ^ |
      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 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # ^ |
        Проголосовать: нравится 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