Endagorion's blog

By Endagorion, 10 years ago, In English

Hello, Codeforces!

On Sunday, April 26th at 19:00 MSK the 300'th regular Codeforces Round will take place.

I would like to congratulate all Codeforces members and administration on this remarkable milestone. The platform has grown hugely in size and quality since its foundation, has hosted lots of exciting competitions, and has been providing the opportunity to everyone to hone their problem solving and algorithmic mastery. For this we thank the Codeforces platform creator MikeMirzayanov and all the Codeforces crew. Keep up the incredible job, guys!

That being said, I'm excited to announce that the problems on the jubilee three-hundredth Codeforces Round will be set by me, Mikhail Tikhomirov (Endagorion). You may remember the past rounds with my problems: #99, #109, #265, #283, and (in part) #295. I thank the Codeforces problems coordinator Max Akhmedov (Zlobober) for helping me in preparing this round, and Maria Belova Delinur for translating the statements in English. Also, special gratitude to Vladislav Isenbaev (winger), Alex Fetisov (AlexFetisov) and Pavel Kunyavskiy (PavelKunyavskiy) for testing the problemset and help with preparation.

This round will be shared for both divisions and will last two hours and a half (as you can see at the Contests page). The round will feature several ( ≥ 6) problems, varying in difficulty and topics involved. I hope that everyone will find an interesting and satisfying problem just for themselves! The scoring will be announced later.

To add up to the excitement, there are 30 exclusive Codeforces T-shirts to compete for in this round! The top 15 participants will get their T-shirts right away; another 15 will be randomly distributed among those who place in the top 300. Even if you think your chances on being the very best are weak, there are still good odds you will get a treat! =)

That's it. Mark your calendars and come back to compete for the prizes and for the fun!

UPD: there will be 8 problems. The scoring is standard (i.e. not dynamic): 500-1000-1500-1500-2000-2500-3000-3000.

UPD2. In order to choose people getting T-Shirts we will use the following python3.4 code that you can manually run in "custom invocation" tab on Codeforces. It uses an integer as a seed for random generator, this integer should be equal to the last submission number that happened during the contest.


import random seed = int(input()) rnd = random.Random(seed) # all contestants except top-15 contestants = list(range(16, 301)) rnd.shuffle(contestants) tshirts = list(range(1, 16)) + contestants[:15] for x in sorted(tshirts): print(x)

UPD3: Thanks for participating!

The winners are:

  1. bmerry
  2. Egor
  3. Petr
  4. rng_58
  5. scott_wu
  6. jqdai0815
  7. eatmore
  8. atetubou
  9. qwerty787788
  10. niyaznigmatul

The list of places getting the T-shirts are 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 40 46 67 75 80 102 103 144 152 161 169 198 233 243 269. The lucky participants are as follows: bmerry, Egor, Petr, rng_58, scott_wu, jqdai0815, eatmore, atetubou, qwerty787788, niyaznigmatul, gs12117, W4yneb0t, JoeyWheeler, zxqfl, yeputons, kcm1700 & HYPERHYPERHYPERCUBELOVER (sharing the 40-th place, so both get a T-shirt), piob, Leo_Yu, matrix & Nerevar (sharing the 75-th place), Haghani, ACube, DemiGuo, etal, Emarci15, hlwt, Salvare001, dzy97, FatalEagle, gchebanov & Jimanbanashi (sharing the 243-rd place), and Solaris (please let me know about any mistakes). Congratulations!

UPD4: At long last, the editorial is up! Enjoy, and sorry for the waiting.

Announcement of Codeforces Round 300
  • Vote: I like it
  • +1212
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
Rev. 3   Vote: I like it +32 Vote: I do not like it

I really hope that such jubilee round will be awesome :)

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

can't wait more!

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

Sounds cool!

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

