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

Автор shigule, 10 лет назад, По-английски

Hello, Codeforces!

Codeforces Round #278 will be held at Nov/21/2014 20:00 MSK for both divisions. Note that the time is 30 minutes later than regular Codeforces time, and Moscow is currently UTC+3.

The problem setters are taorunz and me. This is our first Codeforces round!

We'd like to thank Maxim Akhmedov (Zlobober), who helped us prepare the problems very much; also to thank MikeMirzayanov for Codeforces and Polygon platforms.

This round is involved in MIPT Fall Programming Training Camp, and top-20 of contestants from the camp will be rewarded with Codeforces T-shirts. For other contestants it will be regular Codeforces round.

Hope you enjoy the round, and wish you high rating.

UPD: Score distribution:

Div. 2: 500 — 1500 — 1500 — 2500 — 2500

Div. 1: 500 — 1500 — 1500 — 2000 — 2500

It's not for everyone that the optimal strategy is solving tasks in order. Make sure you've read all problems before the contest ends.

UPD: Very sorry that the round will be moved 20 forward due to technical reasons.

UPD: Top 5 participants:

Div.1

  1. ACRush
  2. rng_58
  3. Egor
  4. Kostroma
  5. sankear

Div.2

  1. nghiand
  2. rabbit_TR
  3. mwc123
  4. batkhuyag
  5. whalyzh

Honorable mentioned:

anta, who solved Div.1 E!

CKYang, who solved Div.2 E!

UPD: Editorial is here!

UPD: hack statistics (Div.1 and Div.2) by kostka!

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

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

> "top 20 contestants blablabla CF T-shirts"
> reads it again

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

Oh maaan , the time is too late for me.

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

Codeforces Round #278 will be held at Nov/11/2014 20:00 MSK for both divisions

Today is Nov/20/2014 — are you really writing about the date in past?

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

Two amazing events in one day :

1.A (maybe ;) ) rated Codeforces Div.2 + Div.1 round after a long time.

2.Hunger Games Mockingjay part I release.

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

Oh my god, the time is unscientific, it's toooooooooo late

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

I want a T-shirt..... I haven't get the T-shirt of Codeforces! What a pity!

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

Omg

one contest after another

really cool...

if you start ten contests on a week i will join all of them...

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

top-20 of contestants from the camp will be rewarded with Codeforces T-shirts

There's no chance for us
It's all decided for us
This world has only one sweet moment set aside for us
...

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

Really do not like that time.

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

First contest that forces me to participate until 24:00 :)
And this comes in a day that tomorrow i have region olympiad :(
I think i will not wait for system checking and updating ratings today.

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

The contest is prepared by Chinese but I really don't think it is prepared for Chinese because it will start at 1:00 am UTC+8.

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

Please consider Chinese coders' sleeping time. Contests starting time has been moved from 23:30pm to 01:00am now, so sleeping time of Chinese coders moved from 01:30am to 03:30am.

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

Late night contest is great adventure

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

This unusual start time is good for me. I can start contest after taking my dinner :D

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

I want to take part in this contest because of the e-mail says: Attention! Unusual start time: the round starts on Friday, November, 21, 2014 17:00 (UTC). However , this time changes. I cannot do it now. Chinese people don't want to the Chinese one's to take part in? OK . OK.

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

我是来测试一下能不能发中文的

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

For Japanese, it starts in 2:00 AM and too hard to participate...

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

In Arabic, "saffah" means a murderer! i hope this has nothing to do with today's contest :D :D. No hard feelings bro :D

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

It seems so late, maybe I will be hungry at half.

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

oh my god! 1:00 am! I have a class tomorrow morning ==

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

I bet there will be at least 1 pure math problem! :D Because it's a Chinese round...

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

hey guys plz unlike me

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

hope for some dp!!!

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

Loving this series of CodeForces Rounds :) ..

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

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

