adamant's blog

Oleksandr Kulkov Contest 1 in gym
By adamant, history, 6 years ago, In English

Hi everyone!

I gave a contest in winter Petrozavodsk programming camp and now I'd like to share it with codeforces by making it a contest in codeforces gym: 2018-2019 Winter Petrozavodsk Camp, Oleksandr Kulkov Contest 1. It was my first experience giving a contest to the camp and I'm pretty much excited about it!

In the camp only 7 out of 11 problems were solved, so there should be something in the contest for everyone. To make the contest more interesting I suggest you to participate in it as live contest on Saturday, 9 March, 12:00 (UTC+3), which may be changed in case of overlap with some other contest or if it's inconvenient for many participants. After this I suggest to gather here and discuss problems (if anyone's going to participate, of course). I will also post editorial which may (or may not) contain some neat stuff.

Uhm, good luck and have fun :)

P.S. It appears you already may see problems if you have coach mode enabled, I'd ask you to not do this unless you're not going to participate in contest!

UPD: Gentle reminder that it's less than 24 hours before the contest and it's hopefully not going to be rescheduled this time.

UPD 2: Thanks everyone for participating in the contest! Here are editorials: link

UPD 3: Google drive link got broken, so I uploaded the editorial to the contest directly.

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

Comments Comments (33)
| Write comment?
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

There is an AGC on 9 March, 15:00 (UTC +3). Could you change the time?

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

    I think so, but I'm not sure what time should I choose then.

    I'm considering 9 March, (from 17:30) or 8 March (from 12:00) or 10 March (from 16:30), all UTC+3. By "from HH:MM" I mean any time from HH:MM to, like, 18:30.

    Would like to know opinion of somebody who is interested in writing contest (if any)

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

      Personally I prefer 8 March, 12:00 (UTC +3).

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

        Welp, so be it then :)

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

        Oh, codeforces placed rated round on the same time >.<

        Guess have to move it again...

        I moved it to 15:30 same date for now, will move again if anyone complains

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

What's the duration of the contest ?

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

how many string problems will there be?

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

Because AGC has moved to Sunday, I move the time of my contest back to initial time of 12:00 (UTC+3) on Saturday, 9 March.

Sorry for inconvenience ^.^'

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

Nice problems! How to solve A?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +10 Vote: I do not like it
    (A * B)[0] = (A[1] + A[2]) * (B[1] + B[2])
    (A * B)[2] = A[0] * B[1] + A[1] * B[0]
    (A * B)[1] = (A[0] + A[1] + A[2]) * (B[0] + B[1] + B[2]) - (A * B)[0] - (A * B)[1]

    O(4^k)

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

    You may also look into editorial for some kind of rigorous proof.

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

How to solve B and G?

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

How to do I?

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

How to solve F?

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

    F: Consider all edges with cost at least x. Maintain connected components for all edges with such costs and for only major edges. Each component connected by all edges is a union of one of more components connected by major edges. If there are more than one components in that union when all vertices in this component are bad.

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

How to solve J?

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

    Let's assume there are no '?'. Then let's build a bipartite graph with n vertices in each part. For columns i and j if the first m - 1 characters in i-th column are equal to the last m - 1 characters in j-th column, add an edge (i, j) to the graph. We need to count the number of perfect matchings in this graph. Notice that each component in this graph is complete. If in some component number of vertices in both parts of the graph is different then the answer is 0, otherwise it's the product of factorials of sizes of components.

    Now let's deal with '?'. For each row calculate multiset of characters it that row. If some of these multisets are different then we can find out what each of '?' must be and solve the problem without '?'. Otherwise all the '?' should be the same character. Let's just try all possible characters. We only counted multiple times permutations that map each '?' to another '?'. So count the number of such permutations and subtract it each time.

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

YuukaKazami you might also be interested in discussion here and/or editorial :)

(Since I saw you wrote it on opentrains)

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

    Actually it's me.

    I think you should write "we should compute the distinct pairs" in the statement for the string problem.

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

      That's true... Has it caused you any trouble?

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

        Not too much. BTW I really love the problem set. However, after finishing easy problems, I don't know which one is more solvable.

        → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why does this solution to I work in $$$O(n\log^2n)$$$?

EDIT: I think wakaka's submission makes it clear: 61531106

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

There is a much easier solution for problem C :

let $$$F(x)=(x+1)^a(x-1)^b$$$, then $$$F'=\frac{aF}{x+1}+\frac{bF}{x-1}$$$.

Multiply the equation by $$$(x^2-1)$$$, then $$$(x^2-1)F'=a(x-1)F+b(x+1)F$$$.

By comparing the coefficients we find that $$$(n+3)f_{n+3}-(n+1)f_{n+1}=af_{n+1}-af_{n+2}+bf_{n+1}+bf_{n+2}$$$.

Since $$$a+b=N-1$$$, $$$2af_{n+2}=(n+3)f_{n+3}+(N-1)f_{n+2}+(N-n-2)f_{n+1}$$$. Find a non-zero $$$f_{n+2}$$$ and solve the equation, then we know the value of $$$a$$$.

→ Reply