May I suggest that in future rounds, the i-th ranked contestant would have 1/i chance of receiving a t-shirt. Then everyone will have a chance to win t-shirts, while the expected number of t-shirts needed/given is small!

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

    The number will be about ln(n) in total which is too small.

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

    so the winners (1/1==1) would always recieve T-shirt ?)

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

      Yes, of course rank 1 should get a T-Shirt.

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

    I think that even though it's a small number for a contest, there are approximately 2 contests every week; therefore, it would be a lot in total. However, this idea could be applied every 10th (or something) contest.

    Also, some users are consistently in top-15; that's why some people would get unnecessarily many t-shirts, which would be boring even for them. A time restriction (for example, you can't win a t-shirt for 3 months after you've won one) would be great. Still, some people would get the exact t-shirt more than once, and this problem could be solved by changing t-shirt design let's say every 6 months.

    Apart from these, I think this is a really cool idea.

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

    Well, I think it's not fair that e.g. 4th person gets a T-shirt while 2nd person gets nothing!

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

      But now it could be that the 300th gets a t-shirt while the 16th gets nothing too!

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

Thanks MikeMirzayanov! Congratulate codeforces on last 300 raund!

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

Looking forward to the contest!!!!!!!!

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

After more than 1 week we have a contest :D

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

Love CF rounds by Endagorion, the problems are interesting and challenges in the editorial are also awesome! Looking forward for that one!

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

I hope the problems will be interesting and attractive.

And, I also hope will have more participants in this contest. Because this is the contest for both divisions, so it is easy to get high ratings.

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

when I felt that I lost the sense of life, I found codeforces and in general ACM contest, this really change my life, Get to work facebook, google, etc. not is a dream if you study algorithms and practice on codeforces in special. so far are 300 th contests, it is incredible thanks MikeMirzayanov and Endagorion!!!! good luck and have fun for everyone thank you codeforces!!!

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

We enjoy the 300th Round in 2015, and imagine the moment that, when we have been old, we enjoy the 2015th Round together with our children — around the year 2045.

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

    It seems it better to imagine 1024 round in the 2025:)

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

Thanks MikeMirzayanov! :)

It will be really very interesting and funny :D

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

I have just ended my exams and that's what I'm waiting for :D

hope not to go downrated :3

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

You are beating PrinceOfPersia in Top Contributors list! What a week! A lot of changes and too bad for Petr :D

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

How hard is the first problem expected to be? Div 1 A, Div 2 A or Div 2 B?

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

what is the probability for someone to win 2 T-shirts? (one being within top 15, another one randomly)

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

"The round writer is Codeforces problem coordinator Endagorion. Do not miss the round!"

Looks like Zlobober has lost his job... :P

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

    Holy Dijkstra! My bad again :-( Sorry! Seems to me it's time to retire...

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

      Holy Dijkstra!

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

      Seems it's time to write automatized script with one if statement, which will generate the email.

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

      Holly Dijktra! so funny =))

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

I want the 300th rank!

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

Currently, there are only about 3500 participants registered in this contest.

It is too little in my thinking. I hope will have more, (about 5000 participants).

Because this is the contest for both divisions, so it is easy to get high ratings (if have more participants).

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

Mark your calendars and come back to compete for the prizes and for the fun!!! I hope the Round to be FUN like your last round #295 :D

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

hope it is ratingful!

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

Don't want Dynamic Scoring.

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

Обожаю когда Div1 и Div2 пишут один контест) хоть в этом контесте можно посоревноваться и с Div2 и с Div1))

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

I hope i become master and afsh5 aka.Sohieb w OmarHashim

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

Congrats! :D

You're now first in top contributors list.

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

NO Iphone 6 so tourist wont participate

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

it seems that the contest will be great,good luck everyone !!

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

When registering for the round, do you need to do something more than click the register button? I clicked on it yesterday, but I can't submit anything now, because apparently I'm not registered. I suppose there is no way of registering during the competition... this is so annoying.

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

    Yes; there are two separate registrations, one is to register for Codeforces (getting an account) which is done at the very first time before you have an account, and another is to register for each contest which is done every time before a contest starts.

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

