Блог пользователя tweety

Croatian Olympiad in Informatics 2016
Автор tweety, история, 9 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +38
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

How to solve task Torrent?

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Results are out!

Apparently no one got RELAY right.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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/

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

      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.

      → Ответить
»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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/

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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/

→ Ответить