playing clash of clans and coding and coding and coding in CF.

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

Too late for Chinese.T_T

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

Interesting score distribution!

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

can't wait. want to see new winners and at first get in div.1 :D good luck everybody

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

a3333333... why :'( !!

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

Is B harder than usual?

Please don't delay the contest! I have to go to school tomorrow and now the contest will finish at 11:00 PM in my country! :D

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

20 mins delayed?!

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

Why delay the contest...

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

    If you were here in MIPT Fall Training Camp, you wouldn't even ask :)

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

What!! It's been put off...Oh no, i must go to sleep

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

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

very bad :(

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

So for this time does "technical reasons" mean "dinner on training camp" again? :D

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

good rating 500 — 1500 — 1500 — 2500 — 2500

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

Moved is always better than unrated ;-)

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

Задержка — это плохо =(

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

А нельзя уже сделать как на топкодере, контесты в разное время? Я, конечно, понимаю, что основной контингент хороших программеров России обитает в Питере, Москве, Саратове и им удобно, когда контест начинается в 19-30, 20-00 и т.д., но чем восточнее город, тем решать становится сложнее, и реально не прет решать задачи на ночь глядя после рабочего дня и ещё 4-5 часов ожидания. Просто сложно нормально выступить, даже если ты неплохо кодишь.

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

В следующий раз я забью на все правила конфиденциальности и не затру имя и фотографию.

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

    Что-то последнее время на codeforces вообще много странных личностей развелось, то решения просят, то постят всякую ерунду в блог. Кажется, пора как на хабре, систему с инвайтами вводить %)

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

"Note that the time is 50 minutes later than regular Codeforces time, and Moscow is currently UTC+3."

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

Why profiles are locked?!

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

it seems we should expect so many "Codeforces is temporary unavailable" during the contest !!

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

Сделайте, пожалуйста, чтобы при нажатии на регистрацию на контест, если человек не залогинился на сайте, его отсылало на окно логина, а потом на окно регистрации на контест, а не как сейчас — только на логин. Уже второй раз пропускаю из-за того, что думаю что зарегестрировался, а оказывается что нет. Или возможно подсветку красным-зелёным окна, где написано время до ближайшего соревнования.

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

Its really disheartening and frustrating when you cant submit a code for like half and hour just because servers are not working.. :\

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

За 50 минут до конца:

А мне начинают нравится китайские раунды. И пофиг, что по А было TL4 и WA3.

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

    Как-то мало во 2 диве взломов в топе оО

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

      Мало кто может решить С... Я прям до последней минуты сидел и ждал, когда же еще кто-нибудь тупой перебор зашлёт)

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

        Что не так с перебором?! :D

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

          Зависит от перебора. Если перебирать все 3 значения, то можно упасть на том, что иногда выгоднее накупить много (больше того, чем многие ограничивали перебор) дешевых жизней, чем немного дорогой атаки/защиты.

          Тест:

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

          Все упорно перебирали характеристики до 100, в то время как атаку нужно перебирать до 200, а хп не скажу точно до скольки (но точно не более 10000).

          На тесте 1 1 1 100 100 100 1 100 100 необходимо купить 990 хп.

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

        В 1 диве со взломом этой задачи намного веселее было)

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

Keep getting "Server down" errors for the last 15-20 minutes. Need to cancel this round for sure.

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

I don't know if It happened only for me (!) , but CF kept "Connecting ..." for me half of the contest, and was "Temporary Unavailable" for another 15 minutes! Couldn't even submit ...

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

Nice contest ^_^

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

Very nice problems. Can't wait for the system test to end so I can submit solutions at C.

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

was hard problems mostly mathematic so i couldn't write good. but i love math and hard problems really waiting for editorial(tutorial).

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

...yet another chinese round...

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

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

