Zlobober's blog

Codeforces Round #345
By Zlobober, 9 years ago, translation, In English

Hi everybody!

Glad to tell you that tomorrow on 9:05 UTC there will be Codeforces Round #345. The round is formed of the first day of X Moscow Open Olympiad problemset with several additional problems created for this round. This round is brought to you by the scientific committee of Moscow Programming Olympiads controlled by GlebsHP, romanandreev and your humble servant, and also with a great help of fcspartakm who helped us make a complete problemset of our problems.

The round will be conducted under the standard Codeforces rules, you will be given 5 problems for 2 hours. Yes, this round is rated :)

Note that because of holding the main onsite round system testing and upsolving will be available no earlier than 12:35 UTC. Also we would like to ask you to not discuss problems in comments during the time between the end of the round and the end of the onsite competition. All comments with discussions will be removed and the most active violators will be punished. Thanks for your understanding.

UPD Sorry, the round start was moved to 9:25 UTC. It is not easy to run onsite round and Codeforces Round simultaneously!

UPD2 You may discuss the solutions! System testing will be run shortly.

UPD3 The editorial has finally appeared: http://mirror.codeforces.com/blog/entry/43677 Sorry for the delay!

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

Comments Comments (296)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it +109 Vote: I do not like it

And Zlobober's serious work to get the first place in the contrib list!!

Nice tag (best way to spend Monday)!! good luck;

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

    But seriously though, who holds olympiads on Monday mornings?

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

      I can't imagine a better way to start your Monday.

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

        great minds think alike.codeforces makes my life better

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

please change the contest time in this time in iran we are at school and we have Combinatorics class with Dr jamali (for informatics olympiad)

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

    At any other contest time , someone else in the world might have Combinatorics class with Dr jamali (for informatics olympiad) . Ever think about that ?

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

      Well, I doubt Dr. Jamali goes around giving Combinatorics classes the whole day, every day. For sure Jamali must take some time to rest, teaching must be exhausting.

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

    It could be worse. It is going to be at 6:00 AM in my country.

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

    Same here!!

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

A better reason to leave Lecture :) .

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

Russian contests are always good!

Specially when this team( Zlobober + GlebsHP + romanandreev) are authors !

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

