cgy4ever's blog

Topcoder Open 2017 — Round 2A
By cgy4ever, history, 7 years ago, In English

TCO Round 2A will start at 12:00 noon EDT Saturday, May 20, 2017

Top 40 will advance to Round 3 and will get a T-shirt.

Find more details here: https://tco17.topcoder.com/algorithm/rules/

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

Comments Comments (27)
| Write comment?
»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I'm sure that some time ago, the start time on that page (https://tco17.topcoder.com/algorithm/rules/) was 11:00, not 12:00, but they quietly changed it.

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

DS Weekly Challenge #8.2: Do the latest successful challenge in Algorithm Round 2A.

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

Starts in 1 hour.

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

How to solve 500?

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

    Consider just solving it for dist0 with as many edges possible. Now, take the intersection of these two solutions and see if it satisfies the original constraints.

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

      So, this is the same as creating a complete graph and removing all edges which are invalid (ie. abs(dist0[a]-dist0[b]) > 1 || abs(dist1[a]-dist1[b]) > 1).
      I finished coding this 2 min after the contest ended. FML. :(

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

    First rule out the obvious non solutions (d0[0] ≠ 0, d1[1] ≠ 0 and d0[1] ≠ d1[0]).

    Consider a pair of vertices (u, v). If there is an edge between them, then |d0[u] - d0[v]| ≤ 1 and |d1[u] - d1[v]| ≤ 1. Although this is not an equivalent condition, one possible solution is to include all edges where the above conditions satisfy. Do a Floyd-Warshall in the end to check if the solution is valid.

    EDIT: typo.

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

    A harder version was here: http://cf16-exhibition.contest.atcoder.jp/tasks/codefestival_2016_ex_a, and there is an editorial for this problem here (problem A, english version is at the end).

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

      Yes, this problem ruined my 2a. :( I tried harder version ideas and made a bug.)

      → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +39 Vote: I do not like it

How is "unused code rule" enforced? Had to scroll through 3-4 screens of templates today before reading one solution(and there were some comments inside too). pinging cgy4ever

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

Who else missed the case (c, s) = (5, 6)?

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

    I did. And also screwed up B. Yay, 0 points :)

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

    It takes me one attempt! :(

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

Medium reminds me this: http://cf16-exhibition-open.contest.atcoder.jp/tasks/codefestival_2016_ex_a

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

How to solve 250?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I did it like this: let's find all reachable pairs for A, B <= 50 using straightforward dynamic programming. If c, s <= 50, we're done. Otherwise, let's try to subtract each reachable pair from c and s and check if the gcd of the remaining numbers is not 1 for at least one such pair.

    A good thing about this solution is that it's impossible to miss a corner case as there're no corner cases (unlike in a solution that uses case analysis).

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

      Each integer greater than 6 or equals 5 always presents as 2a + 3b. Small case is easy to handle.

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

      It can be shown even stronger that if you can split (C, S) into (x, y) and (C — x, S — y) for x, y <= T and the gcd conditions hold (in my code I choose T = 10), you are done. That saves the DP :)

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

wow! too fast editorial!

Problem A seems to be almost same as 500pts!

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

Anyone can solve 1000 correctly has great attention! I didn't have >_<

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

    What do you mean? I had an idea but didn't have time to complete all its details. What I tried to do is to consider how an array b[i] = (a[i] ^ a[i + 1]) changes after a move.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      After considering the array b, there is one free variable : a[0], so the answer to the original problem seems to be something like solve(b)*2, but if we can perform no operation, then the answer is 1 (not 2). I implemented and submitted this code, but in fact, when K==1, the answer is solve(b)*2 minus 1, because we cannot make the array (~a[0],~a[1],...,~a[N-1]). It's difficult to notice this fact (at least for me).

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

        Ohh I see. I've tried to implement something in 5 minutes and failed that test and thought about this. But I gave up as my dynamic programming had a really important flaw (maybe some other observation missing?) and even though I realized multiplying by 2 needs some extra subtracting, I couldn't finish it. I think the problem is really nice and interesting, but, at least for me, it demanded more time

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

        I also missed the k=1 case, sad.

        → Reply