dreamoon_love_AA's blog

Codeforces Round #292
By dreamoon_love_AA, 10 years ago, In English

Hello, everyone! Codeforces Round #292 will be held at Feb/17/2015 19:30 MSK. We're looking forward to your participation!

The problems are from dreamoon_love_AA, and thanks Shik for some discussion. Also we want to thank Zlobober for helping me prepare the round, AlexFetisov and winger for testing this round , Delinur for translating the statement into Russian, and MikeMirzayanov for Codeforces and Polygon.

This is first time I provide all problems for a Codeforces round. I hope you'll find it interesting! Please read all problem statements and discover what the main character drazil do in those problems for he's really cute =)

Finally, I would like to ask sorry_dreamoon to participate this round. I believe everyone have the same curiosity as me about your behavior in Dreamoon's round =) May I have the honor of inviting you?

Update1 : Because problems of this round are hard to determine their difficulty, We will use Dynamic score for this round. Then the order of problems is from easy to hard by sense of me and testers.

Update2 : Due to technical reasons we have to move round on five minutes.

Update3 : Congratulation to our winners:

Div 1:

  1. Haghani

  2. sorry_dreamoon

  3. Endagorion

  4. jcvb

  5. xyz111

Also, special congrats on rng_58, who solved problem E in Div.1, which anyone else could not solve.

Div 2:

  1. EarthQuito

  2. I.Smirn0ff

  3. zclimber

  4. Chipe1

  5. tylerbrazill

Between them, EarthQuito is the only person who solve all problems!

Update4 : link to editorial

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

Comments Comments (284)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it will be great, I agree with sorry_dreamoon :) Best regards.. Ibahadir Altun ..

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

I have a little doubt, dreamoon_love_AA is man or woman? :)

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

"[user:???] for translating the statement..." , I think you mean Delinur

and please pin this post in CodeForces home page so everyone can see it :)

[edit] fixed, thanks :)

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

