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!
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!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 160 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Auto comment: topic has been updated by tweety (previous revision, new revision, compare).
How to solve task Torrent?
unsolvable
And I think that's the easiest one among them :D
OK what is it?
Task Torrent of course , which is "unsolvable" :D
I mean what's the main idea behind the solution?
I don't know for sure.
It would be have been cool if there was a counter for how many times the results page was refreshed :P
Results are out!
Apparently no one got RELAY right.
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
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/
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.
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
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.
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/
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/