dcordb's blog

COJ Round Contest #8 + Editorial
By dcordb, history, 8 years ago, In English

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:

  • Vote: I like it
  • +27
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for posting! Those were fun problems. Any idea when an editorial or solutions will be posted?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Glad you liked the problems. In a bit I will post the ideas of the problems in this post.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the notes! I had the right algorithm for C but still got WA on test 2, do you have any hints?

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest dcordb. In the contest I found problem D harder than E, I'll be looking forward to do other contest from you.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks. I have planned to make another one in September.

    → Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can you please explain D with more details.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have updated the hints from D.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Can you be more specific,What these edges are representing and what is purpose behind adding them.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Let's say b = 4 and you are on node 1101, this node represents all the numbers that have:

        • digit 0 with odd frequence
        • digit 1 with even frequence
        • digit 2 with odd frequence
        • digit 3 with odd frequence

        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.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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)

          → Reply