Topcoder SRM 705
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
32:35:54
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
32:35:54
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 08:59:07 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).
Update: we added one more SRM on Jan 11th and moved the SRM on 14th to 21st.
So we will have 3 SRMs in January! See details: 705, 706, 707
Hope to some really creative problems, like all other problems that you set! :)
This round will start in 22.5 hours, it will be sponsored by Blizzard:
Topcoder Open Sponsor, Blizzard Entertainment, is hiring Topcoder members. Join Blizzard reps on January 11, 2017 at 20:00 UTC -5 just prior to SRM 705 for a chat session in the Arena to learn more about their career opportunities. They are going to be there answering your questions and telling you all about life at Blizzard.
Update: Contest will start in 2 hours.
Are there any ideas for Div.1 medium?
Here's the idea. This problem is really tricky...
Say that positions i, j are "equivalent" if they can be collapsed to the same box under some functions. You can compute equivalence just by a dfs.
Now, let in[] denote nonempty boxes. If there are i, j such that in[i] = in[j] = 1 and i, j are equivalent, apply the sequence of moves to put i, j in the same box. If not, quit and return the number of 1's in in[].
But, how to prove it's correct?
Proof: Note that applying a move cannot increase # of boxes with a coin.
Say some boxes are nonempty. If no two nonempty boxes are equivalent, then you obviously can't do anymore. Otherwise, say i, j are equivalent.
It suffices to show that applying the sequence of moves to put i, j in the same box doesn't mess up the final answer.
To show this, say up to the point before we start merging i, j, we've done some sequence S of moves. Now, after merging i, j, apply S again. Now, note the nonempty boxes now are a subset of the nonempty boxes before merging i, j, so we're happy.
After we merge i, j, although the ans decreases, but the positions of nonempty boxes has changed.
Do you mean apply S twice will make positions of nonempty boxes stay in original place(or some positions just disappear)?
Let's compute whether we can force i-th and j-th tokens to be in the same bin (it is easy to see that this is equivalency relation). After that it is easy to calculate the answer (it is just the amount of equivalency classes). How to find all equivalent pairs of indexes:
. Also if one of our functions is f and 
then 
. It is easy to see that we can generate all equivalent pairs by bfs-ing on reverse edges in graph of pairs of tokens where there are forward edges 
.
UPD. Actually, this is not equivalence relation, see I_love_Tanya_Romanova comment below.
Are you sure it is equivalency relation?
Take an example with 3 bins and 2 rules:
We can force 0 and 1 to be in the same bin (bin 0) as well as we can force 1 and 2 to be in the same bin (bin 2) — but we can't move 0 and 2 to the same bin.
Yes, you are right. Now I understand why my solution fails.
Pretests today are too weak. Why don't TopCoder add some big random test cases as usual?
TopCoder has pretests? I didn't know,i thought there are only examples,there are always a lot of hacks.
What's the intended complexity of the hard? I think I had n/2 * 2^(n/2), but it timed out.
Usually "Unusual Time limit" means TL is just 2x ~ 3x of reference solution in Java, so details mater.
You may need to change 25 to something else to make it faster (or say, to improve it to O(2^(n/2) * sqrt(n))).
Btw, TL looks more tie than I thought, somehow solutions run in Arena are much slower than MPSQAS.
If it's true, someone should investigate it. It's a serious issue.
I think I was lucky today:
My idea for finding cycle was inefficient and thought it would fail. But some how it passed. I ran system test for about 10 times. 8-9 times, the runtime for 6th test case was around 1.99s. For rest of the cases(1-2), it failed to pass.
My code for Div1 Hard is O(max(2^S*n,2^(n-S)))
I set S=28,And then I failed system test
After contest I set S=27 and I have accepted it
Good Game
Div 1 Medium of this contest is almost the same as problem TAP2016E on SPOJ.
Hmm.. I'm not very surprise if this problem was studied by others before (even it is from a book or paper few centuries ago). What makes me surprise is that 'Nlogonia' appears in both TAP2016E and Div1-Easy.
Its certainly related to the following problem whose name I can no longer recall... say that you have N boxes and some moves, and say that after applying some sequence of moves you can get everything to one box. How long can the shortest sequence of moves doing this be? There is an upper bound of O(N3) (proven using same technique as div 1 medium) and a lower bound of O(N2) (some construction that I can't remember). But its unsolved what the actual answer is.
Its on Wikipedia, I'll link if I remember the name.
EDIT: Its called a synchronizing word.
can someone give me a hint for div 2 hard? thanks
This problem is exactly the same as computing the number of walks of length depth — 1 in a directed graph from a source vertex to a destination vertex. This can be computed efficiently using matrix multiplication.
See http://www.math.ucsd.edu/~gptesler/184a/slides/184a_ch10.3slides_14-handout.pdf for more details.
Can I get some help with Div 2 medium? Any pointers or reference to core algorithm?
you form a graph with the characters in each word then the answer is possible if and only if the graph has no cycles
How to solve Div1 Hard?
From above comments, it seems to be meet in the middle.
Let s_i be the set of lamps that button i could change,then we could do gaussian elimination on {s_i}.Let x be the number of i that s_i has a pivot after elimination.For the small x,we can decide whether to choose each s_i with brute force and time complexity is O(2x).As for the big x,there are only 50-x lamps that are not pivots and we could do something like bitmask dp and the time complexity is O(x * 2n - x).So the final complexity is min(2x, x * 2n - x),which is approximately equal to
Hahaha, what a funny concidence. Today I read problems (I didn't participate since it was 3AM in Poland) and hard turned out to be almost exactly the same as problem J from Chinese contest from Petrozavodsk Winter 2015. What is funny is that together with Marcin_smu we virtually participated in that contest like 10 hours before that SRM xD. What is more is that I also perfectly knew medium problem (it appeared for example here: http://main.edu.pl/pl/archive/ontak/2008/ktb (only Polish version and it asks whether answer==1, but that is same problem)). It looks like I missed a good chance of scoring all problems and getting second place on TC two times in a row :P.
EDIT: OK, I just read in comments, that relation in med is an equivalence relation xD. So likely it would have turned out I will encounter some troubles :D.