The room link is busy most of the time during hacking(codeforces is temporarily unavailable), rest all links are working.

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

538B - Quasi Binary:

Do not have to print the leading zeroes in the numbers.

http://www.eclecticenglish.com/grammar/HaveTo1A.html:

Don't have to means that there isn't any obligation at all,
There is no need to do it.
Don't have to is different from shouldn't and mustn't.

So why the f#ck a solution that prints leading zeroes gets WA?

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

    Agree. Codeforces need a proper translator.

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

    Luckily during the round I guessed this was a translation error, but errors like these mustn't happen.

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

The clarification of problem A was simply enough to ruin the whole contest. :)

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

    True, with this clarification the contest went directly to hacking phase. After I got the notification I resubmitted mine solution cause I read it differently first time and then made around 13 successful hacks on all solutions in the room whose authors didn't update the code yet.

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

    Why did they feel the need to resend a part of the statement as a clarification? The word substring was present in the original statement, so whoever misread it shouldn't get any extra help...

    Edit: The clarification was the exactly once part, not the substring part. The comment still stands, though: if they thought the statement was OK, this shouldn't have been done (and if they thought the statement was not OK, they should have changed it).

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

What was the pretest 4 for B?

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

About me, there is not image to describe the problems.

Too many words to be able to understand the problems.

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

Does anyone misunderstood the problem A statement like me?

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

    Most of them did, I guess. There were so many hacks on A coz of this :P

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

Happiness is — when Pretests pass after 8 WAs :D (I just hope I get AC)

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

Problem D, I can't understand.

Explain for me.

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

    Fill our answer

    xxxxx xxxxx xxoxx xxxxx xxxxx

    For every cell we iterate for all figures (can all figures beat current cell). And check all crosses on table are beated.

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

What the fuck hack on problem A was ?

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

    Everyone thought it's "can cut out as many substrings as you want"

    But actually it's only allowed to cut once. (Clarification)

    So contest went directly to hacking, to hack people who didn't update their code yet

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

    CODQEFORQCES

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

    Pretests are extremely weak; most of solutions which I hacked were checking that input string contains "CODEFORCES" as a subsequence. Checking that input string contains "CODEFORCES" as a substring also passes pretests.

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

      Strong pretests take all the fun of it :)

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

      Checking that input string contains "CODEFORCES" as a substring also passes pretests.

      How does it pass the first sample test? (CODEWAITFORITFORCES)

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

        Agree, my bad. Probably I understood one of hacked solutions in a wrong way.

        However, here is another example of what can pass pretests10893468. This solution doesn't even check relative order; there is only counting of occurrences for every letter. It will say YES for test SECROFEDOC.

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

        Just cur CODE**WAITFORIT**FORCES

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

    I hacked some solutions in the end of round with tests "CODEFORCESB" and "BCODEFORCES"

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

Can someone check what is wrong with this submission for problem D : http://codeforces.net/contest/538/submission/10895720

It gives WA for pretest 1, and I can't find any move that violates the given input.

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

I will become Candidate Master. So sad

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

