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

Автор chrome, история, 9 лет назад, По-русски

Привет всем!

ЗавтраСегодня в 19:00 MSK состоится Topcoder SRM 680.

Предлагаю обсудить задачи после контеста.

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

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

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.

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

How to solve div1 250 problem?

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

    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.

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

Short editorials and my codes are on TopCoder website.

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

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

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

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

    Knew it was you once I read bears.

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

    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!!

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

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