Round starts in 10 minutes.

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

1 | Benq | 3796 |

2 | tourist | 3722 |

3 | Radewoosh | 3719 |

4 | ecnerwala | 3578 |

5 | ksun48 | 3462 |

6 | Um_nik | 3456 |

7 | maroonrk | 3445 |

8 | jiangly | 3431 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

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

1 | 1-gon | 207 |

2 | awoo | 186 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 177 |

5 | Radewoosh | 177 |

7 | -is-this-fft- | 176 |

7 | maroonrk | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

Round starts in 10 minutes.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/15/2021 09:19:24 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

What was the problem with DIV1 Medium? I couldn't get a solution but so many people failed the system tests or were hacked (I guess their codes TLE'd)

I guess their solutions used wrong assumptions, which leads to wrong solutions, which can be easily challenged with big random tests.

It's not that surprising — the first thing to expect is a greedy strategy, and many such strategies can be invented, but it doesn't actually work.

Firstly, only relative positions of corresponding rings of the lock matter, so you can replace pairs of (original,target) positions by just their differences

D_{0}[i]. You can add a correctly placed ring to the left of the lock and transform the sequence of differences to a new one:D[i] =D_{0}[i] -D_{0}[i- 1] (mod 10). In this case, an operation is just adding 1 toD[i] and subtracting 1 fromD[j] for any pair (i,j), or just adding/subtracting 1 fromD[i] (that corresponds to rotating several rings at the right side of the lock).We want to convert the array

Dto all zeroes using a sequence of operations; the order of operations doesn't matter. If we'd add 1 toD[i] and subtract 1 fromD[k] (or from noD[k]), and at some other time subtract 1 fromD[i] and add 1 toD[j] (or to noD[j]), it can be replaced by one operation, for example (D[j],D[k]). That means we only rotate each ring in 1 direction.Let's sum up

D[i] of rings which are rotated up, and sum up 10 -D[i] of those rotated down; denote them asxandy. The answer is obviously , andx-yis constant (), so if we could find all possiblex, we could obtain the result quite easily. Andx< 10N, so it's now clear that a DP works. Letdp[i][j] be > 0 ifjis a subset sum from the firstientries of arrayD, 0 otherwise;dp[i+ 1][j+D[i]] =dp[i][j+D[i]] +dp[i][j].The time required for this is

O(10N^{2}); it can be cut down by half if we're not interested inj+D[i] forj> 5N(because then we just havey>x, and we don't want even largery); it can also be cut down on memory toO(10N) if we only remember the last 2 rows of the array. I haven't coded it during the contest, but it should pass.The actual input of the first problem is one string , making the input is two vectors of strings was very confusing!!! I wasted time until I realized that this has nothing to do with the solution.

That's normal on topcoder, they can't make the input string too big because challenges are not like codeforces where you can upload a generator or something

Oh thanks for information! I'm new on topcoder.

Yeah, it usually is confusing for the first time. When I did my first div1 contest on TC, the 250pt problem was also partly about parsing strings (but even worse than this time), and it left me really annoyed that "the problems are not about algorithms, but string parsing". I only found out later that such formats of input are not so common.

I think I was lucky coz I took few times to make a large input and then hacked 3/4 TLE codes :p. It was an awesome feelings because TLE hacks are hard to get :p.