adamant's blog

Oleksandr Kulkov Contest 1 in gym
By adamant, history, 7 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?
»
7 years ago, hide # |
 
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
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What's the duration of the contest ?

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

how many string problems will there be?

→ Reply
»
7 years ago, hide # |
 
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
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Nice problems! How to solve A?

→ Reply
  • »
    »
    7 years ago, hide # ^ |
    ← 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
  • »
    »
    7 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

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

How to solve B and G?

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

How to do I?

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

How to solve F?

→ Reply
  • »
    »
    7 years ago, hide # ^ |
     
    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
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve J?

→ Reply
  • »
    »
    7 years ago, hide # ^ |
    ← 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
»
7 years ago, hide # |
 
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, hide # |
← 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
»
6 years ago, hide # |
 
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