How to solve Problem E ?

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

    DP over subtrees, with four cases depending on which player's turn it is and which player is allowed to rearrange the numbers in the leaves beforehand.

    The number that then needs to be stored for each tree is the final result if the leaves of that subtree are labelled with the numbers from 1 to msub, where msub is the count of leaves in that subtree.

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

      Would you mind to elaborate a bit more? It's not clear to me.

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

        Let's first say we are the minimizing player and also allowed to modify the labels.

        For the subtree rooted at i, define f(i) = k if the game on that subtree ends on the k-th smallest label among the leaves in that subtree.

        There are two kinds of nodes, depending on which player's turn it is. Let's call the current node i and its children j1, ..., jt.

        Case 1: it is our turn. Let j be the child of i with minimal value of f(j). The best solution then is to rearrange the labels in the current subtree so that all the smallest labels end up in the subtree rooted at j and make our move to j. So in this case f(i) = min(f(j1), ..., f(jn)).

        Case 2: it is our opponent's turn. As he wants to maximize the result, he will move to the child j where the f(j)-th smallest label is as large as possible. We need to find a rearrangement of the labels to keep that value as small as possible, and we can see that the best we can do for that label is f(j1) + ... + f(jt). For instance, we can place the f(j1) smallest labels below j1, the next f(j2) below j2, and so on. So in this case f(i) = f(j1) + ... + f(jt).

        Let's now say we are the maximizing player. This works in fact dually, we now only have to define f(i) = k if the game on that subtree ends on the k-th largest label instead. We can even reuse the code from the minimizing case (something I didn't notice during the contest).

        Code: 10900486

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

    I figured out simplier solution: let's consider 1-st player as person we wish to win. Firsly, you can recognize, that if our palyer can get x as an answer, then he can do it for x-1.

    So you can use bin-search on answer. Let suppose your answer x, then all numbers >= x denote as 1, others 0. So you need to have 1 at the end in order to win. Let's calculate next value(dp): minimal number of 1's needed to win in current subtree. If this is vertex where you are to make move, your dp is just max of values of your childs. Else you value is simply sum of those values.

    Now the magic: we can remove bin search (which was displyed for better understanding), and replace our calculting value with something as: minimum number of large(small) numbers to win. So the answer for first would be (leafNumber + 1 - dp[root]), and dp[root] for the second.

    http://codeforces.net/contest/538/submission/10897335

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

    DFS, for each node you compute how many leaves are there in this subtree and index of a leaf to be returned (for example there are 10 leaves and this node will return 7th of them (ordered by value)), i.e. the exact values don't matter. E.g. for MAX node with two children-leaves the result is simply 2|2; for maximizing game for MAX node with children 1|3 and 1|2 the result is 4|5.

    Then figure out how to combine such values for MIN/MAX nodes, it's quite easy.

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

      I looked at your dfs code. But I can't figure out why is summing the children nodes correct for some cases? Other cases are clear though.

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

        For example in maximizing game look at MIN node. Assume children have values ai|ci, that means that in a child node i the aith element will be selected. It means we can put ai - 1 smallest elements there and they will not be selected. Sum of all ai - 1 gives us number of smallest elements we can drop away. And then it does not matter where we put the next smallest number — the MIN node will choose it, that is the index of chosen node will be sum(ai - 1) + 1.

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

How do you calculate which and how many numbers to use for B ?

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

    Maximum digit.

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

      Oh, maybe I will get Wrong Answer.

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

    The maximal digit is the answer to "how many". Simply generate a number which has '1' where N has nonzero digit and '0' everywhere else, then subtract it from N. Repeat this until N becomes 0. To me, this is done easier using strings, not numbers.

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

Looks like I finally solved B 5 minutes past 12. :( But maybe Iam wrong. System tests are pending, so they won't accept my submission yet. Here is link . http://ideone.com/1Izsvr

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

when will system testing start ?

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

2.5 hour its too much for 8 problem.I think 10 min it's enough to write all of them ;) Why author of problem D thinking that his problem gives us something... ,becose I know how to solve problem E(and idea for F) fuck him as my brain is fucked now by '#','o','.' symbols -_- Happy 300 Round -_-

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

    easy man !!! calm down :D :D

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

    I think similar to you, you are my best friend, LashaBukhnikashvili

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

      People can't understand us,they are w8ing their t-shirts and positive ratings so dont afraid about their minuses ;)

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

    aeiou

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

    Yes, problem D gave me something. I realized, that in some problems I need to output redundant "YES" before the solution itself and in some (other) problems you do not need to :) It cost me level up :) Nevertheless, I liked the contest and problems and do not feel that 2.5 was too short, first 4 problems were relatively easy, although not always well formulated :) Don't worry man, just have fun...

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

