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

Автор cgy4ever, история, 17 месяцев назад, ,

Topcoder SRM 705

•
• +67
•

 » 17 месяцев назад, # |   0 Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).
 » 17 месяцев назад, # |   0 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
•  » » 17 месяцев назад, # ^ |   0 Hope to some really creative problems, like all other problems that you set! :)
 » 17 месяцев назад, # | ← Rev. 2 →   +36 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.
•  » » 16 месяцев назад, # ^ |   0 Update: Contest will start in 2 hours.
 » 16 месяцев назад, # |   0 Are there any ideas for Div.1 medium?
•  » » 16 месяцев назад, # ^ |   +55 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[].
•  » » » 16 месяцев назад, # ^ |   +5 But, how to prove it's correct?
•  » » » » 16 месяцев назад, # ^ |   +51 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.
•  » » » » » 16 месяцев назад, # ^ | ← Rev. 2 →   0 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)?
•  » » 16 месяцев назад, # ^ | ← Rev. 2 →   -10 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.
•  » » » 16 месяцев назад, # ^ | ← Rev. 3 →   +40 Are you sure it is equivalency relation?Take an example with 3 bins and 2 rules: 0 0 2 0 2 2 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.
•  » » » » 16 месяцев назад, # ^ |   +10 Yes, you are right. Now I understand why my solution fails.
 » 16 месяцев назад, # |   -11 Pretests today are too weak. Why don't TopCoder add some big random test cases as usual?
•  » » 16 месяцев назад, # ^ | ← Rev. 2 →   +5 TopCoder has pretests? I didn't know,i thought there are only examples,there are always a lot of hacks.
 » 16 месяцев назад, # |   +10 What's the intended complexity of the hard? I think I had n/2 * 2^(n/2), but it timed out.
•  » » 16 месяцев назад, # ^ |   0 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.
•  » » » 16 месяцев назад, # ^ |   0 Btw, TL looks more tight 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.
 » 16 месяцев назад, # |   +39 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.
 » 16 месяцев назад, # |   +38 My code for Div1 Hard is O(max(2^S*n,2^(n-S)))I set S=28,And then I failed system testAfter contest I set S=27 and I have accepted itGood Game
 » 16 месяцев назад, # |   +15 Div 1 Medium of this contest is almost the same as problem TAP2016E on SPOJ.
•  » » 16 месяцев назад, # ^ |   0 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.
•  » » » 16 месяцев назад, # ^ | ← Rev. 4 →   +35 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.
 » 16 месяцев назад, # |   0 can someone give me a hint for div 2 hard? thanks
•  » » 16 месяцев назад, # ^ |   0 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.
 » 16 месяцев назад, # |   0 Can I get some help with Div 2 medium? Any pointers or reference to core algorithm?
•  » » 16 месяцев назад, # ^ |   +10 you form a graph with the characters in each word then the answer is possible if and only if the graph has no cycles
•  » » » 16 месяцев назад, # ^ |   0 Thanks, I missed that intuition.
 » 16 месяцев назад, # |   0 How to solve Div1 Hard?
•  » » 16 месяцев назад, # ^ |   0 From above comments, it seems to be meet in the middle.
•  » » 16 месяцев назад, # ^ |   +8 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
 » 16 месяцев назад, # | ← Rev. 2 →   0 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.