tweety's blog

Croatian Olympiad in Informatics 2016
By tweety, history, 9 years ago, In English

Quick reminder:

COI is going to take place today at 14:00 GMT/UTC

Don't forget to register from here!

Let's discuss the problems after the contest ends!

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

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

Auto comment: topic has been updated by tweety (previous revision, new revision, compare).

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

How to solve task Torrent?

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

It would be have been cool if there was a counter for how many times the results page was refreshed :P

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

Results are out!

Apparently no one got RELAY right.

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

Task: Palinilap can be solve with hash

First compute for each i longest odd and even length palindrome which middle is i. You can use Manacher but it is also possible with hash Compute number of palindromes (a,b pairs)

Second remove all a,b for each i a<=i<=b change each i to all 26 characters And compute it's longest odd and even length palindromes and add to a,b pairs.

Answer is maximum number of palindromes of each operation

Time complexity: 26*NlogN

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Task "torrent"

If there is one source, then make it the root: F(u) = answer for subtree u. Transition is simply sort the children descending F(), F(u) = max(F(v1)+1, F(v2)+2, ...).

For the first subtask, iterate the edges on the path a->b, delete that edge, then solve for the two parts. Complexity O(N * NlogN).

Binary search (or ternary search) for the split edge gives O(logN * NlogN), which solves subtask 2.

(Edit) code: http://paste.ubuntu.com/15595565/

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

    How can we ternary search here? I generated some tests and I realized that there are a lot of equal values while choosing a split edge. From all I know, we can't ternary search if there are equal values.

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

      I wrote (out of the contest, unluckily) a binary search which checks every edge and his right neighbour in the path a->b: you can handle all cases except the case in which timea = timea' and timeb = timeb' (where timea is the optimal time to fill from a his part of tree and timea' is the same thing from the next edge etc), but in both cases (if you decide to go right or left in your binary search) it gets 100 points, lol. That's strange D:

      My code: http://pastebin.com/tenyL8CR

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

      Instead of ternary search, you can find last edge such that second part gives bigger value, with binary search. Then answer is this edge or next one.

      → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Task "Palinilap"

I used polynomial hash to quickly check equality of any pair of substrings.

Compute Inc(i, j) = number of palindromes we'll get if s(i) is changed to character j. Compute Dec(i) = number of palindromes will be "destroyed" if s(i) is changed.

After binary search for each center, we got the first mismatched position L, R. Update Inc(L, s[R]) and Inc(R, s[L]), again use binary search + hash to calculate the bonus. The Dec[] array is changed in range [L+1..R-1], this is just offline range update of linear functions.

Finally answer is max(initial_palindrome_count + Inc(i, j) + Dec(i))

Time complextity: O(NlogN + N * 26)

(Edit) code: http://paste.ubuntu.com/15595576/

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

My AC solution for "Dijamant" is O(N*K*(N + K)), but I think it's hard to generate a test case where it fails.

For each node u store a set A(u) of its super classes. To check for "diamond" after adding node U, let L be the list of nodes that U inherits from, we need to test if there is any two nodes (x, y) from L, such that (neither x inherits y, nor y inherits x) and (A(x) intersects A(y)). To eliminate the first condition I filter the list L to make it contains only the deepest nodes (no other nodes in L inherits from these), this part is O(K*K). From the reduced list check set intersection in O(K * N), this can be done effectively using std::bitset<>.

Any idea for better asymptotic ?

(Edit) code: http://paste.ubuntu.com/15595579/

→ Reply