Please allow tourist to change his handle to sorry_sorry_dreamoon for this round .

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

    Am I the only one who thinks tourist is sorry-dreamoon himself??

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

    Plot twist: sorry_dreamoon is already tourist

    EDIT: Damn, I was not first :(

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

      But sorry_dreamoon's solutions were written in Java .

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

        Pretty sure that since tourist is rated 3200+ with C++ he would easily still be 2700+ with Java, even if he does not know the language quite as well.

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

        I don't think it's very difficult for toursit to write solutions in different languages. For example in результаты, he wrote code in delphi, and won 3rd place in Div 1. I don't know delphi, but it looks like Java is much closer to c++ than delphi.

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

          Trust me, when shifting from C++ to Java, you'll encounter many (from a competitive point of view) stupidities and need to find out how to skip them.

          For example, suppose you want to debug and throw return 0; somewhere in the middle of your code. C++ has no complaints; in Java, it won't even compile! Because you can't have leftover code after returns.

          Pair? There's none, write your own. Map? Which map? There are about 3 types. Vector? Possible, but ArrayList is a new version of Vector. Forget about using [] in vectors (or arraylists), you need to use access/modify functions. Which arguments are passed to functions by reference? Not to mention having to throw some exceptions.

          A lot of these things make sense from a development point of view (the absence of a Pair class does not), but are unnecessary in contests and definitely take some time to learn. Nobody would chug out a working code in Java on the first attempt.

          Also, implying nobody but tourist can beat dreamoon_love_AA.

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

        so sorry_dreamoon is already petr :P

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it

        tourist can program in Java. you can see it in this link: http://mirror.codeforces.com/contest/482/submission/8394627

        Do you think: 1-what does tourist do during the contest? 2-why does he register but don't Participate? 3-why is he online now,if he don't want to Participate in this contest. understanding it is easy: if he copy his code that submited with sorry_dreamoon's profile and submited it in onother profile (tourist) everybody understand that tourist is already sorry_dreamoon so he have to program in Java and C++ and it is a hard work!

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

          of course sorry_dreamoon can program in C++ because he hack Mohamed.Bassem and randan's solution and both of them program in C++ but sorry_dreamoon program in Java! Who is sorry_dreamoon? it can Specified in the future for next contests... . ;)

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

            you don't need to know other programming languages to hack solutions of different participants

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

              you're right but for certain you must know other programming languages(of course if you have many time.)

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

Petr possibly be sorry_dreamoon , the program in java .

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

I wonder how sorry_dreamoon feels when reading all those comments considering whether he is tourist or Petr :P. My contribution to that investigation is that we can clearly exclude all participants from here: http://mirror.codeforces.com/contest/498/standings :D.

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

    You aren't there!

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

    I think we can narrow down the list of suspects to 5 after today's contest!!

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

    It's definitely not Petr. I don't think he has the time to play games like this because of work + He never considers pure Div.2 rounds. I'm almost 100% sure that it's either tourist or YuukaKazami because though the code is in Java, their style is so damn similar (one letter variable names etc.)

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

      Yea.. True. Not only that, both of them keep braces for single line if/else statements. Both of them have a single space after ; in loops. Both have same spacing for braces in general, single space then a brace. The only difference one could spot is the newline spacing between different modules in the programs, tourist does not use spaces/newlines at all, whereas WJMZBMR uses a single line to separate out different sections of the program(similar to what sorry_dreamoon did).... :D

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

    Why not Egor ?

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

    what about niyaznigmatul or Egor ? They are in a group of five people ( Petr, Egor, niyaznigmatul, Illyakor, mmaxio) from top 30 who use java . Illyakor and maxio participated in div1 284.

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

      If it is a group of five users from top 30, I think the score of Codeforces Round 284 (Div. 2) may be higher. I think two or three users will be possible.

      Because 3 minutes(147 seconds) for div2B and 3 minutes(183 seconds) for div2C(div1A) is an amazing speed for reading statements and coding if it is single!

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

    Let's ask Mike about him and his IP address. And then ban him for using second account!

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

nice today!!!!

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

Would love to see dreamoon_love_AA and sorry_dreamoon compete in the next Div 1 contest. Lets see if he manages to beat him in a Div 1 round.

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

I'm dreamoon' for math!!

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

how it would have looked when dreamoon was blue,hosting a div1 contest!

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

sorry_dreamoon reading comments:

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

How about dreamoon_fan? He (She) is 3rd place in the CF Round #284 (Div.2) :D

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

Am I the only one who thinks YuukaKazami is sorry_dreamoon? :P

→ Reply
»
10 years ago, # |
  Vote: I like it -65 Vote: I do not like it

Hi!

I can't solve this зproblem. My code:

include

using namespace std;

int main() { int a, b; cin >> a >> b; int ans = 0; for (int i = 0; i < a; i++) ans++; for (int i = 0; i < b; i++) ans++; cout << ans << endl; return 0; } Please help

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

    holy mother of formatting.

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

    This type of code (and God bless that styling) is one of the reasons robots + computers are going to declare war against human being someday.

    P.S: If it was a joke, please accept my haha.

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

Tomorrow night is Chinese Spring Festival's Eve, which is the most important festival to Chinese people, just like Christmas Day to western people. The Chinese year of the Sheep (or goat || ram || lamb?..) is coming, I want to say "Happy Spring Festival" to every friend on Codeforces!

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

    Wish you a happy Spring Festival :D

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

    Happy Spring Festival...I think many Chinese students are busy preparing for tomorrow's big dinner and visiting their relatives, so the number of contestants decrease a lot.

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

    Wish everyone a happy Lunar New Year!

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

    It is my first Spring Festival's Eve with coding~~~ Amazing night!

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

    Happy Spring Festival!

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

    Happy Spring Festival

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

My first DIV1 contest, look like it would be a severe fight for me tonight.

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

Wish score distribution won't be DYNAMIC...

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

    ...and the scoring is dynamic, just as we all had not hoped D:

    Because problems of this round are hard to determine their difficulty, We will use Dynamic score for this round. Then the order of problems is from easy to hard by sense of me and testers.

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

GL & HF to everybody!

→ Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it -37 Vote: I do not like it

its dreamoon_love_AA VS sorry_dreamoon Again :p

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

    You should change the names on the back of the clothes~

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

3 hours before contest, good luck everybody, I'm definintely gonna be green after contest ends

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Does peter50216 have any CF account?

Update: Oops, he is peter50216 on CF, I didn't know that.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

deleted

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

    too soon. No I seriously mean it, it's too soon.

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

It will be amazing to see if dreamoon_fan participates or not :D

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

hoping to get good rank in my 100th contest :)

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Thank everyone this round was very interesting!!!

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

Can you tell me what is the difference between dynamic scoring and the usual scoring, please? I'm sorry if you find my question stupid :)

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

