Hello everyone.
I would like to invite you to participate in the 8th COJ (Caribbean Online Judge) Round, this will be a contest with 5 problems, and three hours of duration. The problems will have Div2-like complexity and will be in English and Spanish. The contest will have ACM-ICPC format.
You can find out more about it clicking here. You can also check out the previous rounds here.
UPD1: Time of the contest has changed because of overlapping with Euro Semifinals :). The contest will start at this time.
UPD2: The contest is about to start, get in now!!.
UPD3: The contest is over. Hope you liked the problems.
Hints:
Problem A:
The last player to play wins. Note that this last player can always get what the previous player got in the previous turn plus another positive number. Watch out with n = 1 case.
Complexity:
Problem B:
You can start from the right: i = n, decreasing k with i - 1 while k ≥ i - 1 and append to a vector the number i. Then you can append the rest of the numbers (in increasing order) to the vector.
Complexity:
Problem C:
Note that the graph is a tree with a cycle. The probability to disconnect the graph in one step is and in two steps is
. So the expected value is
. Here c is the length of the cycle. You can do a dfs to find c.
Complexity:
Problem D:
A number is hyperdrome if it has at most 1 digit with odd frequence. So build a graph where each node is a bitmask representing the parity of the digits's frequence of a number. Add edges between node x (0 ≤ x < 2b) and nodes .
Also add a node 2b that represents the empty set, and add and edge to itself, and to 21, 22, ..., 2b - 1.
Then you can exponentiate this graph to obtain the answer.
The answer will be . Where a is the adjacency matrix of the graph.
Complexity:
Problem E:
Segment Tree. In each node save the lcp of the range, and a string that is in the range. Then to combine two nodes you can do:
lcp[x] = min (lcp[2 * x], lcp[2 * x + 1], GetLCP(str[2 * x], str[2 * x + 1]))
str[x] = str[2 * x]
Where x is a node in the segment tree and GetLCP is a function that calculates the LCP for two strings. Also you should add lazy propagation to this.
Complexity:
Thanks for posting! Those were fun problems. Any idea when an editorial or solutions will be posted?
Glad you liked the problems. In a bit I will post the ideas of the problems in this post.
Thanks for the notes! I had the right algorithm for C but still got WA on test 2, do you have any hints?
Nice contest dcordb. In the contest I found problem D harder than E, I'll be looking forward to do other contest from you.
Thanks. I have planned to make another one in September.
Can you please explain D with more details.
I have updated the hints from D.
Can you be more specific,What these edges are representing and what is purpose behind adding them.
Let's say b = 4 and you are on node 1101, this node represents all the numbers that have:
Now you can add digit 0, 1, 2 or 3 to the number, this are the edges.
So if you add 0 you go to 1100 (because 0 had odd frequence and you add a new 0), if you add 1 you go to 1111, and so on.
Hope that makes it clear.
Thanks a lot!I got it now.I had never seen this kind of trick before.Are there problems which can be solved by similar methods?(sorry if I am asking too many questions)
The problems are from easy to hard:
COJ 3670
COJ 3107
COJ 3264
COJ 3548