### chrome's blog

By chrome, 4 years ago, translation, ,

Privet, everyone!

Tomorrow at 14:00 MSK will be held Topcoder SRM 653.

Let's discuss problems after contest.

•
• +64
•

 » 4 years ago, # | ← Rev. 2 →   +8 without you chrome I would miss participating all the SRMs, thanks :D
 » 4 years ago, # |   +18 Would it be rated ? :P
•  » » 4 years ago, # ^ |   0 Till the start of contest we have to expect that.
 » 4 years ago, # |   0 450-Div1 seems to be similar to SPOJ_MOBIVINA
 » 4 years ago, # |   +18 I'm wondering if there's a test case for 250 d1 in which the number of possible layouts is equal to 1 modulo 2^32, but not equal to 1. If there is, then many contestants will fail because of overflow :)
•  » » 4 years ago, # ^ |   0 Tried to create such case during intermission but couldn't. Hoping problem setter was devilish enough to come up with one :)
•  » » 4 years ago, # ^ |   0 And even more would fail if there is same for modulo 2^64
•  » » 4 years ago, # ^ |   0 Looking at final standings — there are no such tests; however, still curious about existence of such test for given constants:)
•  » » 4 years ago, # ^ |   +64 Here's one such test: 0,0,2,0,1,0,3,0,0,0, 2,0,0,1,0,3,0,0,0,2, 0,0,1,0,0,0,3,3,0,0, 0,1,0,0,0,3,3,0,0,0, 1,0,0,0,0,4,0,0,2,0, 0,0,0,4,4,0,0,0,1,3, 0,0,0,0,0,3,0,0,0,0, 0,6,0,0,6,0,0,0,0,1, 3,0,0,0,0,0,3,0,0,0, 0,0,6,0,0,6,0,0,0,0 The answer is 152·232 + 1.
•  » » » 4 years ago, # ^ |   0 How do you find it?
•  » » » » 4 years ago, # ^ |   +3 If we have configurations with answers a and b, we can obtain a configuration with answer ab: concatenate them separated by a single 1. I looked for numbers k·232 + 1 with small numbers in factorization, and constructed random configurations until all prime divisors could be obtained.
•  » » » » » 4 years ago, # ^ |   0 Similar problem was in the first Russian Code Cup)
•  » » » » » 4 years ago, # ^ |   0 Nice!A pity such a test didn't appear in the final test set though. Fine, we'll have to do better at the challenge phase next time ;) .
•  » » » » » 4 years ago, # ^ |   +5 Kudos! Is there anything with k*2^64+1 within given constraints? (i.e, N = 100)
•  » » 4 years ago, # ^ |   +45 Turns out there's a much simpler test, which is: (33 times 0), (2 times 33), (33 times 0).There's exactly one way to put the 33's in different groups, and 32 ways to put them in the same group, each one yielding 233 ways to deal with the remaining zeros, so the answer will be 1 + 238.Answering to ainu7's question below: there is a similar test of size 130 (and it can be even optimized to 128) that causes 264 modulo solutions to fail. While this construction is good, it's not clear whether this is the shortest test with such property.
 » 4 years ago, # |   0 How to solve Div2 1000?
 » 4 years ago, # |   +8 How to solve 450 and 900 ? Thanks.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 450 hint: min cut900 hint: look at matrix with 0, 1, 2 as rows (Bob's) and R, P, S as columns (Alice's) and what happens if 0 was Rock, 1 was Paper, but now 0 is Paper and 1 is Rock
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 450 is mincut (which is equal to maxflow, as you need only value of cut, not cut itself).For every value X, add edge with capacity 0 from S to X, if X can be assigned to Bob, or edge with capacity INF, if it can't.For every value X, add edge with capacity 0 frot X to T, if X can be assigned to Alice, or edge with capacity INF, if it can't.For every pair of values X, Y, add edge between X and Y with capacity C, where C is penalty for assigning X and Y to different players.Now you need to find mincut between S and T in given graph. You'll assign all vertices in same component with S to Alice, and all other vertices to Bob.P.S. I can't understand why they gave this problem, it is pretty standard task, reduction to maxflow is well-known, and lot of users are using prewritten implementation of maxflow, therefore main part of solution can be done with copy-paste very fast.
•  » » » 4 years ago, # ^ |   0 Got it , thanks. Pretty simple , should have spent more time on it.
•  » » » 4 years ago, # ^ |   +8 Also zero capacity edges are not needed, obviously
•  » » 4 years ago, # ^ |   +19 You can see the editorial for div1 900 here. (spoiler alert!)Please tell if something is unclear. :)
 » 4 years ago, # | ← Rev. 2 →   0 How to solve div2 1000? UPD: Ignore it... I forced my lazy brain to understand from someone's code and I did.
•  » » 4 years ago, # ^ |   +3 I use DP like this.Let dp[i][j][k] be the minimum difficulty of the first i pitch, where pitch from i — j + 1 to i are given to Alice if k = 0, to Bob if k = 1.Then with dp[i][j][k] we can update to dp[i + 1][j + 1][k] and dp[i + 1][1][1 — k].The answer is min(dp[n][j][0], dp[n][j][1])
 » 4 years ago, # |   0 As I_love_Tanya_Romanova said, there were no tests such that number of ways to obtain a correct division was 1 mod 232, but even though many contestants failed 250 problem (about a half in my room for example). Did anyone investigated the reason? Were there some other tricky testcases or a deceptively looking "solution"?