rsFalse's blog

By rsFalse, history, 8 years ago, In Russian

Which problems did you enjoy the most? I enjoyed problem N.Kitchen (div.2), a very interesting math problem. How to solve div.2. G and O?
P.S. I have found that upsolving of 15, 16, 17 rounds have appeared!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

O: Find two smallest primes which are not equal to given one and multiply given prime by them.

G: Count leading Ls plus trailing Rs and add 1 if there is something between them.

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

    Thank you for G, I didn't realise that after Ls and Rs I need to add 1 if something is between. Upsolved with simple

    regex

    In problem O, I couldn't pass TC#1, with this perl code :(

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve D, A, C?

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    D: Let's define f(i) as the best score we can get if we end in a position i. We need to maintain all available transitions (with respect to the segment length constraints) for the current position. When we move i to the right, we need to delete one element and add another one. After that, we need to take the maximum of f(i) for all smaller prefix sums and add 1 to it, just take the maximum with the same prefix sum andvthe maximum minus 1 for all larger prefix sums. If we use a segment tree, insertions/deletions are just point updates and getting an optimal transition is reduced to three range max queries.

    C: One can show that a pair is bad (that is, neither even nor odd) if and only if it lies inside a non-bipartite edge-biconnected component or such a component is reachable from one of the vertices. So we need to find all biconnected components and remove those that are not bipartite. After that, we have several bipartite components. Let c0 and c1 be the number of vertices 0 and 1 colors in some component. We need to add c0 * (c0 - 1) / 2 + c1 * (c1 - 1) / 2 to the number of even pairs and c0 * c1 to the number of odd pairs.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody give me a link on statements for GP of Moscow Div2. Or a link on virtual contest. Please