chrome's blog

Topcoder Single Round Match 680
By chrome, history, 9 years ago, translation, In English

Hello everyone!

TomorrowToday at 19:00 MSK will be held Topcoder SRM 680.

Let's discuss problems after contest.

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

Comments Comments (9)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

without set up arena system,can i do this contest? as view as codeforces problem set and submit my code. if there any website please give this website.

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

How to solve div1 250 problem?

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

    The constraints partition will if consistent partition the range from 1 to b into several buckets where each bucket contains a certain number of elements.

    Within each bucket that number can then get arbitrarily divided up between even and odd numbers.

    So basically you keep track of the biggest possible difference between odd and even and even and odd and if they can be zero then it's valid.

    I also checked that a partity constraint is satisified.

    There is also a nice trick where if you add a fake (b,n) constraint that simplifies conding somewhat.

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

Short editorials and my codes are on TopCoder website.

Congratulations for tourist, the only one to solve div1-hard!

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

    Once again, good work Errichto, as soon as I read Limak, I thought it will be a good contest.

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

    Knew it was you once I read bears.

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

    Can you please tell why this approach fails?

    Initially My state was dp[i][j] which represented is it possible to have j even numbers till i th sorted upto (Note If I know that there are j even numbers I also know the total numbers till i hence I know the number of odd numbers)!

    Now I can know the maximum amount of choices of even number and odd numbers by checking the difference of upto[i] and upto[i-1].

    It failed for 2 tests!

    Then I changed it to simple dp[i][j][k] represents is it possible to form a set of numbers till i th sorted upto such that it contains exactly j even numbers and exactly k odd numbers..

    Link

    It fails too!

    I cannot understand why any of my solution fails(obviously they are incorrect , but why?)

    Thanks!!

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

If tourist is not first after coding, mostly hard fails or something happens that he regains his position. Hats off!

→ Reply