Is that enough to check attack decrease up to 100?

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

    1 1 1

    100 100 100

    1 100 100

    answer is 11890(i hope xD).

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

    No, for example

    2 1 1
    100 2 100
    100 1 100

    requires increase attack by 199

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

    Attack decrease (that is, increasing defense) is enough to 100; once your defense is more than the opponent's attack, you won't be harmed. But attack increase must be checked up to 200, an HP increase must be checked up to 10000. (Someone in my room used 1000 and passed, but 10000 is easier to prove.)

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

    No. There is a easy test when you need 199

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

Solution to C:

n must be prime or 1 or 4 (trivial), so let n be prime number

a1 = 1, an = n and ai = i / (i - 1) :>>

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

    i/(i-1) = 1 (i >= 3)

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

      Division is handled in Zp field. In other words, i / (i - 1) = i·(i - 1)p - 2 mod p.

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

    ...I tried to figure out whether 9 is possible or not, since I saw that the primes and 1 and 4 worked. I should have just hardcoded the solution for 4...

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

    Why cannot n be a degree of a prime?

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

      Because we have p and 2p, if p > 2, so for p2 number 0 will occur too early.

      If n = pk, k > 2, then we have p and pk - 1.

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

      Because for non-prime N, (N-1)! mod N = 0, since N has to be last, we'll get two 0.

      Except for 4, which I forgot. I can prove it for all non-primes except perfect squares — you just decompose the number into prime multipliers and then get rid of powers — all of numbers are distinct from 1 to N-1.

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

        Same here, forgot 4 and will get 0 for this apparently =( Hate these rules, why can't we get partial scores or see the results right away.

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

          4 should be in pretests... You would force people who didn't see it to lose points, but they wouldn't get 0.

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

            No, 4 should not be in pretests. It makes good hacks. (And 1 too.) That makes people need to figure out all corner cases.

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

              It also disbalances the contest completely.

              1. Someone with a guy in the room that knows that corner case has a huge advantage, because they will get hacked and fix their code (for instance Swistakk).
              2. The person that doesn't notice the corner case gets zero points, i.e. the exact same as someone who didn't think of the solution to the problem at all.
              3. Someone who notices a corner case can get more points for noticing it than for solving a problem (especially true if the corner case is in problem A).
              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится +5 Проголосовать: не нравится
                1. This one I agree somewhat. Although the only plausible alternative is to get everyone into a single, large room, and that's just plain impossible.
                2. They have failed to solve the problem, and thus I say 0 is deserved.
                3. This is Codeforces, not ACM-ICPC; you should adapt your strategy to the Codeforces platform. If you know hacking might potentially yield plenty of points and you refuse to hack, that's your problem.
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Your argument that the contestants should adapt to the rules applies to any system, good or bad, so it's not relevant here.

                  You can have all the codes in your room hacked by someone in your room who saw the corner case 5 minutes earlier, and therefore has 700 points more than you do now. In that case hacking was never an option for you.

                  Ideally, the system should be as little luck-dependent as possible and as fair as possible, in that it allows for people who performed similarly in a contest to be placed in similar positions. What I mentioned above is an example of that not happening.

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

                  Which simply means you need to practice to find corner cases faster?

                  I don't see any luck involved among contestants in a single room (barring server problems and so). Which means I should suggest that rating updates only see people inside a room, but that will make a single position up or down to have a major effect in rating, in which those unexpected troubles (server problems) will now have big effects.

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

    Wow, it's much easyer, than I have.

    I found generator, and set ak = r(k - 1) * ( - 1)k.

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

    My solution is more sophisticated :| Let n = p be a prime number, We find generator g mod p. Let a be the sequence 1,  - 2, 3,  - 4, ..., (p - 1) / 2, ...,  - 3, 2,  - 1 mod p - 1. The answer is 1, ga[0], ga[1], ..., ga[p - 2], p.

    Oh, it's the same as PavelKunyavskiy's solution.

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

    How do you know that ai = i/(i-1) is unique for each i? Is this a known theorem or something?

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

      i / (i - 1) = j / (j - 1) implies i·j - i = j·i - j, so i = j.

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

      Let
      i * k = (i + 1)
      j * k = (j + 1)
      then
      (j — i) * k = j — i
      then k = 1

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

      1/i is a unique reciprocal of i in Zp field. This is such a number k that . There is exactly one such number and it can be computed as

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

    You got lucky you were hacked with 4... I didn't share the same happy ending :)

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

    I forgot to print "YES" , if n < 5 :(

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

    Used the same approach, can you prove that a will contain distinct numbers only?

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

      i / (i - 1) = 1 + 1 / (i - 1)

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

      Yes. x / (x - 1) = y / (y - 1)(modn) if and only if x = y(modn)

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

      Suppose you have i! = j so that i / (i - 1) = j / (j - 1) <  =  > i(j - 1) = j(i - 1) <  =  > ij - i = ij - j <  =  > i = j, so it contradicts the hypothesis.

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

Got around 12 WAs on Problem B inspite of checking all possible permutations of the given numbers. Can someone point out certain corner cases?

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

    well, for me I got 6 WAs, re-wrote the code 3 times, and in the last 2 mins, I found that I accidentally wrote 2 instead of 3 xD, (though I still don't know if it'll pass system test or not)

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

div1, I'll be back!

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

thanks shigule for nice problem

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

Seeing so many people harvesting points through hacks, I got impatient and lost 100 points :p Never doing such a silly act again! Not gonna unless I am sure of what I am doing.

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

How I can solve problem B?

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

    Div2 B For n=0 :Print 1 1 3 3 or any other satisfying numbers For n=1 :x2=2*x1, x3=2*x1, x4=3*x1 For n=2 :Sort the given numbers. x3=4*x1-x2, x4=3*x1 For n=3 :Sort the numbers. And check if (2*x1+x2+x3)/2 == (5*x1+x2+x3)/3 If true,then print anyone of these. For n=4: Sort the numbers and check them. Take float datatype here as integer may give wrong answer(Hacked 1 solution on this)

    I hope it passes final test. I am not sure if it is right.

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

      what about this test? 1 1000000 u forgot that Bi must me non-negative and <=10^6

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

        Problem statement: "The next n lines contain integers ai, denoting the number of candies in the i-th box (1 ≤ ai ≤ 500)."

        Candies wont be more than 500 so no need to check for <=10^6. I forgot to include Bi condition. Thanks. I have included it in my solution though.

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

Nice contest, but I can't pass B problem's 5-th pretest, so good bye blue colour(((

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

Why B was worth more points than usual? I think it was straitghforward, easier than usual... By the way I really enjoyed problem D, I'm fond of interval trees composing funny things :).

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

В задаче А див.1 есть тесты, на которых нам будет выгодно брать больше 100 какого-то итема?

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

    109 раз Attack

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

    как минимум 100500 взломов!

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

    Да. 1 1 1 100 100 100 1 100 100

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

    В теории:

    Защиты нам не нужно более 100, ибо имея 100 мы сможем отразить любой удар.

    Атака нужна максимум 200, ибо в худшем случае, чтобы убить монстра одним ударом, нам нужно пробить 100 защиты и 100 ХП.

    На счет количества ХП трудно что-то точно сказать, но рассмотрим вот такую ситуацию: у нас защита 1, чтобы убить монстра когда-либо нам нужно наносить 1 хп, а так как у монстра максимум 100 ХП, значит нам максимум понадобится 100 ходов, чтобы убить монстра. Следовательно, нам нужно, чтобы монстр убил нас более чем за 100 ходов. Допустим, монстр бьёт на 100, значит нам нужно (100-1)*100 + 1 = 9901 хп, чтобы монстр не убил нас до того, как его убьём мы. Но вряд ли в действительности нам когда-нибудь понадобится такое количество ХП, потому что, скорее всего, нам будет выгоднее купить атаку (и ускорить победу), нежели ХП.

    Поэтому могу предположить, что достаточным было сделать перебор ХП до 1000, атаку до 200, защиту до 100.

    UPD: Нашелся тест, где перебирать ХП нужно до 2000. Возможно, есть и хуже, поэтому лучше вообще отказаться от перебора и вывести формулу необходимого количества ХП при данной атаке и защите.

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

      Можно перебирать до 1e4, т.к мы в ход теряем не больше 100hp и нам нужно не более 100 ходов(иначе мы вообще не убьем). Если добавить break, то это успевает отработать за секунду.

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

        Я по-тестил, тупой перебор 10000 x 200 x 100 не работает, а вот перебор 10000 x HPm + DEFm x ATKm заходит.

        8792822

        8792817

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

          Достаточно в ваше первое решение добавить бряк, как только мы нашли что-то (если мы выигрываем из состояния (h,a,d) нет смысла смотреть на (h+1, a, d), (h, a + 1, d) или (h,a,d + 1).

          Добавил break — все залетает. 8796090

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

    UPD 1 x defence and 100 x attack = 200

    Sorry for mistake

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

This platform is always crashing during competitions and I can not submit another try during last minute as it keeps crashing. Really think you need to spin up some extra servers for this platform.

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

The contest was like "Lets hack as much submissions before I get hacked myself xD ".

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

let me say the reality

This problems was worst problems that i have seen in contests :(

But like other times thank u that try to make this site better and better

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

    Worst problems because they allow many hacks? I call those challenging problems. Although why do you think they are "worst"? I think they are nice.

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

Man I'm so slow, I can barely handle Div 2 questions, I have no idea what kind of mindset other experts pack, its like I'm from a different planet, it really hurts my feelings when I'm incapable of solving these supposed to be easy problems x_X

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

    Think about guys who don't even try! You are at-least trying to solve questions and slowly you will be able to solve these questions! I joined CodeChef 4 months ago and I wasn't able to solve even a single question untill my 5th competition and here in codeforces I have not solved more then 1 question! So never lose hope!

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

      Thanks, I been here for 11 months but did not participate much due college and other things however I solved so far over a hundred problems, yet when it comes to real time events, I'm incapable of thinking clearly that it becomes frustrating, I guess its just a matter of time until I get the hang of it, tomorrow is my birthday Q-q , I'll make a wish to break this infernal limit!

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

        Best of luck and Happy Birthday in advance! :)

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

        It is probably psychological then. Just try to approach it as a nice game. Do not treat it as a duty to perform well. Because as A. Einstein said, "Love is a better teacher than duty". I had the same problem for a long time (3 years), I was solving problems on USACO gold and solved some not so small portion of it, I was able to think of algorithms and code it when there was no pressure. However, I was making too much of a deal when it would come to real contests. Just let it flow, try to approach it with love and passion and you will be getting better :) Have fun!

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

    I think your rating will be increase today... 1 problem solved.

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

    Man, Don't feel bad, keep trying and practicing!

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

    You got your Birthday gift one day before see you ratings! :) :)

    Hope you will do much better tomorrow or the day after tomorrow contest! :)

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

      Unbelievable, I actually got points UP and saw a new message for the first time haha!!!! My jaws almost broke from over smiling - This is definitely the best thing happen to me over the past few months, even just for once seeing points going up is miraculous, I will no longer feel down, I will keep coding, I will code....FOR THE GLORY! -

      Thank you all for the encouragement!!! :D

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

It was difficult to read solutions of guys from room, because they usually didn't appear, because of lagging, or appeared after a time.

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

Test for A, where you need to get more than 1000 HP:

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

    Your test upgrade :))

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

      Yeah, I stopped as soon as I got over 1000, because that was a constant in the code. I've also seen 2000 as a constant, but I don't think it's possible to create such a test.

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

        I was too lazy to think tonight, so I checked hit points up to 100000000 using binary search:)

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

