### cgy4ever's blog

By cgy4ever, history, 6 years ago,

Topcoder SRM 705

• +67

| Write comment?
 » 6 years ago, # |   0 Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).
 » 6 years ago, # |   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
•  » » 6 years ago, # ^ |   0 Hope to some really creative problems, like all other problems that you set! :)
 » 6 years ago, # | ← 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.
•  » » 6 years ago, # ^ |   0 Update: Contest will start in 2 hours.
 » 6 years ago, # |   0 Are there any ideas for Div.1 medium?
•  » » 6 years ago, # ^ |   +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[].
•  » » » 6 years ago, # ^ |   +5 But, how to prove it's correct?
•  » » » » 6 years ago, # ^ |   +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.
•  » » » » » 6 years ago, # ^ | ← 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)?
•  » » 6 years ago, # ^ | ← 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.
•  » » » 6 years ago, # ^ | ← 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.
•  » » » » 6 years ago, # ^ |   +10 Yes, you are right. Now I understand why my solution fails.
 » 6 years ago, # |   -11 Pretests today are too weak. Why don't TopCoder add some big random test cases as usual?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 TopCoder has pretests? I didn't know,i thought there are only examples,there are always a lot of hacks.
 » 6 years ago, # |   +10 What's the intended complexity of the hard? I think I had n/2 * 2^(n/2), but it timed out.
•  » » 6 years ago, # ^ |   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.
•  » » » 6 years ago, # ^ |   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.
 » 6 years ago, # |   +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.
 » 6 years ago, # |   +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
 » 6 years ago, # |   +15 Div 1 Medium of this contest is almost the same as problem TAP2016E on SPOJ.
•  » » 6 years ago, # ^ |   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.
•  » » » 6 years ago, # ^ | ← 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.
 » 6 years ago, # |   0 can someone give me a hint for div 2 hard? thanks
•  » » 6 years ago, # ^ |   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.
 » 6 years ago, # |   0 Can I get some help with Div 2 medium? Any pointers or reference to core algorithm?
•  » » 6 years ago, # ^ |   +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
 » 6 years ago, # |   0 How to solve Div1 Hard?
•  » » 6 years ago, # ^ |   0 From above comments, it seems to be meet in the middle.
•  » » 6 years ago, # ^ |   +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
 » 6 years ago, # | ← 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.