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

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

Here in this 1073C - Vasya and Robot my observations are -

1)If (abs(x) + abs(y)) < string_length then ans -1

2)If (abs(x) + abs(y)) > string_length and ((abs(x) + abs(y))-string_length)%2 != 0 then also ans -1

Then I was thinking like, okay only way can be binary approach or any tiring greedy approach. But none of these could not help to proceed. Because If I will use binary search, how can I increase or decrease the length.

Do not put any direct solution. Just hints or just let me know where my thinking is wrong?

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

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

I am trying to be very subtle...

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

    On length. But,if on length, from where it has to be started?

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

        Nice. I have got it. But I thought, checking for each length might cause TLE. Because for each length there would be (n-len) positions to check.

        But it won't. Because we might have to check for logn length. And in worst case there might be nlogn complexity . Well I do not know if my calculation of TL is right :3 But I have got the idea. Can you please explain the complexity? And thanks for being subtle <3

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