Am i the only one who overkilled B, with a knapsack? XD

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

Note for myself: don't solve problems starting from the hardest if the contest is for both divs.

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

F worth 2500 pts — 300 AC
G,H worth 3000 pts — <10 AC

Are you serious? One thing is that there were no "middle" problems, whole problemset was completely not balanced. Second thing is that point distribution was very badly adjusted. Problem with 300 AC can be worth at most 1500 pts, no matter what. If someone creates a contest with some very easy problems designed to easy Div2 problems than what he should do with Div1-type problems is to save the ratios of values of other problems, not their differences!

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

Last submission ID was 10896731. So the T-shirt list will be:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 40 46 67 75 80 102 103 144 152 161 169 198 233 243 269
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Good bye Master. Good bye Orange. Good bye HaRiSK

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

.

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

lashabuknikashvili ylea?

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

The problem statement mentioned "cut out some substring from the banner" in the second paragraph, also from the last paragraph, "cut out of the banner some substring”. But I can't see where did the problem told us that just cut exactly one substring, at least in the English version.

So could someone explain to me?

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

    "some substring", not "some substrings" ?

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

      maybe "a substring" is more suitable and unambiguous than "some subtring"

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

aeiou

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

Can somebody please help, I don't know why am I getting runtime error on problem B code here while it works perfectly on my machine.

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

in problem b 538B - Quasi Binary : in this submission 10894501 when i run the system test, the wrong test case on my machine it gives me the following:

415

5

111 101 101 101 1

here the systems says it gives

9

110 100 100 100 1 1 1 1 1

actually i have been all the contest trying to figure it out and i feel so angry can anybody tell me what is wrong with my code ???

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

    i too got the same thing..:(

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

    log10(x) is a floating point function and you should never use it for integer operations.

    Also the function has different implementations in different systems and compilers, and will give different results and/or precision errors.

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

      but i cast it as (int) ?

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

        casting, in your case, does nothing at all because your already floored the answer.

        What I am saying is that, in some systems, log10(100) may be < 2 so when you take floor, it gives 1 instead of 2.

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

My solution for B gives correct answer on ideone while it fails on codeforces server for 4th test case.linktocode

strange!!!

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

How to solve D? I was trying to check all the possible moves for various pieces, but couldn't come up with a better logic. Any pointers for it?

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

    Yes, you essentially do a brute-force check.

    For each piece (o), and for each clear space (.), you can compute the difference dx, dy. And you know that dx, dy cannot be in the set of vectors. You disallow all such dx, dy (this takes O(n^4) time).

    Now, considering the dx, dy which are not banned, you check that each "x" is indeed attacked by some piece, i.e. for each "x", there is some "o" such that the difference is not banned.

    If this is true for every "x", it is possible and you output all non-banned dx, dy. If this is false, it is impossible.

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

Are the editorials out? When and where to find them?

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

    The main blog is going to be updated when the editorial comes out.

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

    I'm terribly sorry, but the editorial will most probably not come out today. Stay tuned tomorrow, I'll update the main blog post when editorial is up.

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

In problem D in testcase 2(knight) (o..x) is invalid (I suppose we cant make this move since it forces the piece out of the board) but why in testcase 1(rook) (ox) is valid? Can anyone explain why?

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

    "If there are several possible answers, print any of them."

    o..x is a perfectly valid move in the second case, but the possibility given in the samples also correctly describes the board.

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

      Thanks! completely missed the statement that " there can be multiple answers"

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

my dreams came true, finally I hacked a red one and became international master. Thanks Endagorion..;)

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

My code for Probelm A fails on this testcase: MDBUW**C**ZFFZKFMJTTJFXRHTGRPRE**O**RK**D**VUXO**E**M**F**YS**O**MSQGHUKGYC**RC**VJTNDLFD**E**WF**S**

