Блог пользователя cgy4ever

Автор cgy4ever, история, 5 месяцев назад, По-английски,

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/

 
 
 
 
  • Проголосовать: нравится  
  • +48
  • Проголосовать: не нравится  

»
5 месяцев назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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.

»
5 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Starts in 1 hour.

»
5 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

How to solve 500?

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +39 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится +39 Проголосовать: не нравится

      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. :(

  • »
    »
    5 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится +23 Проголосовать: не нравится

    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.

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

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

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
Rev. 3   Проголосовать: нравится +39 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve 250?

  • »
    »
    5 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится +20 Проголосовать: не нравится

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

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks :)

»
5 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

wow! too fast editorial!

Problem A seems to be almost same as 500pts!

»
5 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        I also missed the k=1 case, sad.