shigule's blog

By shigule, 10 years ago, In English

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!

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

| Write comment?
»
10 years ago, # |
  Vote: I like it +48 Vote: I do not like it

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

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    "from the camp"

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Yes, that's what I found out when I read it again.

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +61 Vote: I do not like it

        I agree, this valuable information could be spread among participants attending the camp.

        No necessity to write to others about t-shirts which could not be received by them :D

»
10 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Oh maaan , the time is too late for me.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Its never too late for a Codeforces Contest!!!!!

»
10 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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 years ago, # |
Rev. 5   Vote: I like it +9 Vote: I do not like it

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 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Omg

one contest after another

really cool...

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

»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Really do not like that time.

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Maybe we want to make something different from previous Chinese rounds. As you can see, no one is here saying anything like "yet another Chinese round, huh?"

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      So ? You do not want the Chinese coder's to do this Chinese round?

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        I think it should be a Codeforces round first.

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

      yet another Chinese round, huh?

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Late night contest is great adventure

»
10 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is 17:00 UTC, isn't it?

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

    the later 2 days is one of China Regional Contest....SO, most of coders will decide to have a good sleep.

»
10 years ago, # |
  Vote: I like it -54 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +67 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    Okay this name is randomly typed when I was 9 years old and needed a nickname......

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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

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

    Close condition?

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It's not a typical Chinese round.
    (At least the time is unusual, isn't it?^_^)
    We hope to break the stereotype about Chinese rounds.

»
10 years ago, # |
  Vote: I like it -44 Vote: I do not like it

hey guys plz unlike me

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hope for some dp!!!

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Loving this series of CodeForces Rounds :) ..

»
10 years ago, # |
Rev. 3   Vote: I like it -34 Vote: I do not like it

»
10 years ago, # |
Rev. 3   Vote: I like it -62 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Too late for Chinese.T_T

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting score distribution!

»
10 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

a3333333... why :'( !!

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

20 mins delayed?!

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why delay the contest...

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

very bad :(

»
10 years ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

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

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

    so we are waiting for them to finalize their dinner :D

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I know nothing about their dinner, but i was able to finish my dinner thanks to this delay :Ъ

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

      well atleast somebody's happy for the delay!!

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

good rating 500 — 1500 — 1500 — 2500 — 2500

»
10 years ago, # |
  Vote: I like it +88 Vote: I do not like it

Moved is always better than unrated ;-)

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    Better hope it won't be unrated in the end, then :D

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

      You are right, hopefully the'll fix the problem completely not partially, we will see...

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    [Deleted]

»
10 years ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

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

»
10 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why profiles are locked?!

  • »
    »
    10 years ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it

    I can't even open my own profile.

    UPD- Now Everything looks ok.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    For no chitting mb=)

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    to reduce the load I think

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Yeah, that's to prevent cheating and begging solutions during contest.

    That has already happened during last 3(/4?) contests.

»
10 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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 years ago, # |
  Vote: I like it +67 Vote: I do not like it

Nice contest ^_^

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

    When I saw so many people were getting extra points by hacking A, I thought to give it a try myself. Then I found that almost all the hacks in my room has already been taken by someone. Not to mention, I couldn't think of any tricky case either. What case did you use?

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 3   Vote: I like it +5 Vote: I do not like it

      I tried to find minimal test case to let people do the same mistake again =) Most of all can beat with follow test case:

      1 2 1

      2 100 1

      1 100 100

      And second test (for those who tried to fix solution but failed):

      1 2 1

      30 100 1

      1 100 100

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    True rampage! You are amazing!!!

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Your room mates hate you, I'm pretty sure :-D

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it +9 Vote: I do not like it

      To tell the truth I have found mistake in my own solution. =)

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

      Actually he is doing them a favor. It is better to know that your solution is wrong earlier in the contest than towards the end, or not know it at all. :)

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Did you add your profile pic now to go with the picture? :D

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

    poor people. :D

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

    забавно, что на тесте

    1 1 1

    100 100 100

    1 100 100

    у тебя падает)))

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Your profile pic + the image = perfection =))

»
10 years ago, # |
Rev. 3   Vote: I like it -13 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it -14 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

...yet another chinese round...