do you know what's the meaning of Dynamic score for me ??? yep you are right Div_2 again :D

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

There's only one way to find out who sorry_dreamoon is and this will work only if he is not very careful. Someone who works at Codeforces can determine the IP address from where he is logging in and compare it with the IP addresses of all other users. By this comparison, we will either get one particular user who always logs in from the same IP address or we might get a few users who log in from the same IP address (maybe behind a university proxy?). Hopefully, there won't be many International Grandmasters in the list.

This will work only if sorry_dreamoon is not very careful and doesn't use proxy servers (or Tor) to be anonymous on the internet (at least while logging into Codeforces with that handle).

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

Why does Div. 1 start 5 minutes later?

UPD: Oh! Div. 2 also moved by 5 minutes.

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

Thank you very much!

P.S. I just want +331 too =)

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

I hope the 5 minute extend will be the only technical problem today, dreamoon_love_AA is an awesome coder and I hope we will be able to enjoy his problems without any difficulties :)

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
10 years ago, # |
  Vote: I like it +29 Vote: I do not like it

I think sorry_dreamoon is one of the ITMO guy (by looking at his style of code) and my wild guesses are mmaxio or qwerty787788

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

    Yeah even I guess that it could be more of a chance being qwerty787788 looking into the style of his code, even now he didn't attend today's srm and was just active 4 hours ago and the style of his coding looks way similar and yeah he didn't attend srm 284 and was regular for all other srms other than 284 , so chance of sorry_dreamoon being qwerty787788 is high :D :D :D

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

It would have been fun to the characters of the problems were dreamoon_love_AA and sorry_dreamoon

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

Guys, ABHISHEK004 and pranjuldb are cheaters. They are from my room. I want you to take a look at their submissions for A after the contest!

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

It's time to back to the old color.

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +34 Vote: I do not like it

I think Haghani should change his handle to sorry_(sorry_dreamoon) :)

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

What is wrong with pretest #1 on problem B div2? I can't believe my solution didn't pass it.

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

    Pretest #1 is the sample, the one which is in the task description

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

      That's why I'm asking. My solution passed all sample tests on my computer. It's very strange...

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

        Maybe you used freopen or ifstream or you read from some files(most of coders use input and output files and than, when they submit, erase that part of program)Anyway, it could be also something like you used dome variables which weren't defined.I can't view your source yet.

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

        http://pastebin.com/SrNrsUaP

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

          Use "Custom invocation".

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

          I don't know what to say.The only strange thing is taht you used reserve with n and m.I think it would be better to use sample vectors or to reserve something like n + 10

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

            The problem was that reserve() leaves the vector uninitialized. I should have used resize() which sets all values to 0. D'oh :-(.

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