First thank all people who prepare this contest. But i think the start time of contest is not good for iranian coder (or maybe for another coders who live in another countries too),bacause on this time we are in university... :(

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

    oh my god!why vote negative??? :O

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

      because it's CF :D

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

      i can't believe this (O-O)!!! why???! 19 negative vote !!!for what??? -_-

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

        Because every time will be good for some participants and bad for others. This time you had bad luck, other times the contest will be in good time for you and bad for others.

        Life is hard

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

          i just said its bad for IRANIAN coder!

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

      No matter what time they set the contest to start, it would be inconvenient for someone somewhere in the world

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

      I can upvote your very useful comment

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

Please postpone contest, I'm still at uni :'(

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

    10 minutes delay, they did what you want :)

    UPD: another 10 minutes, please come home quickly

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

Just came back from school and about to start the contest. I like these rounds with unusual times because I can actually compete on weekdays. Normally, they're hosted at 10 pm or 11 pm in my country's time :(

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

Rating!? Oh no! Sad end for my cat...

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

the timing of the contest is probably one of the best timings for competitors from Korea; it's 6pm; an hour or two from now (so, 7pm or 8pm KST) would be ideal.

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

    It's 3am on a weekday in the US :P Oh well, better than 10am — at least I have a chance to participate. Looked like it got bumped back 10 minutes though.

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

delayed for 10 mins

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

    delayed by 20... :(

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

    I'm disappointed too. It was just that I would complete the contest and go to school, now I have either to skip the first class or solve for only hour and a half :(

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

      Why are you disappointed? you have a reason to skip the first class now :D

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

        You might want to tell this to our history teacher :)

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

          History is a lie, Contest is real :D

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

          You want to attend history class! what's the matter with you :D

          when I was in school I always skip history classes even if there's no contest :D

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

          If it were about a Math or Info or Physics class, maybe he would have been more rational, but in this case, man, I'm sorry for you :))

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

          All of you didn't understand. My history teacher will surely kill me for being absent(it's sad because I'm a math/informatics competitor, history is one of my worst subjects :)) ).

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

    暴走漫画。。。。。

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

      no zuo no die

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

      Hey guy ! why so many people got unhappy with you !

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

        Because it's CF :D Maybe most of the people who got unhappy with him is Chinese. Why? I don't know QwQ

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

        All are unhappy with anyone comments in language different from English..

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

          I'm sorry.I don't konw it before.

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

Guys, I must go to school today ;)

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

    Same — could've gotten 20 mins more sleep. Some of my classes probably are unimportant enough I can use them as nap time though :) Bets it will be delayed 30 mins?

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

5pm in China. Hungry... Please start...T T

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

    but it's so nice to take part in the contest during the day for Chinese=w=

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

I haven't slept all night last night and Just got back from my university to participate in this round :D

I hope there will be interesting problems.. I am feeling like being Div1 for a while :p

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

    such high , much wow all the best

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

    For me writing after a sleepless night is premise for falling rating=(. Hope it is not your case, good luck

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

      Well... I'm not in my best shape.. but I need to get used to coding in stressful environments, because I am preparing for ICPC WF this year, which is my final year as a contestant :((

      any way I only hope the problems are enjoyable that's all :D

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

    I'm feeling the same as you and dropped from #150 to #800 due to int overflow in the last contest T.T

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

    I'm actually glad for the delays :D now I can change my clothes and get into my comfortable pajamas, drink a cup of tea, as well as write this comment :D :D

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

    you did it :)

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

      Yes! Thank you ^_^

      I Also got my best rating so far with 1944 points :D

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

Why are you delaying the start time? u.u

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

10min delay?!
We can, we do, we practice :(

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

Another 10 minutes? :O :/

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

On one hand if I complain about timings, Russians will downvote me, on the other, if I don't and still participate I'll miss my lunch(and get downvotes). Hmmm.....what to do

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

My first time to participate a CF round sync w/ onsite.It's cool!

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

Should I compete? Because I am in a Lab class and my teacher gave me an "1 hour break!" for completing the tasks early.

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

Waiting for the next delay :P

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

what's wrong with the hacking? nothing shows up when i try to hack (sorry for my vulgarity on my previous post).

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

    Its because you shouldn't be hacking. Solve problems, go go go!

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

    I have a similar problem. Pretests passed but cannot lock! Neither is it showing on the dashboard.

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

    It was unuvailable for ~10 minutes. It affected all the participants, so all of you have been in the same conditions. Sorry about it.

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

      Wow.It seems that there are many guys who are unsatisfied with the long time of waiting.

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

      I wonder, who downvoted the boss???

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

First time i solved C in contest . guess what i solved B and C. and 4 WA on A and could not get AC. Awesome problemset :)

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

    I think it is because of unclear statement. Almost sure it is the case if you get WA on pretest #7.

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

Can somebody explain me This ? Whats wrong with my generator .

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

The statment for the second task is pretty clear, but again I spet 30 minutes to understand problem of the task :D

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

we should wait till 12:35 for system testing,right

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

when will system testing start?

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

    In an hour from now as I understand (15:35 MSK).

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

We kindly ask you not to discuss problems or solutions since the onsite round is still running. We will notify you when it will be allowed (approximately in 2 hours). Thank you!

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

UPD Thank you for your understanding! You may now discuss problems and solutions. System testing will be run shortly.

UPD Спасибо за понимание! Теперь вы можете обсуждать задачи и решения. Системное тестирование скоро начнётся.

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

    Two questions:

    When will start testing ?

    Why disscussing is so important, when everybody can see codes from other participants ?

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

      Exactly..

      I guess that the onsite contestants cannot have any kind of communication with the outside world..

      So why bother stop discussions here? I can't see the point in doing so :\

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

    I can see the other's solutions.

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

    Any updates on system testing now ?

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

i still do not understand the problem statement for division 2 D, but judging from number of people who solved the problem, perhaps it's just me who is confused about the problem statement.

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

Seriously? -_-

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

    So, were there edits in the problem text?

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

    Let me clarify this. We actually received a question pointing to the typo in the statement (the word "has" was obviously an extra word there) and we fixed that typo. After 1.5 hours of contest we received the second question about the mistake in this problem and we didn't even think that you are talking about that mistype. After all, it was a small typo that doesn't affect the understanding of the problem, and we fixed it 1.5 hours ago, we almost forgot about it.

    Of course we didn't have any intention of lying to you or whatever.

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

What is Compilation error? I lost much time because of that...

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

    Are you kidding?

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

      I had not gotten Compilation error and today is first in Codeforces. So i don't know Compilation error well.

      I only know this.

      struct A ={a,b} => Compilation error A.x = a, A.y = b => Correct

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

        {a,b} this would work with std::pair not with struct

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

        There is no = operator by default for custom structs.

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

          You are wrong. It can be auto-generated by compiler.

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

          Yes, there is. In C++11.

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

            Click

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

              You didn't write constructor for two int values. So compiler doesn't know what to do. Click

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

              The problem is that you've written you own (empty) constructor for your struct. If you'd write no constructor, just:

              struct smth{
    int x, y;
};

              it will work.

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

    Candidate master asking about Compilation error >.<

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

    Ya.. Me too..!! And can you believe, they are asking us to code a solution.!!! I lost so much time in that.!

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

    http://bfy.tw/4cfa

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

A bit difficult for me.But I'm sure I can do better.hard work will pay off!

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

    Also!I'm not in my best condition. I got Wrong answer 2 times in A and C,and 1 in B. Oh my god!I lost 250 point! Even more...the Internet shut down in the contest.

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

first time take part in div 1 =w=

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

Had someone div2 C WA 3? Can't understand where is the problem.

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

I Can't Wait... When will the Final test...

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

    Beresta said:

    In an hour from now as I understand (15:35 MSK).

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

    It's in the announcement: "Note that because of holding the main onsite round system testing and upsolving will be available no earlier than 12:35 UTC."

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

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

    What is reason that we are still wating.

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

      'the reason'.I'm sorry.

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

        Protip: you can edit your comments by clicking the button that says "Edit" (surprising isn't it)

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

    why are you waiting? you didn't participate as I can see.

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

    available NO EARLIER than 12:35 UTC...

    Only GOD knows how much do we have to wait.

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

    Quite funny picture...

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

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

Round must be made unrated. We couldn't hack or lock solutions for ~10 minutes.

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

everybody should give a chance to submit the problems that went wrong in pretest as system test is not running. just asking

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

Why do codeforces problems differ so much in nature from ICPC problems? I think ICPC problems are too hard to think :/

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

    Not really... You should compare ICPC problems to Div1 contests. and both are pretty darn hard :D

    I believe Div2 contests are comparable to easy regionals

    You should also consider teamwork in ICPC and much longer contest time (5 hours). This means more problems can be solved.. So can you see why it requires harder problems to make a good ICPC contest?

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

      How effective do you think Codeforces problems are for preparing for the ICPC? Am I better off focusing more on solving on SPOJ, UVa, etc?

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

system testing started ! hold your nerves !

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

System test is started. Feel free to discuss problems. Sorry for delay.

===

Системное тестирование запущено, можно обсуждать задачи! Приносим извинения за задержку.

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

    How long to wait for editorial ?

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

      I'm sorry but this will be a round with delayed editorial. All editorials for problems will be posted no later than March 9th, most probably on March 8th evening.

      You may find brief ideas for the problems by simply asking in comments for this post.

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

    When can I view other people's solution?

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

How to solve C? please someone tell me briefly

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

    Briefly — after simple math (square, equal, cut) we get that valid pairs have either equals X or equals Y. Put every value in counting dictionary/set/whatever and get sum.

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

    I couldn't participate, but I have read the problem and I think you can use a hash table (C++ map) for X and another for Y, and count how many individuals have each X and each Y. Then traverse all those keys and for each one, if the count is N, add to a global counter N * (N — 1) / 2, which should be the number of pairs you can make out of N watchmen.

    Then you should make sure not to count twice or to subtract the individuals which are the same X and Y, which should not be difficult.

    And as somebody said in another comment, use long long.

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

    While it took me about an hour to read, think and code Problem C, someone on earth solved it in 0:01 min.Just saying.

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

Welcome to Problem D test 35 .

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

What was the hacking case for A?

For B it was int32 overflow.

UPD: Damn, I've messed with tasks again. I meant int32 overflow hack case for C.

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

Damn these overflows got me again on C. Need to still wait more to get 4 correct in a Div 2 contest :(

WA: http://mirror.codeforces.com/contest/651/submission/16569379 AC: http://mirror.codeforces.com/contest/651/submission/16582445

I should start to use #define int long long probably

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

    You would get Compilation error

    The function main must return int value

    i did it once, and costed me two hours of debugging :3

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

      use signed main()

      #include <iostream>
using namespace std;
#define int LL
#define LL long long int
signed main() {
	int a=12345678912345678;
	cout<<a<<endl;
	return 0;
}
      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too :( F***ing overflow.

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

Why can't I see the tests?

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

I need some help regarding Div2 C.

I did it following way:

I found out the number of distinct horizontal and vertical lines and count of number of points for each horizontal and vertical line. After that simply we can form pairs for each line by using n(n-1)/2 and keep on adding it to the final answer.

But I've a problem that this way I can't remove the duplicate points and each duplicate will be added twice in my answer.

Any suggestions regarding a faster method to find similar points? (The best I know would be simple brute-force and that will be running in a time which violates time constraints?)

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

    Use another map to count number of points in the same position (can use map<pair<int,int>,int>), then for each position, subtract the result for n * (n - 1) / 2 with n is the number of points in each position.

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

    I used a map<pair<int,int>,int>. You could also sort all the points by (a.x <b.x) and by (a.y < b.y) when (a.x == b.x). After that you can count how much points are equal in O(N).

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

    If you code in C++ read about std::map.

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

    I didn't use map and got AC with arrays. So, one array of pairs for (x, y), two arrays: one for X and one for Y coordinates. Sort them all, and then you can calculate easily how many of them are with same X or Y coordinate, while tracking how many of them coincide.

    16585770

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

Thank you for fast rating updates :D

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

Waiting for system test was like riding a roller coaster for me. And I did have GREAT fun when I knew the results!

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

Memory Limit 256 MB , memory used 255 MB

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

Congratulations to tourist on his best performance ever — today he got +172, beating his previous record of +162 (which was set back in 2010, in CF Round #8).

One more round with such inflation and we'll see 4000+ :)

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

    Feels wrong that #1 person placed #1 in tournament get so much points.

    Why TooDifficult got only 84? Its 2 times lower.

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

      He got 2 times lower place :P

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

      I think it's because the round was really stacked because of the time; a lot of great asian coders participated who couldn't otherwise, and only the more dedicated coders from other continents participated (or the ones who don't have school this week hehehe)

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

Bredor where is your scrincast with russian rap?

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

In my previous CF Div2 (#343) round, I managed to solve only 1 problem and had a ranking of 2400. Today I could successfully submit 2 problems and had a ranking of 1700. Which implies an increase of 700.

My rating still fell down today. I've no clue as to why is this happening!

Improves from previous round and still rating decreases! :SAD: :(

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

    Well it seems you have participated in too little rounds for your rating to stabilize.

    Also it is not really depends on the place number, but rather on the amount of participants, their quality (rating) and your relative position among them. E.g. if contest have only 100 participants and you placed #100 — its worse, than if contest have 10000 participants and you placed #8000. But also if in first case other 99 would have rating of 100500 you probably won't lose anything (maybe even get higher), but if everyone of them have rating of 0 you will fell down pretty heavy. Hope you got the idea.

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

    What do you love more — Problem Solving or seeing positive rating changes ?

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

Problem E turned out to be surprisingly simple. For example, in the example below, the following works:

  • Remove 7-4 -> add 7-6
  • Remove 9-4 -> add 9-1
  • Remove 4-6 -> add 4-5
  • Remove 3-5 -> add 3-1
  • Remove 5-6 -> add 5-9
  • Remove 6-1 -> add 6-3
  • Remove 8-1 -> add 8-5
  • Remove 10-2 -> add 10-5
  • Remove 2-1 -> add 2-6

(We need a slight modification when the two trees have common edges, but this is not very hard.)

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

    I don't get it. What is the pattern I should see from this example? I am very curious how to solve E because it doesn't seem that hard (you have a lot of freedom when doing operations), but still, I am unable to create an algorithm that works all the time. Can you explain exactly how you solved it? (just the main ideas)

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

      The main idea of one of the authors solutions is working with leaves. Consider a leaf u with its edge (u, v) in the first tree. There are two cases: if the edge (u, v) is present in the second tree, it should stay as is and we can contract this edge forming a new vertex uv in both trees. In the other case we should find any of the edges going out of u in the second tree, let's call it (u, w), and replace (u, v) with (u, w), and after that contract u and w. Note that all v, u, w may be contracted vertices and should be dealt carefully (in particular, the endpoints of removed and newly added edge may be distinct though they belong to the same contracted vertex u). This leads to an O(nα) solution.

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

It seems that smth is wrong with Java invocations. If the parameters are set correctly, it should be impossible to get ML in this language: it will be either TL because of long GC, or RE because JVM cannot allocate more memory. However, I've got ML for the following solution 16574238. It consumes at most (1M (input) + 2M + 2M (edges) + 1M + 1M (dsu)) = 8M int's, 1M boolean's, 1M ArrayList's of total size up to 2M, 1 ArrayList of size 1M. In total it is up to (8 * 4 + 1 * 4 + 1 * (8 + 4 + 8) * 2 + (8 + 4) * 2)M bytes, which is way below 256Mb. Of course there are plenty of temporary variables, but they should be safely garbage-collected. Unfortunately it doesn't show me the test, so I cannot debug what's going on there.

So the question is, how are memory params (-Xmx etc.) set for for Java on server? If they're set consistent to the problem ML, then MLE verdict should be impossible. Am I missing smth?

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

    And another data point. Apparently GC behavior on server is very weird. E.g. the following code:

    public class Main {
    public static void main(String[] args) {
        int[] churn = new int[50 * 1000 * 1000]; // Allocate <200MB.
    }
}

    consumes 194Mb as expected. But the following code

    public class Main {
    public static void main(String[] args) {
        int[] churn = new int[50 * 1000 * 1000]; // Allocate <200MB.
        System.gc();
    }
}

    consumes 472Mb! And another experiment: the following code 


    public class Main {
    public static void main(String[] args) {
        int[] churn = new int[50 * 1000 * 1000]; // Allocate <200MB.
        churn = null;
        System.gc();
    }
}

    consumes 292Mb.

    This essentially means that if GC triggers, all ML's for Java are divided by 2. I think Java/GC configuration on servers needs some serious adjustments...

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

      I remember someone already pointed out in comments that CF uses Xmx 512MB.

      Also this submission: 16585600 and 16585728 looks like Xmx is indeed 512MB.

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

        So, the memory limit verdict happens when the launched jvm goes OOM?? As such -Xmx corresponds to the max heap memory, apart from this there are other sources of memory consumption for a java process, Different GC policy for sure would reveal different memory usage pattern, like in JAVA8 if you call System.gc() in a loop when G1GC is your garbage collection strategy then you would observe that the given java process keeps on incrementally consuming more and more memory without going OOM (consumed memory might be part of native memory area.)

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

Can somebody post brief explanation of Div.2 E/Div.1 C ?

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

How to solve Div2 D ?

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

    First precalculate how much time it would take to reach from 1st picture to ith picture while doing right swap each time for each i from 1 to n. Similary calculate time to reach from 1st photo to last picture while doing left swap each time.

    Then for each position from i to n while going right, you have to find the maximum position you could reach on the other side (left), this could be found using binary search. Again the same for left to right.

    Complexity: O(nlogn)

    My solution: http://mirror.codeforces.com/contest/651/submission/16580683

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

      I implemented this too, but I think it's possible to do in O(N), because if you try to find the max position you can reach on left, for each i, then it will be at most the position for i - 1, and hence you can use something like a two-pointer technique (or sliding window if you prefer that analogy) to do it in O(N).

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

anyone can tell me the tecnique of div2 c ? plz...

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

    Manhattan and euclidian distance between two points is same when at least one coordinate of both the points is equal. You can prove this by equating both equations. Then you can use map to store count of occurrences of each x and y coordinate. Use another map to store count of pair(x,y). You can find answer by adding gC2 for each x and y ( g is the count of occurrence of each x and y coordinate stored in map). However some points may be repeated in the input and so you will add those pairs in the answer twice once for x coordinate and once for y coordinate. So just use the map used to store pair(x,y) and for each point subtract countC2 from answer ( count= number of times given point appears in input).

    soln : http://mirror.codeforces.com/contest/651/submission/16566465

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

    First, let us assume A = |x(i) - x(j)| and B = |y(i) - y(j)|. Then, Manhattan's distance = A + B, and Daniel's distance = sqrt(A ^ 2 + B ^ 2). Solving this, we get 2 * A * B = 0, which means that either A or B is 0. So, all such pairs of points which have either the same x-coordinate, or y-coordinate are to be counted. So, we sort the array according to x-coordinate and then for each unique value of x, if the number of points have that x is N, then we add to the total the value N * (N - 1) / 2 as that is the number of ways of selecting 2 points from all N points(NC2). Then we do the same for y after sorting the array according to y-coordinate. But, here there will be 1 problem that we will have counted those pairs twice which have both the x and the y coordinates same. So, to remove this, for each point having coinciding points, if the number of coinciding points is M, we subtract M * (M - 1) / 2 from the total.

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

It's already frustrating...In div1, we can't see sources or tests. Please fix this issue: I really want to find my bug in div1D

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

Again failed C because of overflow ( lost 1200 points ).
What do you do to avoid overflows ?
I tried #define int long long but thats throws an error main() must return int

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    #define int long long

main(){
    return 0;
}
    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't use it but you can try this:

    #include <bits/stdc++.h>
#define int long long

/*
 *  Something
*/

#undef int
int main() {
    #define int long long
    /*
     *  Something
    */
    return 0;
}
    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Or you can use int32_t instead of int :

    #define int long long
int32_t main()
{
}
    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It is better to define (before the contest)

    typedef long long ll;

    and just use ll everywhere instead of int (except main() type, of course). Speed disadvantages are minor, and at the same time you will get overflow very rarely.

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

      Hell No !

      i remember getting lots of ML and TL because of this the best way is to use ll only when it is needed but when u wrote ur code and u suddenly find out about the overflow u can simply define int long long and change int main() to main()

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

        Probably on some hard div1 problems (C-E) you can improve wrong solution from ML/TL just using int where long long is redundant. This problem seems unlikely to me on div2A-D, it can happen only when your code is very suboptimal. I'd like to see counterexamples if I'm wrong.

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

          Well since you asked for a counterexample :P

          ML exceeded code(in method solve2) : 16439466

          Accepted code(just changed type of array board from long to int in method solve) : 16439508

          PS : the method names are different because I had just removed the unused method solve before submitting again.

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

            You have three big arrays: Cross[] allcrosses, long[][] board and long[][] sum, other are not greater that a couple of MB. It is interesting why it is ML, because maximal size for each of them is 4*10^6 elements, long is 8-byte and Cross is 4+4+8=16 bytes. So total used memory should be ~4*10^6*(8+8+16)=128*10^6 bytes. In theory. Maybe I don't know something about Java to configure the cause of this doublesizing in practice.

            However, as I said, ML here is the result of suboptimal solution. You needn't store all crosses, only positions and values of the two current best crosses.

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

could someone here explain what division 2 D / division 1 B is about? i had a hard time understanding that question and still have hard time parsing the problem. in particular, in the beginning is all the images in vertical direction? so only cost you spend is when we need to rotate image that is in the horizontal direction? i'd imagine you need to go left or right depending on some kind of 'measure.'

what's the solution concept? is it some kind of dynamic programming, or is it something completely different?

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

    I didn't solve D but I can answer your queries about the problem .
    You view the images on a phone which is initially in the vertical orientation , so if you encounter an image which is of the opposite orientation than your current phone orientation you need b seconds to change the orientation of your phone .
    UPD: My bad !

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

      This is wrong, you are not allowed to rotate phone, only pictures. Trying to rotate phone because I read problem before clarifications is why I'm orange now :(

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

Regarding question C Watchman. Codeforces says wrong answer on test case 3 as wrong answer expected '33', found '39' But my computer machine gives the 33 answer and on codeforces the same code giving 39 answer on 3rd test case ..I also cross check on Iedone.com .It also giving me 33 but codeforces give 39 and hence not accepting answer ....please have a look to my submission no 16580949 or visit my submission ..pls help ..

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

    Yeah, pretty weird. Let me check...

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

      Did you find any error ?

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

        It seems right. In my PC give 33 too. I don't know! Make sure you don't have unespected runtime error. I heard sometimes system give WA but is RE instead (also in ACM ICPC Regionals).

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

    // while(i < n && v[i]==v[i-1]) // while(i < n && v[i].first==v[i-1].first) // while(i < n && v2[i].first==v2[i-1].first) remember to check the boundary when using while. BTW, I really don't like your coding style

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

I mean it IS obvious, but still... is tourist even human anymore? :/

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

Could anyone help me find the bugs in my code of Problem C(Div. 1)? It always got TLE on test #14 and I am confused about it....

Here's the code, Click

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

Is it possible to solve div2A with the formula? The 2 steps forward, one step backwards thing looks too darn familiar...

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

    Click.

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

      Thank you.
      By the way, I've found an interesting solution that uses DFS!
      div2A — DFS

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

      How did you come up with that?

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

        This is sentews2's code.
        I don't know whether he'll answer your question, so I'll tell you my version of the story.

        First, take a look at this rain water barrel:

        You see, there are 2 paths for water to go out. The throughput of the lower tap is 1 liter per minute and of the upper tap is also 1 liter per minute. Let's imagine that, when we open both the upper and the lower taps, the barrel will lose 2 liters of water every minute.

        Now, we'll do the following trick. Let's connect the upper tap with the hose and return that water, running from the upper tap, back into the barrel. On one hand, the barrel still loses 2 liters of water every minute, but on the other hand, the barrel now gains 1 liter per minute from the upper tap. This image clears the things out for me, so I can see that the barrel now loses 1 liter per minute in total.

        The key moment, I think, is to consider the whole system. That is, how much water (or energy, in the case of the div2A problem) does the whole system lose? If we think about the joysticks as a single system containing some amount of energy, we see that the amount of energy contained in that system is a + b and the system loses 1 unit of energy every minute.

        If we could just drain the energy from 2 joysticks to 0, the amount of time the system would survive by losing 1 energy unit a minute is a + b minutes. Since we cannot drain it to 0, when we are getting close to complete exhaustion, the internal structure of the system of 2 joysticks becomes important, i.e. the distrubution of energy between the two affects the answer. Exactly for this reason, we should also consider all the cases of relative energy distribution in joysticks (when energy is near 0):
        0 0
        0 1
        1 0
        1 1

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

        I think it is simply a DFS on states! The states are acyclic you can prove it on the basis of transitions( They only take you to larger or smaller number) . Hence the states form a DAG. But there might be multiple ways to reach a state I cannot understand how is he taking care of that! I think if we can prove that the first time we reach the state, the value we maintain is optimal then we can prove his solution! Edit: Yeah If I change that max taking condition to work only when we visit the state at first it gives AC then too. So probably anyone who can prove the hypothesis by me can prove the solution :) Any Red People, correct me if I am wrong?

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

        We can notice that: if the remainder abs(a — b)%3 equals 0, it would keep 0 after each minutes. Otherwise, it can change between 1 and 2.

        For the first case, the final state is (0, 3) or (3, 0). (why no (0, 0)? because ever time the total energy would lost 1 percent, but we can't get (0, 1) or (1, 0))

        For the second case, the final state is (0, 2) or (2, 0).

        So the answer is max(0, a + b — 3) or max(0, a + b — 2). 16601248

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

    I used a recursive function:16582603.

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

I wonder if tourist is going to reach 4k this month. Just looking at the slope of that curve.

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

    Seems like new rating system is more appropriate for those who often takes top1. tourist did the same good for a few last years, but there is no such jumps on the graph like for last 4 contests.

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

Is there any editorials?

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

Bring a new rating category, tourist is close to breaking 4000 limit :D

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

Can anyone please explain the idea of Div1/C or Div2/E ?

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

    build a graph G with n * m vertices that each of them correspond to a cell in the table. add an edge from vertex u to vertex v if u and v are in the same row/column and a[u] <= a[v];

    now find every SCC of the graph and create a new graph H in which every vertex is a SCC of G. note that vertices of a SCC of G should have the same number in the final table. now find the topological order of vertices of H(I leave it to you to prove that there is a topological order for vertices of H). the vertices that are not endpoint of an edge(note that since the edges are directed, start points and end points are different), can be assigned value 1. erase those vertices from H and assign values to the other vertices recursively.

    note that this solution uses O((nm)^2) edges to construct graph G. you need to use some ideas to reduce the number of edges(I leave it to you).

    let me know if you need any more help.

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

I'm already sure that you forgot to let us the permission to see the tests or someone's else source (as we don't have the permission during the contest). Please let us. I've been looking for a bug in my source for a couple of hours and it'd be much easier if I could see the test (as we usually can). It's my third comment about this problem ans I hope someone will see it. I don't know where to post it...

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

    badass is here for help

    try this test

    8 10
28 97 4 46 44 31 35 21
6 88
7 71
5 94
1 84
3 91
2 61
1 59
3 43
1 73
2 82

    correct output:

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

      I've just found what's wrong but I don't know exactly how to solve it now. I may have an idea but the code is already very hard to understand and it's very complicated what I want to do. I think I'm going to quit. Still, badass, can you tell me what is your idea?(BTW, I guess you've just found a new nickname :)) ) Actually, I'd like to hear ideas from anybody about div1D. It seemed really nice at the beginning(the answer is either M — 1, M or M + 1 where M is the maximal length of a maximal increasing subsequence). Now I've tried to check whether is M + 1 (this was easy). Now I have to check if it is M — 1 or, if not, to print M. But my idea for checking whether M — 1 or M is a solution is very hard and I'm almost sure that this is not the solution.

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

        Let the length of longest increasing sub-sequence(LIS) in original array(before any update) be S.

        we need to find for each element in the array whether it's included in at least of the LIS or not, and if yes does removing it will decrease length of LIS by 1 or not.

        let L[i] be length of LIS ending in i and R[i] length of LIS starting in i

        it's clear that if L[i]+R[i]-1 == S then element i is included in at least on of LIS, now how to know if we remove i then S will decrease or not?

        it's a bit tricky, removing i will decrease S if and only if there's no j such that element j is included in at least one LIS and L[i]==L[j] (i.e. element i is the only element which have the value L[i] among all element which are included in LIS)

        after we know for each element if removing it will decrease S or not it's easy to answer the queries now :)

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

          I've just got AC. I made the arrays L and R as you said but for being sure wheter its elimiation decreases S by 1, I used some hashes(yep that's right=)) ). I just counted in how many ways optimal L or optimal R can be built and it should be equal to the total number of optimal increasing subsequences. Anyway, thanks :) I understood your observation and it is a better solution(because mine can give a wrong anser in case of collision)

          LE: I've implemented your idea and got AC: faster and shorter code. Thanks :)

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

          Nice :)!

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

          Nice solution! I was struggling to get track of which element is in LIS during contest time, and finally came up with a weird method when the contest was over...

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

Need some help with problem C Round 345.Any editorial soon??

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

    At first, solve it mathematically.

    Set a = xi — xj, b = yi — yj

    1. sqrt(a^2 + b^2) = |a| + |b| ; =>
    2. a^2 + b^2 = (|a| + |b|)^2 ; =>
    3. a^2 + b^2 = |a|^2 + 2*|a|*|b| + |b|^2, where |a|^2 = a^2 — obvious ; =>
    4. 2*|a|*|b| = 0, where a = 0 or b = 0

    Result solution: We must to calculate count of x-coordinate and y-coordinate repeats, and calcuate unique combinations PROFIT!

    P.S. Sorry for my english))

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

