COJ Round Contest #8 + Editorial

Revision en8, by dcordb, 2016-07-08 01:23:01

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 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.

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:

Tags coj, round, caribbean, contest

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English dcordb 2016-07-08 19:56:11 143
en8 English dcordb 2016-07-08 01:23:01 23 Tiny change: 'n node $x (0 \leq x' -
en7 English dcordb 2016-07-07 22:38:32 232
en6 English dcordb 2016-07-07 22:30:35 12
en5 English dcordb 2016-07-07 22:27:44 1624
en4 English dcordb 2016-07-07 19:48:04 63
en3 English dcordb 2016-07-07 16:03:23 115
en2 English dcordb 2016-07-06 06:28:16 374
en1 English dcordb 2016-07-05 05:05:05 652 Initial revision (published)