Всем привет!
Завтра в 18:00 MSK состоится Topcoder SRM 688.
Предлагаю обсудить задачи здесь после контеста!
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
5 дней
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
5 дней
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.11.2024 09:14:02 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Is topcoder working currently? I can't connect either through application or web. Connection timed out
For me, the Java arena managed to start, just very slowly (after a few minutes).
My arena is not working at all. And "ping topcoder.com" doesn't respond.
I am having the same result. Hope the coding time will be extended.
I'm still waiting for arena to start too.
How to access problems in the web arena? I can't seem to find them.
Will that be unrated? I turned on my arena at 16:58 at it loaded at 17:18 :P. Nevertheless I decided to take part, because I'm not solving contests mainly for rating, but for fun.
Yes, I spend 10 minutes to open arena too, and i can't submit second problem;(
My short story of today's SRM:
1. I tried to open Arena at 16:58 (SRM was starting at 17:00 in my timezone), but it was loading forever. At 17:10 I lost my hope and stopped waiting and watching CF if that is not only mine issue (from comments here I concluded that others also experience this). No wonder it influenced my mood in a very negative way.
2. Very surprisingly at ~17:20 it finally loaded. I thought that everyone had the same issue as me, but there were already many submissions on the leaderboard, so I felt that it was really unfair. But as I was already in a bad mood I thought "OK, ^&*# the rating I will compete either way. I will try to perform well, but that will ont be easy"
3. After ~10 minutes I wasn't able to figure out 250 problem, so I thought "OK, now I don't care even about place, so let's check if hard problem is fun"
4. I got some not very clever observations in hard problem and my intuition told me that a stupid approach which is on my mind may be ok. It seemed to be waaay too easy to be a good solution to hard, but as I already said I wasn't in a mood for solving problems, so I was too lazy to think about any proof/counterexample/different approach, so I started coding.
5. After some debugging it passed samples. Lol. Submitted it expecting miserable fail on systests.
6. It passed systests and I'm 9th XDDDDD. In the beginning of the contest I already accepted fact that I will got like -150 to my rating and didn't try hard to change that, but in the end I got +84 xD.
In my opinion problems should be cyclically shifted one place to right preserving their original point values :P.
How to solve Hard? :D
cgy4ever told me the intended solution for Hard and it was a very nice solution with flow. (This is a very big hint, but I still couldn't solve it with this hint — can you solve?)
I greedily constructed those strings keeping their 'heights' difference as small as possible. After considering some prefix of s, first constructed string always have exactly the same number of nonclosed brackets as second one or exactly one more. In the end compute their summed cost :P. As I looked, Petr's submission follows exactly the same idea.
My code is here: http://ideone.com/JgVmI7
Observations which I made during the contest were:
1. Those strings can be constructed iff s is a correct bracket sequence
2. If I'm not mistaken (I may be) consider two strings A and B so that their "heights" (number of nonclosed brackets) are the same. Then (cost(AC) — cost(BC)) is fixed for all valid Cs. That implies that if we are in the middle of constructing process, only thing that matter for future decisions is the height. That statement is either very easy to prove or obviously false, but as I have already said few times I was too lazy to check and still I am
3. Since x^2 is an increasing function, it is better to make those strings relatively flat, so better keep their heights as close as possible to each other.
EDIT: Statement 2. is in fact obviously false. A="(()", B="(", C1=")", C2="())". However I don't know now how does that affect dubious correctness of my solution.
Well I tried the same solution with one little difference. I also always put +1 to the smallest and -1 to the biggest, but I don't fix which one of two strings will be the largest (case of equal heights). And without it the solution doesn't pass systests (in my code it's a change of "<" to "<=" in closing bracket case).
It's interesting whether this solution actually works at stress.
I remember Petr on his blog wrote that it works to all strings up to some length (something like 16 or 18). I believe it is a correct algorithm, but I expect proof to be noninteresting ifology (but still requiring some nontrivial idea), so I didn't think hard about it.
My solution is DP which will work for any cost function. The idea is following: notice that there exists a solution where every pair of matching open and close brackets belongs to the same subsequence. So we can build a tree of pairs of brackets (we'll add a dummy node and make it a parent of all bracket pairs without parents) and the goal is to distribute its nodes into two trees so that overall cost is minimized. Let f(v, d1, d2) be the optimal cost of splitting a subtree of node v into two trees so that depth of the first tree is d1 and depth of the second one is d2, node v is considered unassigned (i.e. we'll assign it to one of the to trees later). Then, we can iterate over child nodes and make a DP transition for each of them (when we assign a child node to one of the two subtrees, the depth will change by 1, overall depth will be max(current_depth, this_child_depth)). Overall complexity is O(N^4).
I had a similar idea, but got stuck, because initial sequence not necessary a correct bracket sequence. Did you add some artificial brackets to deal with that?
If it's not a correct bracket sequence, the answer is -1.
Have you proved that "there exists a solution where every pair of matching open and close brackets belongs to the same subsequence"? Is there some simple proof?
I have passed in practice room with the following greedy solution (which seems to work only for cost functions growing faster than linear):
Answer is not -1 iff initial sequence is a valid parentheses sequence
If the sequence is valid there is corresponding forest (And depth of the sequence is exactly the height of the forest).
"there exists a solution where every pair of matching open and close brackets belongs to the same subsequence" => there exists solution where the relation of being nested over parentheses is preserved => there exists solution where the relation of being successor over vertices in the forest is preserved
Since function grow is faster than linear it is optimal to just colour every tree into 2 colours. (The parentheses corresponding to each colour form the sequence)
Complexity is linear. But I have to admit there are some gaps in the proof.
Code http://ideone.com/uCzy9E
Up until point 4. my situation was exactly the same. The difference was that I didn't finish debugging Hard in time and I'm at 0 points and (I don't want to see the rating change).
Was that experience with web or java applet arena?
Java applet arena.
how to solve Div1 250 ??
Preprocess the string, for any index i, try to delete as much as possible valid parenthesis starting from i. The preprocess will take O(n^2), after that the string can be 3 formats: "))..))", "(((...(((" and ")))..(((". In each case it is easy to find a way to make it valid.
The operation given is equivalent to take the mirror image of the segment.
Use a stack insert everything that is unbalanced into stack , even ')' brackets.
At the end, the state of the stack will be something like :
)))))(((((((
If the stack size if odd return -1.
Note : The ')' sequence or '(' can be empty too . Also the balanced parenthesis keep balanced even after the operation.
Now to balance try taking mirror image of at most STACK_SIZE/2 using one operation and another operation to turn other half to make the state of stack as STACK_SIZE/2 '(' and STACK_SIZE/2 ')'.
(Sometimes you do not need to take mirror image of some elements)
Complexity : O(N)
Replace '(' with +1, and ')' with -1. Compute prefix sums. Observe that correct bracket sequence is equivalent to sum[i] ≥ 0 for all i and sum[n - 1] = 0.
Find the smallest prefix sum — say sum[k]. If sum[k] < 0 then apply our move on that prefix. Observe that the first property (sum[i] ≥ 0 for all i) is now satisfied (why?)
Now if sum[n - 1] = 0 then we are done. Otherwise sum[n - 1] = 2·h > 0 (because n is even), now just find last index l with sum[l] = h and apply our move on suffix [l, n - 1].
Wow, cool. I thought it's gonna be something like O(logN) moves.
Technically you're right, 2 is definitely O(logN) :P
Actually this is very similar to my approach but somehow I managed to not to keep balance sum (I do not need crossing Operation too). Solution
Don't you think, it should be [l + 1, n — 1]?
Any corner cases can you think of? I had same approach but I got hacked :(
No stk[i] is the position of the unbalanced parenthesis in the original string We have to balance. You will reverse from this position to the last.
Though I don't have your code but I think your mistake is quite trivial you will eventually have a facepalm moment.
Where can one view problem submission challenge data ?
Any hints for Div 2 Hard?
Could someone tell me How the algorithm in Div-2 500 ptr will always output less than or equal to (lenth_of_string/2 + 1) flips ? A formal proof of some sort. My idea was to keep a variable balance which stores difference b/w '(' and ')' seen up till a certain point. Balance is incremented when '(' and decremented when ')'.
if bal<0 ---> index is pushed and , bal += 2
if bal>1 ----> index is pushed and bal -= 2
This failed the system tests since it outputted more than (length/2 + 1) flips. Could someone tell me why my idea wouldn't work. Thanks.
When i found my self stuck and can not get a proof fast, i assumed there will always be a way to do so ( the statement said that ) so i coded a dynamic programming solution which gets the min number of flips needed, then 1 more function which trace my DP table and gets the path that the DP follows ( the indices that should be flipped ). and passed the system test.
this is my solution.
Thanks.
I wrote a greedy algorithm with time complexity O(n) where n is length of input string. It passed system tests.
Here is my solution.
how to solve div2 500?
What you need to flip are ')' that don't match to their left, and '(' that don't match to their right. But remember if you have 2 ')' that don't match, and you flip the one that appears first, you'll have these 2 symbols matched: )) -> () The same with '('s. So you just perform a check:
finally you'll get a stack with '('s, flip half of them you'll get a valid sequence.
for div1 hard, i got an idea like this: Let dp[i][cnt1][cnt2] be the minimum cost starting at position i, and to its left there were cnt1 opening '(' in sequence 1 and cnt2 opening '(' in sequence 2, what's the minimum cost. The transition:
and when "i" becomes s.size(), and cnt1 = cnt2 = 0, return 0, or else it is an invalid solution. I think this works because I just put each symbol into sequence1 or sequence2, but actually it won't even pass the samples. And I just can't figure out why, could someone kindly help me with the problem of this idea ?
Another idea I also tried is that, I maintain 2 stacks, and opening '('s are put into them, and I'll try to make the length of these 2 stacks as close as possible, that is, whenever a '(' comes, I push it into the stacks with less '(', and whenever a ')' comes, I match it with the sequence with less length. However, this idea is also wrong and has the answer as the previous one.
I know where my problem lies... depth(AB) = max(depth(A), depth(B)) cost(AB) = cost(A) + cost(B)
I wrote a simple O(n) greedy in Div.1 Hard and to my surprise it passed system test.
I just build the forest using the parentheses sequence, and I divided the tree into two parts: the nodes with a odd depth and the nodes with a even depth. Then I calculate the cost of the two parts.
It seems that it's correct but I can't come up with a strict proof...
Thanks! This is an interesting idea. I think it's quite similar with the idea that maintains 2 stacks. It seems somewhat obvious to do so but I can't neither show that's mathematically correct :-(
Any ideas on Div 2 Hard
How to solve DIV 2 1000 ??? I need an explanation