anyone can explain me ,, div2 D,,,,plz...

i make comulative sum,,, from first to last and then last to first ,,and the bainary search but some cases still mistake,,,

plz explain me what it says,, i am trying to read from first or reversly,,is it possible to start from center?

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

    There are many details in this problem which need quite a bit of careful handling. You can find the cases where your program gets WA (either in the system test or created by yourself) and think it over, or take a look at others' code.

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

The announcement has div1 tag only. Can you tag div2?

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

Guys, please publish the editorial !!!!!!

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

My code for div2 C get right wrong for "3 1 1 7 5 1 5 "(the first sample) but get WA on codeforces... Could someone explain me that? Here is my code: 16575774

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

OMG !

still can't see others codes :|

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

When will the tutorials be available ?

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

The problems are very difficult to hack ,so very bad.

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

Someone can give me simplified version of 19 test in "D" problem (div 2), please. Or explain, problems with binary search.

Thanks)

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

Please serve Editorials. Been a long wait.

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

    Zlobober : " I'm sorry but this will be a round with delayed editorial. All editorials for problems will be posted no later than March 9th, most probably on March 8th evening. "

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

have thought over it for hours still not able to find the testcase I am failing. http://mirror.codeforces.com/contest/651/problem/D

http://mirror.codeforces.com/contest/651/submission/16641326

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

    Here is your corrected code: http://mirror.codeforces.com/contest/651/submission/16641625. It seems that in your last loop, you are forgetting that we must see image 0 before we see image n - 1. Also, you are forgetting the case where we only move left or right and therefore do not need to take a * (i + 1) seconds to move back to the first image. I hope this helps!

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

Difficult to hack！！！！！！！！！！ TOO BAD!!!TOO BAD!!!TOO BAD!!!TOO BAD!!!TOO BAD!!!TOO BAD!!!TOO BAD!!!TOO BAD!!!TOO BAD!!!TOO BAD!!!

→ Reply