| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
Hi there,
Topcoder SRM 698 will start in about 9 hours (Sept 17, 12:00 noon EDT).
This round is Sponsored by Google, find more details here.
Thanks for participating! The Div1-Medium and Hard were prepared to be used in TCO Round 3B, but shangjingbo told me they are too easy (he got the idea for each of them in 10 minutes). It turns out they are not that easy. :P
Let me be the first one. How to solve Div1 Hard?
spoiler
let's spoil it :)
I still don't follow. Can you explain further?
I think there is one detail not obvious at first: 2-SAT solution may choose, for example, pieces like this:
which is not a good shape, so one might think this solution is not really correct, but actually it doesn't matter because in every such case the resulting "bad" shape contains a good sub-shape, so if there is a solution with some "bad" shapes, then there is also a solution where all shapes are good.
Thanks, that's the part I hadn't understood.
Anyone please explain the approach of Div2 hard...
Let's the solve task indepently for all the bits. The answer will be
(2^0 * <number of subtrees that has at least one 1st bit>) + (2^1 * <number of subtrees that has at least one 2nd bit>) + ...So, we can reduce our task. Now, we must solve the following task: the vertexes of the tree are marked with "0" or "1" and we must count number of subtrees that has "1". How can we solve it? We can calculate the number of subtrees that has only "0" and subtract it from total number of subtrees.
So, let's calculate the total number of subtrees. Use
dp[i]that means the numbers of subtrees with rooti. The answer will bedp[0] + ... + dp[n-1]. How to calc it:And how to count the number of subtrees that has only "0"? We can just remove all the "1" vertexes and get some trees. Then, count the total number of the subtrees for all of them and add them.
Really elegant and clever, Thanks ! :)
We can solve the problem for each bit, and then sum them up. For each bit, it becomes: compute the number of subtrees such that at least one node has weight 1. It equals to: (number of all subtree) — (number of subtree that all nodes has weight 0). Both can be solved by tree DP.
Great ! Thanks =)
Div2 Hard ?
Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).
Lol, because someone got an idea in 10 minutes for that problem you put significantly easier problem on TCO xD. And hard looks pretty unsolvable during that time (just first impression). It has some flow flavor in its looks, but dunno.
Yes, this Hard is not ideal: if you don't have a template for 2-SAT, then it will be too hard to code it in time. And it is vulnerable to bruteforce search.
Hints for Div1 500?
Good pairs = all pairs — bad pairs.
Pair is bad if at least one of sets has <3 points or if they form two legit polygons that have no intersection.
Figured out this much. Can't figure out how to find the total number of possible non-intersecting pairs of polygons. Thanks for the help though!
So now think how we can count legit nonintersecting polygonal. They can be separated by a line. It would be good to make that line unique.
Nice Contest :)
My screencast
SRM 698 Div 1 250 — link
SRM 497 Div 2 1000 — link
I haven't been able to participate in recent matches since hackerrank stopped showing SRM in it's calendar. What are other alternatives? How do you remember contests?
Visit clist.by
I cannot find the editorial.
How to solve the problem RepeatString?
Break the string in two parts(there n-1 ways to it) and find it's LCS. Answer will be 2 * maximum of all those LCS.
Complexity -> O(n^3)
Code
Is it possible to use here Minimum Edit Distance algorithm?
The description of the algorithm looks suspiciously similar to the problem description. At least the algorithm supports the same kind of operations: insertion, deletion and substitution.