By adamant, history, 3 years ago,

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

• +173

 » 3 years ago, # |   +8 There is an AGC on 9 March, 15:00 (UTC +3). Could you change the time?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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)
•  » » » 3 years ago, # ^ |   +8 Personally I prefer 8 March, 12:00 (UTC +3).
•  » » » » 3 years ago, # ^ |   0 Welp, so be it then :)
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +8 Oh, codeforces placed rated round on the same time >.
•  » » » » » 3 years ago, # ^ |   0 10 March 16:30 then maybe?
•  » » » » » » 3 years ago, # ^ |   0 Not sure it's good idea to place it after Open Cup round...
 » 3 years ago, # |   0 What's the duration of the contest ?
•  » » 3 years ago, # ^ |   +3 5 hrs
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 [Deleted]
 » 3 years ago, # |   +8 how many string problems will there be?
•  » » 3 years ago, # ^ |   +191 Yes
•  » » » 3 years ago, # ^ |   +8 WA. :P
 » 3 years ago, # |   +14 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 ^.^'
 » 3 years ago, # |   0 Nice problems! I really enjoy them.
 » 3 years ago, # |   0 Nice problems! How to solve A?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +10 (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)
•  » » 3 years ago, # ^ |   0 You may also look into editorial for some kind of rigorous proof.
 » 3 years ago, # |   0 How to solve B and G?
•  » » 3 years ago, # ^ |   +5 Editorials are posted now :)
•  » » » 3 years ago, # ^ |   0 Thanks for the nice problem set:)
 » 3 years ago, # |   0 How to do I?
 » 3 years ago, # | ← Rev. 3 →   0 How to solve F?
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 How to solve J?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
 » 3 years ago, # |   +6 YuukaKazami you might also be interested in discussion here and/or editorial :)(Since I saw you wrote it on opentrains)
•  » » 3 years ago, # ^ |   0 Actually it's me.I think you should write "we should compute the distinct pairs" in the statement for the string problem.
•  » » » 3 years ago, # ^ |   0 That's true... Has it caused you any trouble?
•  » » » » 3 years ago, # ^ |   0 Not too much. BTW I really love the problem set. However, after finishing easy problems, I don't know which one is more solvable.
 » 2 years ago, # | ← Rev. 2 →   0 Why does this solution to I work in $O(n\log^2n)$?EDIT: I think wakaka's submission makes it clear: 61531106
•  » » 2 years ago, # ^ |   +10 I think it's explained in this article...
 » 21 month(s) ago, # |   +10 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$.
•  » » 21 month(s) ago, # ^ |   +10 Wow, pretty nice observation, thanks!