first time ever I see myself on the first ranking page during the contest

probaly means that my solutions are wrong

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

Oh man. Don't tell me everything is going to be delayed today. The contest started late. Now, the system test is pending. Later rating update will be slow. And finally we will see analysis after a week? lol. Feel like going to sleep (already 2 AM), but can't beat the curiosity to see what will happen to my rating. What a dilemma.

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

Why it didn`t start evaluation?

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

Awesome problem set! I'm so gonna be red after this <3

Edit: 2179 ._.

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

It was very bad contest. CF was not available. It's better to unrated this contest

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

But where is 277.75?.. :D

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

I have a doubt in problem A Div 2

what should be the answer of -5?? 3 or 13

if you say 3 then why the answer of -1 is 9 and if you say 15 then OMG OMG I left more then 5 hacks and what I thought is that my solution is wrong which is giving me 13 on -5

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

Problem B: DIV2: I wrote my solution assuming that the inputs are ordered! After getting update, I had to come up with a complete new solution.The update came after almost one hour. Which means I took part in the round for only one hour instead of two! Will it be fair that the contest is rated for them who faced the same problem (Who misunderstood B and had to re think the problem for a while and rewrite the entire code)?

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

    Same here! It was a completely new problem when they updated and my this round (which could really go well) went too bad! :(

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

    Well, that's not right. You weren't promised that inputs are ordered, so you're the only one to blame for that. The autor actually helped you (and me aswell :P), but honestly he didn't have to.

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

    It is always advisable to not make assumptions until explicitly mentioned.

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

      The description told that x1<=x2<=x3<=x4, missing some integers does not change the order! does it? Leave all other cases, my first solution was like : if a valid set(1,1,3,3) is shuffled(3,3,1,1) I as giving NO O.o . I thought they had to be satisfied x1<=x2<=x3<=x4 as well as other three conditions. Anyway , leave it. Those who has experienced problem setting knows that how difficult it is to make statement clear for all. But, I am a bit upset because the clarification took a long time to come, and the contest could be extended for 5-10 minutes.

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

        I could figure out that we would have to order the input in such a case as otherwise a median or range would not even exist if it was not ordered.

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

How long it takes in system testings ?

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

Hello Everyone can anyone help on this ....

http://mirror.codeforces.com/blog/entry/14789

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

Time Limit Exceeded for System Testing :D

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

Height of Revenge : akashdeep :D :D

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

    Maybe you're wondering why your picture doesn't show. That's because you don't link to the picture itself, but a page that shows the picture. You need to link directly to the picture, or it won't work.

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

Can't believe missed an endl in problem B when only 6 people solved it, and took me 1:53 to find the problem at last :(

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

finally the system testing is started!!

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

Что отделяет меня от 2 места в div2:

for( ll a4 = a1; a4 <= 1500; a4 ++ ) {

for( ll a4 = 1; a4 <= 1500; a4 ++ ) {

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

IMHO n=4 for C should have been in pretests. After all, it is just an ugly corner case with with hardcoded answer:(

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

A contest full of hacks and failed system tests.

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

Why did D have a special limit of 10000 change queries? It can be solved in n*log(n), which works fine with 100000.

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

    Could you tell this solution?

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

      Segment tree with mappings. To answer a query, we go up the tree until the left node brings us to an edge or cycle, then down until we reach the bottom of the tree.

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

        Could you kindly give more detailed explanation about your solution? Thanks.

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

          We can express every row as a mapping from 0..9 to either a column 0..9, Left, Right or Cycle. Then we can build a segment tree on these mappings, where each node stores the composition of all mappings in the subtree (from right to left). After updating a row we simply need to update nodes on the path to the root (log(n) operations). To get the answer, we start in the leaf node corresponding to our row, then go up the tree, changing the current column whenever we go left. If we get Cycle, we output immediately. If we get Left or Right, we need to go down the tree to find the exact row where we left the table.

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

            Thanks, I got this idea already by scanning your code. I like idea of Segment Tree with mappings. Could you recommend other problems with this idea?

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

    I misread the task and thought that all "<>^v" are possible and solved that version, 10000 constraint helped a lot.

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

      Wouldn't that make it a lot more complex than simple sqrt decomposition, since you can go back and forth between chunks?

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

        You can do (maybe not so simple) sqrt decomposition on C type queries. For each 100 C type queries mark those cells as important and for each other cell calculate first important cell on it's way. Now when you have A type query you can just traverse through important cells (at most 100 steps, each time you move from important cell to it's successor (probably unimportant cell) and use precalculated data to go to next important cell) and when having C type just change corresponding char.

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

          "for each other cell calculate first important cell on it's way" — how do you exactly handle that thing?

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

            Every 100 queries do a DFS, for every cell follow links until you hit an important cell or a cell you visited before.

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

Such a bloody Div.2 Contest! Congratulations to those who were able to correctly solve Div2 C :) And thanks for the nice problemset

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

O(n) div. 1 B solution: 8791632

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

In Div #2 Problem B Candy Boxes it was mentioned

"All your numbers b must satisfy inequality 1 ≤ b ≤ 10^6....."

but the system doesnt check for 10^6 condition

Example: the case

1 999999

the ans should be

YES 333333 333333 999999

but it also passess the solution

YES 999999 2999997 2999997

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

Got a rank of 185 by solving only Div2 A! 5 Hacks saved my day .

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

Where can we obtain the editorial?

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

    Editorials has not been published yet. Once they are published, it will be updated in the main page

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

Кто-то уже посчитал, по какому месту кат-офф футболок на сборах?

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

Рейтинговый? Млять, вы шутите?

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

Please explain why my solution get ML ? http://mirror.codeforces.com/contest/487/submission/8791889

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

Problems were very interesting, thanks!

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

Despite my rating increased by 82 but I think this round has to be unrated
I left the contest after about 45 min every time I make refresh I found no response
I tried a lot of times to submit A but no response also at a moment I make refresh I submitted an old code for C and didn't manage to submit it again about 15 min.
so I think it's unfair to make it rated unless it's a problem of mine
Thanks

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

    I didn't really face any problems during the contest, other than the contest problems of course :)

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

How to solve 487B - Strip?

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

Лично у меня и у моих знакомых, которые тоже писали раунд, пол контеста сервер был недоступен! Как так раунд рейтинговый?

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

    В самом начале открываешь все задачи, и если кодфорс недоступен решаешь следующий...

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

    У меня был недоступен в районе 70-90 минут от начала контеста. Если страницы и открывались, то невозможно было посмотреть чужой код для взлома. Всё остальное время работало более-менее нормально.

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

After contest i got AC in B (div.2) despite my program would incorrectly print a solution for such corner case: 2 n n*3(separated by newlines), but tests doesn't included it.

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

Почему взлом №125675 был проигнорирован? На контесте я заметил, что по мне была неудачная попытка взлома от VArtem, сейчас (в окончательных результатах) её нету. В списке взломов она присутствует с вердиктом "Игнорирован".

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

already orange ))

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

Why the author's solution produces different output in these two hacks: 125341 and 125632

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

    What is even funnier is that checker didn't accept lac of EOLNs (-_- ...) : 8783190, so that second answer of author's solution won't be accepted :pp.

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

Can anyone explaine me what is a monotonic queue (editorial)?

Thanks x_x

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

Country wise standings has been updated. Also I want to ask a question that how much beneficial is it to the community now and should I continue with it ? I ask this because I have to pay for the hosting from my pocket and it becomes a bit expensive to do it every month and it is going to end pretty soon.

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

captain my captain

i wonder

why do you prefer this round to be at midnight? @shigule