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

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

Завтра Сегодня состоится Single Round Match 639 в 15:00 MSK.

Давайте обсудим задачи после контеста.

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

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

I like your ID.

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

Давайте не будем, пожалуйста, так рано создавать посты с анонсами. Они выпадают из прямого эфира и толку от них почти 0 получается.

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

    Человек думал вчера, что раунд будет вчера, поэтому и создал тему. Я даже поверил и в арену зашёл, а там — шаром покати. Тогда автор исправился и дописал, что раунд, на самом деле, завтра (уже — сегодня).

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

    Зато они вклад поднимают.

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

Another 3-week period between two SRMs

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

250 was cruel!!!

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

It was the HackRound :)

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

    15th place: l0l h4x

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

      See the 33th place. No problem solved)))

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

        Yeah, well 15th place is no problem attempted.

        Also, I guess this gives us simple proof that the "positive points for challenging" rule has been removed.

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

          The rule is "non-negative points for challenging", so you still have one chance if your score is 0.

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

            Oh, okay. I'm not too familiar with TC rules, because I never read rules. I just try out stuff for practice and check what the most important stuff means (and go by common sense). And TC has a lot of more obscure ones that don't apply to me much (like this one, since I'm almost never challenging).

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

      256th lol) But I was speaking with chinese contestant in chat and discovered that "erfen" is "lower_bound" and "huangjin" is "golden_section".

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

How to solve Div 2. 500?

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    find N such that N*(N+1)/2 == x+y, if you can't — return -1;

    and find the answer by greedy substractions x := x — N..1.

    UPD but I wasn't sure that greedy will work, so I've created array a[2*10^6] with some strange values and used binary search to find the answer "i" such that a[i]<=x

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

    This is my solution. I forgot to check the corner case when x = 0 and my solution was challenged. But I fixed and sent it after contest and it passed all the test. It is sad because I only forgot to include &&x =  = 0. Next time I will be pending for small details.

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

How to solve 1000? I've reduced it to some problem of linear programming with integer values, but do not know how to solve it in these constraints.

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

    I reduced 1100 to the form X * case1 + Y * case2, where case1 is if you feed first pet on t=0, and case2 is if you feed second pet on t=0 (eventually you'll reach a time t in which you can choose again, so you'll end up choosing case1 X times and case2 Y times).

    I couldn't finish during the contest time, but I managed to solve it in the practice room with ternary search on X. Now have fun dealing with all of the corner cases and overflows! :D

    As I can see, Petr and tourist solved it differently, so maybe their solution is a bit closer to what you came up with.

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

      I did the same as you (talking about idea), but did not come up with the ternary search approach.

      By the way, why ternary search works in this problem?

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

а можно как-то узнать тест, которым взломали мое решение??

»
10 лет назад, # |
Rev. 4   Проголосовать: нравится +35 Проголосовать: не нравится

I like the 500 problem very much though I didn't solve it in the contest. (With some array doesn't clean up and one more stupid mistake.) But I'd like to share with you guys my O(N2) solution. I am going to write a post about it. Will be updated soon. :D

UPD LINK

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

Can someone explain why in Div 1 500 folding row-wise and then column-wise independently and at the end multiplying the two values gives the correct result? My main problem is that I don't really understand why they are independent? Intuitively I thought that if the number of remaining rows is smaller, the possible column-wise folding should be smaller.

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

    Take a vertical and horizontal fold. Show that if you can fold vertically first and horizontally afterwards, the board is such that you can swap them.