fvogel's blog

By fvogel, history, 6 weeks ago, In English

Hello Codeforces,

I couldn't find any blog on this year's round C so I decided to create one. Feel free to post your feedback and ideas on the contest.

Personally for me the start of the contest went pretty well. Problem D was particularly interesting and I solved it quickly. However I found problem C quite harder and got quite a few WAs. But I finally got a perfect score!

I plan on hosting a live discussion about the problems from this contest today at 6:00 PM UTC. The link will be posted here shortly. See you there!

Happy coding :)

UPD: Here is the link: https://www.youtube.com/watch?v=jvc_4ZT9da4

UPD 2: There's been a bug, here is the new link: youtube.com/watch?v=SL1-YYocQik

 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Got stuck on C, went to D, copypasted dp, got AC, went back to C, started crying.

Was C simulating it very fast or smth else?

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

    Only subtasks 1 and 2 can be solved with clever brute force

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

      can you tell what's your approach?

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        For each ant, find all the ants before it moving to the right and those after it moving to the left. Then you can notice that when two ants meet, only their indices swap but everything else stays the same, so if you don't care about their indices it's fine to just simulate the process. So sort the left part in descending order and the right part in ascending order then you can just brute force the intersections in $$$O(n)$$$.

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

    How did you approach D? I knew it had to be dp but couldn't figure out transitions and other stuff. Was it a well known problem?

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

      Simply just find total number of subsequences in range 0 to n-1 of length k using dp where k varies from 0 to n-1 and just use PNC after that

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

        Hi, I have been thinking for a long time, but still couldn't understand why the problem can be translate to this. Would you explain in more details.

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

    Can you solve the easier question: when will the last remaining ant fall off? The key observation from that problem is quite useful in C.

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

I also solved D but didn't solve C.

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

Auto comment: topic has been updated by fvogel (previous revision, new revision, compare).

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

unable to solve C, is that kind of bfs ?

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

can't solve B what was yr approach for b I find difficult with these type of question like the one https://codeforces.com/problemset/problem/1684/B what should i do

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

Auto comment: topic has been updated by fvogel (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

I made Video Solutions for all problems in case someone is interested.

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

Auto comment: topic has been updated by fvogel (previous revision, new revision, compare).