Hello Codeforces!
I would like to invite you all to Byterace 2K17 to be held on codechef. It is scheduled on Wednesday 15th February 2017, 9:00PM IST.
The contest will be 3 hours long and will have 6 problems.
It has been prepared by me(Equinox), I_Love_Equinox and cc15. We have given a lot of effort in making the problems and hope that you would like them.
Prizes
- 1st Prize 5,000 INR
- 2nd Prize 3,000 INR
- 3rd Prize 2,000 INR
)
Note
It is not necessary to be a college student to win prizes. Just fill "NA" in college field in the google doc given on the contest page.
Update
Problem authors and their respective problems-
I_Love_Equinox — FGAME, BATGRAPH, DIVIS
Equinox — ADWAR, MODNIM
cc15 — CHARR
Congratulations to the winners. The top 5 are as follows (all from different countries).
Deemo
rns4
nuip
YerzhanU
SameerGulati
Auto comment: topic has been updated by Equinox (previous revision, new revision, compare).
Auto comment: topic has been updated by Equinox (previous revision, new revision, compare).
LOL! i_love_aishwarya_tandon ,, bro use a One time pad to keep it secret :D
Auto comment: topic has been updated by Equinox (previous revision, new revision, compare).
Reminder:- The contest starts in 30 Minutes. See you at the leaderboard.
Prizes are only for indians, right?
Its for everyone.
When will I receive the prize?
We will be contacting all the winners soon via email regarding the prizes.
Again the same CodeChef bug: I solved 5 problems, but it only displays 4. It is because I submitted ~30 seconds before the end of the contest.
We will take that into consideration. But the first 3 have solved all problems.
Editorial or short descriptions ?
Here are the problems that I solved in contest time:
FGAME: We have c[0] white balls and c[1] + ... + c[n - 1] black balls. Try to put just one white ball in every box, and all the remaining white and black balls in the last box.
BATGRAPH: The bridges of the graph generate a tree of biconnected components. The answer is ⌈ leafs / 2⌉ (why? look at the centroid of the tree)
CHARR: We only have to calculate the longest path in the pseudoforest.
DIVIS: Let's concatenate all the strings, then we can do dp: f[i][len][r] is the number of subsequences starting from i of length len and congruent with r modulo d
ADWAR: Create a polinomial P(x) = f0·x0 + f1·x1 + ... + fn·xn, where fi is the number of soldiers with strength i. We can calculate the number of pairs that sum s by looking at the coefficient of xs in P(x)2
Regarding BATGRAPH leafs/2 seems is not right. Counterexample:
1
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
Here we have bridge 3->4 which should be directed to one side and we need make another component reachable by adding one edge.
After generating the tree, we get only 2 vertices and two leafs: [1 2 3]-[4 5 6]. We have to add just one edge
There is no vertex 7 in my example.
Yes I've updated the image, I thought 6 7 was an edge :)
Oh I see what you mean. You mean leafs after compressing biconnected components. I thought you were talking about leafs at initial graph. Both solutions were passing tests so I was confused.
Test data were too weak.The very first successful submission for BATGRAPH prints 0 for this input graph while the correct answer is 1500.
you are right :(
In BATGRAPH can you explain what leafs are in that tree of biconnected components?And can u explain the leafs/2 part?
Hi, I am the author of this problem. First you must understand that we will the create a new tree in which each node will represent a biconnected components and an edge between them will represent "cut-bridge" between the respective components. Now, you can see that it will optimal in this tree to connect the leaves in such a way that it minimizes the number of edges added. So, how to connect these leaves? After some observation you can find that connecting leaves is reducible to find the maximum matching in a complete k partite graphs, where k means here that the there are k subtrees on a particular root of the tree. There's a standard result that x1 + x2 + x3 + ... + xk - 1 ≥ xk where xi represents number of leaves in ith subtree, then matching will be (x1 + x2 + .. + xk) / 2
Thanks got it :D
For MODNIM — Trump will only lose when he gets all the heaps of size 1 and the number of heaps is divisible by 3. Obama will win only when he can convert the given heaps into this form. I will be posting the proof soon.
that facepalm moment when I got the correct solution to MODNIM fast and then waited for 1 hour before realising that I missed out on an "else" part of code :(
Can you tell the proof for MODNIM's solution ?
Here
4th :'(
Auto comment: topic has been updated by Equinox (previous revision, new revision, compare).