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