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

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

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

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

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

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

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

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

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

"[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 :)

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

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

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

Petr possibly be sorry_dreamoon , the program in java .

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

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://codeforces.com/contest/498/standings :D.

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

    You aren't there!

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

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

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

    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.)

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

      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

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

    Why not Egor ?

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

    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.

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

      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!

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

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

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

nice today!!!!

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

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.

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

I'm dreamoon' for math!!

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

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

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

sorry_dreamoon reading comments:

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

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

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

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

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

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

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

    holy mother of formatting.

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

    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.

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

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!

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

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

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

Wish score distribution won't be DYNAMIC...

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

    ...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.

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

GL & HF to everybody!

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

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

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

Does peter50216 have any CF account?

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

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

deleted

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

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

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

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

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

Thank everyone this round was very interesting!!!

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

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 :)

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

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

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

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).

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

Why does Div. 1 start 5 minutes later?

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

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

Thank you very much!

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

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

Первый раз пишу под Ubuntu, может кто-нибудь подсказать, как копировать/вставлять в консоль CodeBlocks?

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

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 :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
9 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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

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

    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

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

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

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

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!

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

Почему в A div1 N <= 15? Есть решения, которые будут за линейное время работать, ну или, в крайнем случае, за квадрат, то есть N можно было спокойно ограничивать 10^3 или 10^5, но никак не 15.

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

    Чтобы натолкнуть на неверные решения.

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

    Можно, например, вместо строчки считывать long long. Зачем делать большие ограничения, если идейно задача от этого не изменится?

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

    Да ладно, пускай задача А будет лояльной по ограничениям, она же А. Хорошие ограничения, чтобы желающие могли написать переборчик — 9886986, или же так — 9891585, или даже увидеть в ней несложную динамику — 9888532:)

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

It's time to back to the old color.

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

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

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

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

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

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

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

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

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

        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.

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

          Use "Custom invocation".

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

          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

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

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

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

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

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

Good bye Div-1!

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

sorry_dreamoon is no.1 in Div1!

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

    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!

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

    Maybe he really is the Petr...

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

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. :(

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

Was D div 2 a bipartite matching problem?

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

    The constraint leads to topological sort, I guess.

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

    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.

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

    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).

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

      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

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

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

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

        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.

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

          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)

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

            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)

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

Огромное спасибо за интересные задачи и такие возможности для взломов :D

Лучше контеста у меня еще не было!)

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

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

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

It seems that sorry_dreamoon's identification will remain a mystery

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

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

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

sorry_dreamoon became 1st again!!!

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

минуты не хватило до submit C.

там ведь слоеные списки по min (x- 2h), и max (x + 2h), с хранением индексов, которые дают эти максимумы. Как обработать ситуацию когда одно и то же дерево дает и max и min? у меня была какая-то странность с этим.

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

    Не очень понял, что за списки, но это задача почти в чистом виде задача поиска подотрезка с максимальной суммой.

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

      Списки для ответа min/max на отрезке за O(1).

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

    Рассматриваем значения 2h+х и 2h-х. Для выбранной пары деревьев ответ является суммой первого значения для правого дерева и второго для левого.

    Дальше дерево отрезков с максимумами всех трех значений (2h+х, 2h-х, ответ). Тогда ответ для вершины при построении — это либо ответ левого сына, либо ответ правого сына, либо (если выбранные деревья в разных сыновьях) — сумма 2h+x справа и 2h-x слева. Аналогично с merge нескольких вершин при поиске ответа.

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

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

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

Очень красивая задача С (див.2) про факториалы! Спасибо:) Истинное удовольствие от анализа условия!

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

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

of course, if I pass system test..

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

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

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

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

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

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

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

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

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

Put the top 5 people in the announcement please :D

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

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

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

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

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

    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.

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

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

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

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

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

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

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

          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 .

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

        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

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

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

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

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);

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

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

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

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

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

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

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

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?

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

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

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

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

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

why did one of my solutions skipped during evaluation?

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

    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.

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

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

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

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

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

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

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

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).

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

    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 :(

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

      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).

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

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.

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

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

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

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.

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

    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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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 ?
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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).

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

Problem C http://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??

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

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

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

Как решать D(Div 2) / B(Div 1)?

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



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

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

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

Where Is Rating?Everyone Feel bore.Follow Topcoder.

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

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

I am getting wrong answer on 5th test.

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

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

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

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.

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

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

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

    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);.

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

      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.

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

        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 :)

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

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

        Sure?

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

When will the editorial be put up?

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

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

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

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

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

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

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

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

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

Не ищу простых путей. В Div1/B вместо того, чтобы проверять появление новой "плохой" клетки я выбирал особый порядок обхода.

Сверху-вниз, справа налево — WA10 Сверху-вниз, справа налево, повторить 20 раз — WA36 От каждого из четырех углов по диагоналям — WA19 От каждого из четырех углов по диагоналям, 20 раз — AC. (достаточно 3).

Вопрос, есть ли какой-то тест, чтобы новые "плохие" ячейки попадались хитрее, чем в наборе тестов?

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

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

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

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

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

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

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

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!

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

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??

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

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?

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

    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.