KieranHorgan's blog

COCI 2017/2018 — Round 7
By KieranHorgan, 6 years ago, In English

The seventh and final round of COCI 2017/2018 season took place this Saturday at 14:00 UTC and has just finished. As no blog seems to have been created for the contest, let's discuss the problems here now that the contest is over.

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

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

Results are now available and analysis mode is now open.

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

    How do you access analysis mode? I did not know COCI has this

    → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Would just like to state that problem C had pretty bad testcases, since a very wrong greedy approach (that I used and it seems like many others) got 90 points out of 100 (only 1 testcase counters that approach and it's easy to come up with some).

Aside from that it went pretty bad for me, with a bug on E that cost me 126 points, and a solution to D that I finished 30 seconds before the time was up so I submitted without even testing it (and I had horrible bugs).

On another topic, the only problem I didn't attempt was F. If I understood it correctly, we can merge all bus stops that are on the same line. We can also compute all pairs of distances of a kid and a bus stop. Then we need to assign at most C kids to a line, while having the minimum possible value for the maximal distance a kid needs to go.

So, I suppose we can try doing binary search on the answer. On some iteration with mid, we will remove all pair distances greater than mid, and then we need to check whether a correct assignment exists with the remaining pair distances, though I'm not sure how to do this part.

Anyone who solved F?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    The last part is a succession of max flow problems. And a linear seach is enough: you don't have to start from scratch every time, because adding edges to the graph doesn't affect the admissibility of the assignment.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there supposed to be bus lines with 0 stops? It seems my solution passes when I remove an assert statement that checked if the bus line had 0 stops.

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Problem D (CLICKBAIT): The structure is a rooted tree. Dfs and print ids in postorder.

Problem E (DOSTAVLJAC): DP on tree. dp1[v][i] := max amount of peppers in i units of time from v to any node in v subtree. dp2[v][i] := max amount of peppers in i units of time from v and back to v in v subtree. I think it runs in O(min(N2, N * M2)).

Problem F (PRIGLAVCI): If C * K < N then no solution, print -1. Otherwise, bisection the maximum distance. Maximum flow to detect a valid assignment.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Can you explain the reccurence relations in problem E?

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

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

    dp[time][current pokemon][farthest pokemon]
    For each state you have a range of pokemon which you have passed, either c...f or f...c. Current pokemon is the one end of the range which you are currently standing at, farthest is the other end of the range which you have passed before.
    There are only two transitions, either you continue in the same direction (current changes by 1, farthest stays the same), or else you walk to the other side of the range (current becomes farthes +/- 1, farthest becomes old current).

    → Reply