### decoder123's blog

By decoder123, 6 years ago,

Tomorrow at 19:00 MSK will be held Topcoder SRM 694.

Let's discuss problems after contest!

Thanks to dened for pointing out the mistake.

• +67

 » 6 years ago, # | ← Rev. 2 →   +26 Did you mean tomorrow? Now fixed, thanks!
 » 6 years ago, # |   +20 Starting in about 30 minutes.
 » 6 years ago, # |   +28 Looks like chrome quitted when he got what he wanted (top 10 contributors) ;)
 » 6 years ago, # |   +13 What is wrong with the Meet-In-The-Middle approach in 500? i tried it but got WA on example 4(my code returns 940008).Also i have seen some coders in 250 were not care about condition "groups should't be empty". Is there countertest?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +33 If some group is empty — you can move any element from other group to this one and it will not decrease your score (because a^b<=a+b).
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -8 Could you please elaborate? It will certainly not decrease the score but it might increase it. I'm definitely missing something here.
•  » » 6 years ago, # ^ |   +10 How can you meet in the middle? I guess on masks? Mask halves are not independent, e.g. 10|00 and 00|10 may be bad masks, but 10|10 is good.
•  » » » 6 years ago, # ^ |   0 Opps. Thank you!
 » 6 years ago, # |   +13 How to solve Div1-900? I saw people used MaxFlow, but didn't figure out how.
•  » » 6 years ago, # ^ |   +26 Move from A[i] to A[i+1]-A[i]; there's flow V[i] from L[i] to R[i]+1. The condition for equality of all elements is now a flow condition (what flows in flows out).
 » 6 years ago, # |   +13 Can someone please shortly describe the solutions for first two Div. 1 problems? Failed both of them on systests :)
•  » » 6 years ago, # ^ |   +10 250 hint: achievable xors are small (up to 256).500 uses a well-known algorithm for computing something for supersets (or subsets) if we know it for given sets, in O(N·2N).
•  » » » 6 years ago, # ^ |   +8 Could you please elaborate on the well known algorithm for the 500? Where does one learn such algorithm?
•  » » » » 6 years ago, # ^ |   +20 Idk, I figured it out myself.You start with something for each set of numbers from 1..n. You want the sums over all supersets of each set s, so you compute the sums over all sets s' where if x ≤ k and otherwise. For k = n, it corresponds to what you started with; for k = 0, it's what you want; for k < n, it can be computed using at most 2 values for k + 1. Think how.
•  » » » » » » » 6 years ago, # ^ |   -12 No way. Your approach is hard-to-come-up-with dp, mine is something like DFS or even easier. for (int mask = (1 << m) - 1; mask > 0; mask--) { if (!bad[mask]) continue; for (int k = 0; k < m; k++) if ((mask >> k) & 1) bad[mask ^ (1 << k)] = 1; } 
•  » » 6 years ago, # ^ | ← Rev. 4 →   +9 This was my second TC contest.My solution failed in system test for case n=1. The problem can be solved using dynamic programming. for(int i=0;i