what was the hacking test case for C(div2)/A(div1) ?

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

    1

    9

    Answer is 7332

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

      I've hacked 2 solutions with 1 9, but my solution is wrong too((((

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

        I just missed your code. Was looking for this mistake, don't know how I overlooked it.
        I missed your A also. Hacked Thandkou's code for the same mistake. Shit.

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

          What is the mistake? I mean, what did those people miss so their solutions can't pass this test?

          Maybe my last post as a purple coder this week :D

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

            In DIV 2 A they were checking (a + b) % 2 = s % 2 where a and b can be less than 0.
            In C they missed 9 case.

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

              I don't know what I missed in B. WA on test 41 :(

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

                ashish1610 u hacked two div1A problem just 2-3 seconds before I could hack it.

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

      what's the answer ?

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

    Mostly just 4, 6, 8, and 9, in case people aren't careful enough with which digits should replace them. (4 is replaced by 322; 6 is replaced by 53; 8 is replaced by 7222; 9 is replaced by 7332. I think most people missed the 9 case.)

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

      and you're right, sir! ;-(

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

      most people missed the '9' case because it was hard to calculate out :(

      anyway problem set was great

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

Good bye Div-1!

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

    You're not alone

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

      Guys, can I join you, please? :D

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

        No, you couldn't :P

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

          Hahahahah, what a luck!!! :D

          However, I think it is better for me to be Div2 until I become able to solve almost every Div2 D problem...

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

        1700.... it's your fate not to join us... Deal with it!)

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

sorry_dreamoon is no.1 in Div1!

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

    I think he/she can pass system test safely!

    UPD: although he/she pass system test... It is surprising that so many FST on B, therefore, the score of B level up from 500 to 1000~~~ rank change!

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

    Maybe he really is the Petr...

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

My life is ruined. I took less number of days in problem B of div2. Was hoping to become candidate master. But now my rating will fall. :(

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

Was D div 2 a bipartite matching problem?

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

    The constraint leads to topological sort, I guess.

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

    I don't think so.That's why they want to know if the solution is unique.If you used bipartite matching, it would took too much, and also, you are unable to see the uniqueness.

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

    No! It could (hopefully, of course) be done greedily.

    • If there is a free cell that is not adjacent to any other free cell, it cannot be done;
    • If there is a free cell adjacent to exactly one free cell, we must place a domino on these two cells;
    • If each free cell is adjacent to more than one free cell, then we can immediately stop (say there is exactly one correct tiling; of course no two dominoes can share a long edge, and it can be proven that there is a cycle in which consecutive dominoes touch each other, for example:
    <><>*
^**<>
v***^
<><>v

    and then you can flip all these dominoes "one forward":

    ^<>^*
v**v^
^***v
v<><>

    giving another good configuration).

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 5   Vote: I like it 0 Vote: I do not like it

      This greedy in my implementation was hacked.

      UPD: I've got TLE with using set of free cells. Maybe there is way to know whether exists cell with single free cell nearby itself without set

      UPD: Using set of pairs was so lame idea. I've got AC using queue. Thanks to mnbvmar

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

        Your code is wrong then. I implemented the same algo and passed system test.

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

        My code got Accepted. Maybe it was too slow (now I see some people getting TLE) or didn't consider some cases?

        // Edit: balalaika: you can use a queue/stack/whatever. When you take an element from such structure, we just check whether we haven't processed it before. It is conceptually similar to a priority queue-based implementation of Dijkstra's algorithm.

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

          I used the same idea, I had luck , because my code passed in 1.996 seconds I use a priority_queue<> how implement with a queue or similar structure for avoid insert and delete operation in o(logn) my solution is O(n^2 * logn) I want implement O(n^2)

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

            Use queue of coords. Firstly push into queue all cells adjacent to exactly one free cell. Then while queue non-empty, you update table and if after that you've got another cell adjacent to exactly one free cell then you push this cell into queue.

            If queue is empty and you still have free cells then output "Not unique"

            Since queue::push() and queue::pop() perfomance for O(1) and each cell can be pushed no more than once you've got implement O(nm)

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

              thank you !! that was overkill

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

Has anybody solved D faster than O(N * Q * log(n))?

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

It seems that sorry_dreamoon's identification will remain a mystery

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

Problems were so so nice, that I was very upset then contest ended :(

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

sorry_dreamoon became 1st again!!!

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

Only champions league can make me happy after such a lose :(

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

    In time zone of GMT +8, the game start at 3:45 am :( sleepless night again

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

      Same here, but still not so bad as yours. GMT +5

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

I solved 3 problems in div2.. My best record :>

of course, if I pass system test..

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

For Div2 participants, this round was a super hack round!!! Problem C was easy to hack!!

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

sorry_dreamoon : Petr or mmaxio or ilyakor or qwerty787788 or eatmore who in top 100 and didnt participant #292 and coding java

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

The problem C (div.2) is excellent! Very interesting and pleasure:) Thank you very much!

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

Div1 B must have been quite tricky...I think over a third of people submitted and failed system test on it.

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

Put the top 5 people in the announcement please :D

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

Now we know its not tourist. cause he is not first. :P

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

I failed the system test of problem B in div2... What is the approach like?

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

    You need to traverse for some more no. of days.Traversing till n*m fails,but 2*n*m passes. It is possible that a girl becomes happy for some i~=m*n and then makes a boy happy sometime afterwards.

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

      Does 2*n*m passes guarantee that it will have correct result?

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

        I don't have the proof,can someone else help out?

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

          running till (max(n,m))^2 days worked for me...

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

          the value is (n+m-1)*n*m. the proof is pretty forward. for functions b(i)=i%n and g(i)=i%m, you have to loop n*m for all possible combinations of b(i) and g(i); as b(i+n*m)= (i+n*m)%n =i%m=b(i) and g(i+n*m)=(i+n*m)%m=i%m=g(i). Now If all combinations of b(i) and g(i) happens without a change in the state (happiness) then terminate. so worst case : 1 of n+m must change to happiness. assuming only 1 is happy at start, and is spreading to only 1 at a time of all possible combinations, so we need (n+m-1)*n*m .

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

        I think that just n*m + max(n, m) would be enough. I don't think I have a formal proof, but I tried it here, and it can be seen passing 41st and 43rd test, which were problematic: 9907232

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

        Only guarantee is n*m*(n+m). No less is a guarantee.

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

I will never use cin&cout without ios_base::sync_with_stdio(0);

I will never use cin&cout without ios_base::sync_with_stdio(0);

I will never use cin&cout without ios_base::sync_with_stdio(0);

I will never use cin&cout without ios_base::sync_with_stdio(0);

I will never use cin&cout without ios_base::sync_with_stdio(0);

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

    You can submit with MS C++ without ios_base::sync_with_stdio(0)

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

Oh sorry_dreamoon is 2nd in final result..! Because of Dynamic scoring, A problem's score is changed...

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

    Too many people failed in problem B so it changed from 500pts to 1000pts...What a sad story

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

dynamic score just to make sure sorry_dreamoon doesn't win the round

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

Why isn't that enough to check up to lcm(n,m) in the div2 problem B?

I saw a lot people solved the problem just by randomly picking large numbers like 1e6 or 1e7 etc. Why is that so?

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

    Because it's easier to throw a big number that doesn't exceed the time limit than thinking about the exact upper limit.

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

    should be 2*lcm(n,m)...

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

      Can it be lcm(n,m)+max(n,m)?

      Upd : It must be max, not min. Thanks for pointing it out.

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

        tested on some cases, should be lcm(m,n) + max(m,n)...

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

firstly congrats to haghani secondly it will be a nice revenge if you change your handle to sorry_sorry_dreamoon :)

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

Ooops... Seems like our little kid (Haghani) beated sorry_dreamoon ... !!

→ Reply
»
10 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

why did one of my solutions skipped during evaluation?

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

    Two reasons — 1- You did your coding in online ide and setting was public 2- You solve the problem as a team and somebody have same code as yours.

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

    may be you re-submitted the solution or submitted from another account before this.

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

Finally,sorry_dreamoon is beated by dynamic score.....

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

Again I failed a problem (C) because of not declaring the array large enough, I though I was over with this kind of mistakes :(

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

If it weren't for bugs in my library I would have been probably 16th and IGM ;__; (didn't manage to debug it during contest in D, already got it ACed, needed sth like 15 mins more).

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

    This is the first time I see such code.. Could you share what that is? Is it centroid decomposition? Googling for "FastrigateTree" yields no result :(

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

      Hahaha, there is no such word as "fastrigate" :D. Few professors on UW used word "fastryga" for doing some easy searches of a tree during first semesters of our studies. That is very weird polish word, I don't even know what this means and not many people know (and it's nothing related to trees or algorithms) and since I maintain my library in English I created a verb "fastrigate" for doing all standard things on trees which came to my mind :). That includes finding a diameter and its middle-edge which was useful here (but can be done in a significantly easier way than in my code, because I do many other things there).

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

Can we solve problem B div2 using graphs.I tried solving it by naming nodes from 0 to n-1 and n to n+m-1, then established an undirected edge between all nodes that can possibly meet on same day.Then for all nodes that have initial happy value 1, I start a dfs and make happy values of all nodes that can be reached 1.

But my solution failed system tests.

Can somebody tell any flaw in this strategy?

Please see my code for details.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    for(i=0; i<n; i++){
        for(j=i; j<(i+m); j+=n){
            graph[i].pb(n+(j%m));
            graph[n+(j%m)].pb(i);
        }
    }

    nop

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

      Ahh..That's stupid of me.What was i thinking.

      Changing j<(i+m) to j<100*(i+m) gets AC.

      Anyway, thanks.

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

    The idea is correct — I solved it using this way.

    Solution link

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

Luckily became GrandMaster....Thanks all!!!

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

How to solve Div1 B ? Please help .. i thought about it a lot during the contest but not able to come up with an idea to solve this one.

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

    If you have an empty cell that has only one empty cell near it, then you are 'forced' to put a 1x2 tile there. Do this for all force cells (And look if new forced cells appear after, and put them as well). If after doing this process there are still empty cells, then there are multiple solutions.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1. firstly, we fill the forced cell.
      2. It may happen new forced cells are generated. right ?
      3. Then, we will again fill those cells.
      4. Then, no new force cells will be generated. why is it so ?
      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, after a while of doing that process there will be no more forces cells. (You keep putting the forces cells and putting the new ones in a queue).

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

Problem C http://mirror.codeforces.com/contest/515/submission/9904318

My above code is generating correct answer on my system for given test case but its showing wrong here Plz help??

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

    In the '9' case you are adding two sevens.

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

      I have to add two sevens , in that test case one seven will come from 8 right??

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

        9! = 72 * 7! = 6 * 6 * 2 * 7! = 3! * 3! * 2! * 7!

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

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

    in the case of '9' you just need a line ofarr[index++] = 7;

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

in problem div1 C:

Drazil is a monkey. He lives in a circular park. There are n trees around the park.

am I the only one who first thought that it means trees which are special kind of graphs not the trees in our normal life? , funny how my default way in understanding the word "tree" became the trees which are special kind of graphs

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +97 Vote: I do not like it



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

I swear I will be in the top 5 one day QAQ.

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

Where Is Rating?Everyone Feel bore.Follow Topcoder.

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

    Contest 2 hours.1 hour system test + 2 hours update rating.

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

Can someone please tell me what's wrong with this solution of Div 2 B.

I am getting wrong answer on 5th test.

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

This is the first comment ever to break barrier of 500 upvotes and it already broke barrier of 800 http://mirror.codeforces.com/blog/entry/16446#comment-213065 :o!

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

So, here is my story:
My solution for Div.1-B failed system testing — TLE on test 15, if I'm not mistaken.
After contest I took my java code, changed Points to pair<int, int>'s, changed queue to C++'s, submitted — and got AC.
So the question is — do I need to forget about using Java in competitions?

UPD: To compare: C++ — 9905626 and Java — 9896943.

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

    На создание объектов в Java уходит больше времени, чем на создание записей в C++. Особенно это заметно когда создается много объектов.

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

    You just need to adapt by using as few objects as possible. For example, instead of Queue.add(new Point(x, y)) use Queue.add(x); Queue.add(y);.

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

      PlayLikeNeverB4, As far as I know Java, the way you said to it, each time x and y will be wrapped into two Integer objects, cause you cannot make a generic queue with primitives.
      Enavik, Of course it takes more time to create objects in Java, but for this purpose TL for Java is twice the TL for C++.
      The thing is that I always thought that Codeforces is such a website, where I don't need to worry about small optimizations when my solution is correct...
      And I think that for this problem TL was really too strict — a lot of solutions failed systests due to TLE.

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

        Another thing is to use arrays. When you have an array (or queue) of pairs, just use int[N][2]. You can even sort them if you want.

        I used to have problems in the past because of the language, but that thought me to be more careful. When it's an important competition I stick to C++ though :)

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

        r this purpose TL for Java is twice the TL for C++.

        Sure?

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

When will the editorial be put up?

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

longer than 100 minutes and I 'm waiting for my rating updated -.-

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

Good luck to tourist with reading his PMs, I guess there will be a lot of questions like "Are you sorry_dreamoon, plese tell me, I won't tell anyone else :)" :D :D :D

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

sorry_dreamoon writes jokes in the head of each submission... 9885853 9893183 9895490 9898972

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

    First one of the jokes is very funny :D

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

    Sees the last one...

    Immediate Persona and League of Legends flashbacks. Them puns.

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

Nice contest, nice problems. Hacked for the first time in my life :)

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

I think Div2 ranks are lost :D lets repeat the contest

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

Thanks dreamoon_love_AA for nice contest I enjoyed the contest and most important thing that I gained +228 :D

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

I really enjoyed the contest today and reached Div1 again :)

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

Can someone explain me why in the final standings my rank is 340 but after the rating update it changed to 626? It's not even close to 340 :( Thanks!

Edit: Nevermind, the issue was solved!

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

In problem A, if you print "yes" in case of "Yes" will it be accepted or not?? Somebody wrote "yes" and he got it accepted??

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

    Why ask when you already know the answer? :)

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

I enjoyed participating a lot. However my submissions were judged incorrectly in pre-testing phase itself.

See here: 9902412 9902094

Can anyone tell me why this unexpected behavior occurred?

How do I contact the organizers for correction?

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

    It' my mistake :'( You should get some message like "your output may contain invalid character". But When I write checker, I will output this message when read invalid character.

    you should not add '\0' to string.

    → Reply