Privet, everyone!

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

Let's discuss problems after contest.

Before contest

Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined)

12:14:52

Register now »

Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined)

12:14:52

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3496 |

2 | Um_nik | 3309 |

3 | Petr | 3298 |

4 | dotorya | 3225 |

5 | W4yneb0t | 3218 |

6 | OO0OOO00O0OOO0O0…O | 3199 |

7 | Radewoosh | 3150 |

8 | izrak | 3109 |

9 | anta | 3106 |

10 | Syloviaely | 3073 |

# | User | Contrib. |
---|---|---|

1 | tourist | 186 |

2 | rng_58 | 175 |

3 | csacademy | 167 |

4 | Petr | 160 |

5 | Swistakk | 156 |

6 | Errichto | 150 |

7 | lewin | 149 |

8 | Zlobober | 144 |

9 | matthew99 | 141 |

9 | adamant | 141 |

Privet, everyone!

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

Let's discuss problems after contest.

↑

↓

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/20/2018 06:20:09 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|

without you chrome I would miss participating all the SRMs, thanks :D

Would it be rated ? :P

Till the start of contest we have to expect that.

450-Div1 seems to be similar to SPOJ_MOBIVINA

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 :)

Tried to create such case during intermission but couldn't. Hoping problem setter was devilish enough to come up with one :)

And even more would fail if there is same for modulo 2^64

Looking at final standings — there are no such tests; however, still curious about existence of such test for given constants:)

Here's one such test:

The answer is 152·2

^{32}+ 1.How do you find it?

If we have configurations with answers

aandb, we can obtain a configuration with answerab: concatenate them separated by a single 1. I looked for numbersk·2^{32}+ 1 with small numbers in factorization, and constructed random configurations until all prime divisors could be obtained.Similar problem was in the first Russian Code Cup)

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 ;) .

Kudos! Is there anything with k*2^64+1 within given constraints? (i.e, N = 100)

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 2

^{33}ways to deal with the remaining zeros, so the answer will be 1 + 2^{38}.Answering to ainu7's question below: there is a similar test of size

130(and it can be even optimized to 128) that causes 2^{64}modulo solutions to fail. While this construction is good, it's not clear whether this is the shortest test with such property.How to solve Div2 1000?

How to solve 450 and 900 ? Thanks.

450 hint: min cut

900 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

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.Got it , thanks. Pretty simple , should have spent more time on it.

Also zero capacity edges are not needed, obviously

You can see the editorial for div1 900 here. (spoiler alert!)

Please tell if something is unclear. :)

How to solve div2 1000? UPD: Ignore it... I forced my lazy brain to understand from someone's code and I did.

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])

As I_love_Tanya_Romanova said, there were no tests such that number of ways to obtain a correct division was 1 mod 2

^{32}, 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"?