My output is YES but the answer is no. Why is it no? I can cut out the substrings in between the words needed and produce CODEFORCES as i have shown above. Where does my logic fail? Is there a catch?

http://codeforces.net/contest/538/submission/10898807

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

    2015-04-26 19:08:16 Announcement Problem A. Cutting Banner

    Note that you have to cut out the substring exactly once in this task.

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

    It was later given in announcement that you have to cut out the substring exactly once in this task.

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

Can anybody please explain why I am getting wrong answer on case 13 in C? http://codeforces.net/contest/538/submission/10891638

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

    In the hei[i] > hei[i-1] case, you want int ans=hei[i]+(k-index[i-1])/2; instead of int ans=hei[i-1]+(k-index[i-1])/2;, i.e. you want to increment the largest of the heights instead of the smallest.

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

      Thank you. Got it accepted after correcting this small error.

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

Can someone please tell me what is wrong with following submission of Problem — B:

http://codeforces.net/contest/538/submission/10876749

It says wrong answer of test case 4 which is: "415" and the output as:

5 110 100 100 100 1

where as on my laptop the answer is:

5 111 101 101 101 1

Can someone please tell? Thanks.

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

    Don't use pow for integers. Look it: http://codeforces.net/contest/538/submission/10899576

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

    If you change ans[i] += pow(10, cur) to ans[i] += pow(10, cur)+0.01 the solution passes as pow returns a float. Be careful with floating points — the compiler flags from Catching silly mistakes with GCC would have catched that.

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

    you could write this, but it's not standard:

    #include <bits/stdc++.h>
    #include <ext/numeric>
    
    using namespace std;
    using namespace __gnu_cxx;
    
    cout << power(10, 7); // this function is fast power that works in O(log n)
    

    also you can implement your multiplication function too.

    const int mod = (int) 1e9 + 7;
    struct mul {
       long long operator()(const long long &n1, const long long &n2) const {
          return (n1 * n2) % mod;
       }
    };
    long long identity_element(const mul& m) {
       return 1LL;
    }
    cout << power(1LL, 100000, mul());
    

    read this for more info.

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

    Thank you guys!

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

Problem A sample test: BOTTOMCODER :)) Is it joke ?!

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

For task A, one of the sample cases was DOGEFORCES. Sadly, the original image post is now down: http://codeforces.net/blog/entry/9729

Does anyone have a working link?

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

if (abs(notes[i].second — notes[i — 1].second > notes[i].first — notes[i — 1].first)) {

cout << "IMPOSSIBLE" << endl; return 0;

}

I can't believe my typo in problem C passed pretests...

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

Can anyone explain why this solution fails for E? http://codeforces.net/contest/538/submission/10901544 There are four DP cases based on whos turn it is to move and who is manipulating the game. I guess I messed up one of the cases somehow...

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    static int n;
    ...
    int n = sc.nextInt();
    
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow, I'm surprised that caused WA instead of an error... Thanks!

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

I am waiting for the tutorial in this contest (especially problem D)

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

Maybe first time that BaconLi wants to be at place 269 instead of 16 :)

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

wasn't able to participate live in the contest because of a worthless college exam. looks like everyone really had fun..

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

Still waiting for editorial...

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

Codeforces Round #300 (with prizes(without editorial!!)!).

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

The first CF round that I couldn't solve problem A, although I spent more than 1 hour solving it :(

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

I had an interesting experience with problem A. i locked and then found that my submission was wrong! So what I did was that I first hacked all those solutions which were locked so that they cant hack mine! So in the end I managed 10 successful hacks ( = + 1000 ) before my solution was judged wrong answer. I hacked 5 solutions with the same hack ( = 500 points) that would give WA on my solution as well!! It was like Counter-Strike!!

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

    BTW, It's allowed (or at least was allowed) to hack if you locked before your solution was hacked

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

      basically that is why i tried to hack all the locked solutions before they hacked mine. And I won! :)