Genius3435's blog

By Genius3435, 4 weeks ago, In English

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 chikku1729 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
 
 
 
 
  • Vote: I like it
  • +39
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for explaining. I completely overlooked this point.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also came to find proof, but I am going to prove that the given solution is correct. Help me how you derived (your thought process) the solution

    assume there are just 3 people and you have sorted then by their max time to talk and time now is $$$t_1$$$

    $$$a_1 <= a_2 < a_3$$$

    the solution chooses $a_3$ along with $$$a_2$$$ (you can choose anyone with $$$a_3$$$) at $$$t_1$$$

    let's assume you instead chose $$$a_2$$$ and $$$a_1$$$, the max time you can involve all these guys is

    minimum of $$$a_1$$$ and $$$a_2$$$ + whatever is left with $$$a_2$$$

    $$$ min(a_2, a_1) + (a_2 - min(a_2, a_1)) = a_1 + (a_2 - a_1) = a_2 $$$

    but if you chose $$$a_3$$$ you can involve them for

    $$$ a_2 + (a_3 - a_1) $$$

    I made a mistake of not considering the "picking the next pair" after every unit time :P in my practice and was searching if any one can prove it.

    Genius3435 please help us with how you derived the solution, thanks!

»
4 weeks ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      You can erase elements like this if you need too.

      indexed_set.erase(indexed_set.find_by_order(indexed_set.order_of_key(key)));

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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