### decoder123's blog

By decoder123, 4 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

 » 4 years ago, # | ← Rev. 2 →   +26 Did you mean tomorrow? Now fixed, thanks!
 » 4 years ago, # |   +20 Starting in about 30 minutes.
 » 4 years ago, # |   +28 Looks like chrome quitted when he got what he wanted (top 10 contributors) ;)
 » 4 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?
•  » » 4 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).
•  » » » 3 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.
•  » » 4 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.
•  » » » 4 years ago, # ^ |   0 Opps. Thank you!
 » 4 years ago, # |   +13 How to solve Div1-900? I saw people used MaxFlow, but didn't figure out how.
•  » » 4 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).
 » 4 years ago, # |   +13 Can someone please shortly describe the solutions for first two Div. 1 problems? Failed both of them on systests :)
•  » » 4 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).
•  » » » 4 years ago, # ^ |   +8 Could you please elaborate on the well known algorithm for the 500? Where does one learn such algorithm?
•  » » » » 4 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.
•  » » » » » 4 years ago, # ^ |   0 Looks like your solution is harder than mine.Let's fix two strings. They make some masks bad. All such masks are submask of mask constisting of all positions where these two strings have equal chars. We can find such bad supermasks for all pairs of strings in O(n2m). Now we should mark all the submasks of bad supermasks. It can be easily done in O(m2m).
•  » » » » » » 4 years ago, # ^ |   +20 I was asked to describe in detail, and described in detail/formally/generally, the part Now we should mark all the submasks of bad supermasks. which I initially described as a well-known algorithm for computing something for supersets (or subsets) Our solutions are the same.
•  » » » » » » » 4 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; } 
 » 4 years ago, # | ← Rev. 3 →   +5 I noticed that many codes for 250 are incredibly similar. I mean that the algorithm is absolutely identical, most differences are variable names (the rest: order of two conditions, initialisation to 0 or -inf, omitting a redundant bitmask, making N global — all trivialities). This... can't be even cheating, it's too obvious. Could so many people be learning it by heart from the same resource?Has cloning advanced so much?
•  » » 4 years ago, # ^ |   +10 Maybe they googled the same solution to some similar problem.
•  » » » 4 years ago, # ^ |   0 It's all reds / high yellows.
•  » » 4 years ago, # ^ |   +8 The problem is too simple to have different approaches, isn't it?
•  » » » 4 years ago, # ^ |   +6 The simplicity necessary for this to be a coincidence is at the level of div2 50pt. Something like "add N numbers". The differences are cosmetic, most of them are just variable names. I initially thought I opened the same person's code several times in a row by mistake.My code looks completely different and uses a somewhat different way to count the same thing (no recursion, two less array dimensions). There are other codes somewhat similar to mine, although none as similar as this. There are a few outliers which look very similar to the template I'm talking about when I look better at what they're doing, but not first-glance identical, for example by using a loop instead of backtracking.It looks really weird.
 » 4 years ago, # |   +10 How to solve div2 1000?
•  » » 4 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
•  » » » 4 years ago, # ^ |   0 Nice solution, thanks :D
•  » » » 4 years ago, # ^ |   +10 Thank you! :)
 » 4 years ago, # |   0 Why there are so strange limitations in 250div1? I was sure that O(nC3) will pass but wrote O(nC2) . I think that O(nC2) solution is nice but the problem is really bad because stupid solution passes.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 My O(nC2) solution with memoization got TLE on one of the sample test cases; therefore, I had to rewrite it in a bottom-up approach. I was very surprised when I saw O(nC3) solutions could pass. Maybe this is the reason why they wanted to extend the time limit a bit (which ultimately caused asymptotically slow solutions to pass).