chrome's blog

Topcoder Single Round Match 653
By chrome, 10 years ago, translation, In English

Privet, everyone!

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

Let's discuss problems after contest.

  • Vote: I like it
  • +64
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Would it be rated ? :P

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

450-Div1 seems to be similar to SPOJ_MOBIVINA

→ Reply
»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +64 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you find it?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Similar problem was in the first Russian Code Cup)

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

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

          → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2 1000?

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve 450 and 900 ? Thanks.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it , thanks. Pretty simple , should have spent more time on it.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Also zero capacity edges are not needed, obviously

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

    Please tell if something is unclear. :)

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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"?

→ Reply