»
10 years ago, # |
Rev. 3   Vote: I like it +15 Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is that enough to check attack decrease up to 100?

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    1 1 1

    100 100 100

    1 100 100

    answer is 11890(i hope xD).

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    No, for example

    2 1 1
    100 2 100
    100 1 100

    requires increase attack by 199

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

    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 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    No. There is a easy test when you need 199

    100 1 50
    100 100 100
    100 1 100
    
»
10 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

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

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

    ...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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why cannot n be a degree of a prime?

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it -13 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            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 years ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              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 years ago, # ^ |
                  Vote: I like it +5 Vote: I do not like it
                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 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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 years ago, # ^ |
                    Vote: I like it +5 Vote: I do not like it

                  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 years ago, # ^ |
    Rev. 2   Vote: I like it +18 Vote: I do not like it

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

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

  • »
    »
    10 years ago, # ^ |
    Rev. 3   Vote: I like it +12 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it -8 Vote: I do not like it

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

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      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 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

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

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

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

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

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

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

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

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

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

      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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +17 Vote: I do not like it

div1, I'll be back!

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks shigule for nice problem

»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How I can solve problem B?

  • »
    »
    10 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        10 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

    I passed 5th pretest but not 6th. Don't even know what's wrong with my method. Hoping that the editorial comes out soon :)

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

    small bug(

    YES
    125
    375
    375NO
    

    forgot return 0 (((

»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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 years ago, # |
  Vote: I like it -18 Vote: I do not like it

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

  • »
    »
    10 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it
    2 1 1
    10 2 100
    100 1 100
    

    109 раз Attack

  • »
    »
    10 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

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

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

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

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it -12 Vote: I do not like it

    В теории:

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

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

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

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

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

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

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

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

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

        8792822

        8792817

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

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

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

  • »
    »
    10 years ago, # ^ |
    Rev. 3   Vote: I like it -9 Vote: I do not like it
    1 1 1
    100 2 100
    100 1 100 
    

    UPD 1 x defence and 100 x attack = 200

    Sorry for mistake

»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    in what time it was not working?

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

      During the previous 3 competetions(including today's) it has been crashing constantly .

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

    It was quite rare for me. ( twice at the middle ) Also you can save the statements locally...

»
10 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

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

    it was really like this

    specially problem B...

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Best of luck and Happy Birthday in advance! :)

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

        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 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

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

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

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

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

    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 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

1 10 1
99 100 1
1 100 100
  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Your test upgrade :))

    1 2 1
    99 100 1
    1 100 100
    
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

probaly means that my solutions are wrong

»
10 years ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why it didn`t start evaluation?

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

Edit: 2179 ._.

»
10 years ago, # |
  Vote: I like it -21 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

But where is 277.75?.. :D

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    of course it's 13, it says such that, if he walks b floors ""higher"".

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

    For -5, its 13. You can only take "positive" steps. That means you can move forward and not backward.

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

      but what about -11 when I solved it with 19 get a WA while solving this with 3 I got accepted! Wasn't it confusing?

      • »
        »
        »
        »
        10 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        -11 + 3 (minimum) positive steps = -8

        -11 + 19 (not minimum anymore) positive steps = +8

        I hope its clear now.

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

        Look at 19 numbers starting -11.

»
10 years ago, # |
  Vote: I like it -9 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

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

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How long it takes in system testings ?

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello Everyone can anyone help on this ....

http://codeforces.net/blog/entry/14789

»
10 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Time Limit Exceeded for System Testing :D

»
10 years ago, # |
Rev. 6   Vote: I like it +37 Vote: I do not like it

Height of Revenge : akashdeep :D :D

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +1 Vote: I do not like it

finally the system testing is started!!

»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

A contest full of hacks and failed system tests.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Indeed! Never seen another similar to this one

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you tell this solution?

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

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

          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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

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

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

O(n) div. 1 B solution: 8791632

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    158 place "A" and "C" ... "B" hacked :( Next time I'll take purple :D

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can we obtain the editorial?

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

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

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

    You don't call "build" anywhere.. not sure why the ML though.

»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Problems were very interesting, thanks!

»
10 years ago, # |
  Vote: I like it -22 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 487B - Strip?

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +3 Vote: I do not like it

already orange ))

»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

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

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Thanks x_x

»
10 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

captain my captain

i wonder

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