Educational Codeforces Round 87 [Rated for Div. 2]
By awoo, history, 5 years ago, translation, In English

Hello Codeforces!

On May/17/2020 12:20 (Moscow time) Educational Codeforces Round 87 (Rated for Div. 2) will start.

Please notice the unusual time.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Also thanks to Neal neal Wu for testing.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Codeforces and Harbour.Space

Hi Codeforces!

We would like to invite you to a very special webinar called Digital Lockdown: AI against COVID-19, by Sergey Gordeychik, director of our Cyber Security programme.

Sergey is CIO of Inception Institute of Artificial Intelligence, and former CTO at Kaspersky.

During this webinar, Sergey will share his expertise and insights on how AI is being used both positively and negatively, during the COVID-19 global pandemic. Tune in for some practical examples of how companies are using AI to innovate and disrupt during a time of crisis, exploring topics like Medical Imaging for CT analysis, diagnosis and mass surveillance.

Join us on Thursday, May 28th at 12h (BCN) to gain knowledge and deepen your understanding about how we can use AI to solve both operational and societal problems.

By participating in this 1hour webinar you will get a certificate of participation, a special digital gift from Sergey, and have the chance to win a FREE 3-week module at Harbour.Space University, depending on the availability and prerequisites of the course.

Reserve your spot now!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 square1001 8 294
2 Anadi 8 305
3 tfg 8 681
4 244mhq 7 192
5 xay_naive 7 248

Congratulations to the best hackers:

Rank Competitor Hack Count
1 qwscaln 29:-2
2 Ankit 5
3 lvao-x 3:-1
4 the_redback 3:-1
5 WICK_ED 2:-1
142 successful hacks and 828 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A fedoseev.timofey 0:02
B Ashishgup 0:03
C1 hitman623 0:04
C2 square1001 0:15
D Not-Afraid 0:10
E autumn_eel 0:17
F squarepants 0:47
G riantkb 0:37

UPD: Editorial is out

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

Comments Comments (645)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it -80 Vote: I do not like it

Good Luck ..

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

Wow this is really a good time in the Philippines! We can finally experience to join a contest at 5PM

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

Codeforces is entertaining quite by regularly holding contests in Lockdown. I'm enjoying. What about you guys?

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

awoo , MikeMirzayanov with all due respect , can you please reschedule the round to next day or during usual time since kickstart will start 5 minutes before this round will end . We can't code for 5 hours straight .

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

    Did you make this account just to make comments?? I wonder what could be the psychology behind this o_O

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

      Making alt accs just to make comments help as it helps you to be the jerk you are without ruining your real reputation. Though this comment isn't exactly being a jerk.

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

        You have my upvote.

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

        meeooow can you plz try to achieve 0 ranting I really really wanna know if it is possible or not

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

          Yes it's possible, even negative rating is possible. The lowest rating right now is -41. Check the last page of ratings table

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

          yep. trying my best to reach -ve asap. Though there are quite a few of them who've reached this milestone before. :)
          It's "rating", and not "ranting" btw.

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

        @meeooow pretty cool rating graph btw

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

    I like your contribution :P

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

    Did you make a new Codeforces account to say this?

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

    I agree. Yesterday's Round 643 was stressful too which affected the Codejam after it. I would hate to skip a codeforces round especially made by such good writers.

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

    :( .contest delayed by 10+5 minutes.Now 20 minutes of overlap .

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

      5 more minutes. But why?

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

      I'm pretty sure you can just close the tab and go to Kickstart.

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

        Well, if you perform poorly in today's round that will affect your kickstart participation so it's not just about time.

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

    And now the constest is delayed by 15 minutes more. Not a pro coder that I can solve all here and then go for kickstart as well.

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

Whatever time it is the participants always show up in large numbers. I'm proud of this community :)

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

Hey, this will clash with Kickstart round C for the last 5 minutes of contest, could you please schedule it something like 10 minutes earlier?

Thanks

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

Back to back contests.. That's why I love codeforces.

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

Does the hacking phase got any points? Or will it affect the rating?

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

    No. Educational and div3,4 hacking phase hacking has no points.

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

I have rarely seen unusual time in educational rounds. What is the reason for unusual time?

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

    I am not very sure but as far as I know, the contest time depends on the availability of the setters/testers during the contest. So the reason might be the mutual time decided by the setters/testers as their available time. Someone correct me if I am wrong.

    EDIT: It seems one of the setters has already notified the reason. This contest is tied to a local contest in Saratov.

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

    IDK

    Maybe because of some other coding events(or contests)

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

I think it's clashing with Google Kickstart round C. Though just 5 minutes but still it matters

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

    There is no break between the two contests that is only problem, usual time would't have created this problem. At last it is up to problem setters, they have their reasons.

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

Will it be easier than general codeforces round of div 2 ? (I have fewer experience about educational round )

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

    I feel educational rounds slightly more difficult than regular div 2.But be sure to learn newer things.

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

    maybe harder cause its problems is from GCJ

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

    from my experiences the difficulty is pretty much similar. but the open hack phase introduces some new challenges for us

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

This contest has a clash of 5 minutes with Kickstart Round C. It would be better if this contest gets preponed by 5 minutes or so.

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

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

I kindly ask newbies and pupils not to participate in this round, you are causing big queues. you are wasting time. Stop programing!!!

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

dsn

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

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

    STOP POSTING GOD DAMN NOT FUNNY MEMES. please.

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

      Ok thank you for your suggesion.

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

        Sorry if it was so aggressive(i said please in the end :) ), its fine if you are trying to make people laugh.

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

      ITS FUNNY FOR ME. STOP BEING A TOXIC.

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

Unfortunately, we cannot shift the round time because it is tied to a local contest in Saratov.

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

Codeforces evolution ->

2017 — Spamming "Is it rated?"

2020 — Spamming unfunny memes

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

    I feel it's my fault :P

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

      No bro you are the legendary grandmemer of codeforces ,soon you will be among the top contributors

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

        Thx <3 but Nah I won't reach top contributors the higher your contribution is the harder it gets to gain more and I'm running out of memes

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

          Ngl, I look out for that one single meme of yours in every contest announcement. They really make my day. :D

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

            Thx ! you made my day with your comment <3

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

            Why this feels so cheezy !!

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

Kickstart -> Educational -> Atcoder. This is just usual Sunday !!!. what's the hurry ?

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

so should we just abandon last 5 minutes of this contest for kickstart ?

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

deleted

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

How do I unregister from this round?

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

Nice contest time :)

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

Finally, I didn't do codeforces in the early morning. This unusual time is too nice for me

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

It's a good time for Chinese people, but it may not be good for other places :)

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

Should I skip this round for kickstart or should I give both. Any suggestions?

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

Live epic upsolving after the round:

https://youtu.be/SdwVz4qzhkY

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

Hey, how come no more non-Kotlin Heroes contests scheduled after this Educational round? (Like dang, many hours past the contest...)

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

Just meme :-) Pics-Art-05-17-01-11-34

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

I think codeforces community is trying to know which time is the best time for holding contest so we don't encounter any problems. I think it is the strategy to find the most suitable time.

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

Is there any specific reason for UNUSUAL TIME or its just fun? :)

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

Hope this contest will have some graph and DS problems.

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

Great time!! Thanks for arranging contests so frequently . Thanks in advance for the webinar.

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

A really good time for Chinese! We can enjoy the contests this weekend without staying up late.

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

It's the first time I am sitting for contests back to back. Hope the results will be good.

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

Less than 20k participants after a long time . Results of Kick start clash may be . Looking forward for an another interesting problemset .

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

Contest Extended!

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

The contest got delayed 10 minutes and now the overlap with Google Kickstart is 15 minutes

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

Delayed for 10 minutes.

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

delayed :(

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

Delayed by 10 minutes!!!

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

The voltage increases... another ten minutes.

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

what the hell is going on ??

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

Damn it, it's getting even worse now we have to abandon last 15 minutes of this contest

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

A penalty of 10 mins to everyone!! HAHA Another 5 mins! Congratulations

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

Delayed by 10 mins : hope server is fine

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

Now a 15 minute overlap with kickstart,rather than 5

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

I don't think it's very sensible to further delay the contest with an overlap of 15 minutes with Kick-start (which is a fairly popular competition and has almost 10k+ participants this year..)

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

Everyone said make it 5 min earlier. Boom you delay it by 10 min. People start worrying for Kickstart. Meanwhile Codeforces : "Here comes another 5 min, you guys just probably spamming"

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

let's hope this delay is not a sign of long queues during the contest

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

Contest should be postponed.It directly overlaps with Google Kickstart 2020.

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

Google Kick Start! :(

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

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

Is this a measure by the problem-setters to decrease their competitors in Kickstart? >.<

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

    In that case, people will do Kick Start instead of this contest.

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

      I don't think so, Kickstart has it's prestige but to people who want rated contests, they might skip Kickstart(or join late).

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

For the First time, a 100 minute contest! XD

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

Amazing.

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

Another 5 mins....

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

yo come on xd

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

okay now i am probably gonna take part in atcoder instead of kickstart (:

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

Another 5 mins :(

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

    THis has become irritating now...

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

    They dont even care to tell the reason of the delay.

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

This is frustrating

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

Now , i m not participating

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

Man, You guys are killing me. Delayed further by 5 Mins. Its a 20 min overlap now.

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

Please make sure not to start to early ;)

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

I am truly amazed by the arrangements.

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

WTF is happening. Again 5 min delay.

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

Why delayed again?

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

JUST TELL ME THE FINAL TIME OF STARTING CONTEST. GETTING PRETTY ANNOYED BY CHANGING TIME.

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

I want my 20 minutes back

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

I was already ready to go in, as here again the transfer for 5 minutes )

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

    By using GP (infinite) 10+5+2.5....=20 so contest will have 20 minutes delay

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

just forget about Kick Start

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

Seems its a trap now :)

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

Why are they playing with our feelings?

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

my patience is giving up .

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

What the hell is that,2 delays?

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

The contest is delayed by 15 minutes, so now we have 20 minutes intersection with Kickstart. Tough spot to be in.

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

Here we go again!

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

10 minute delay had a bonus!

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

Again Delayed! It hurts more than a breakup.

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

While(onClick("Start Contest") { startTime+=5; }

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

1 is okay but 2 is a bit frustrating

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

Server in trouble?

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

delay the round without notice is really uncomfortable...

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

Are you guys planning to delay it over and over so that it starts exactly at the same time as Kickstart?

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

wtf???????

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

why is starting time getting postponed every 5 minutes?

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

I wonder what had happened to this round.

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

Now 20 min penalty woaah why cf ??

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

What should be the priority kickstart or codeforces ??

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

Now we'll get to see real CF fans

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

Maybe they are waiting for 20K registrants.

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

Another 5 min, Hope clear statements !

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

delayforces /qiang

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

How to solve A?

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

    Just do binary search for the time

    first 10 min then 5 then 2 then 1

    glhf

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

When I say myself,**"Now we go",**then Suddenly I see 10 min left,and after 10 min ,again I boosted myself ,and again I see 5 min to go

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

Will they keep delaying it until unusual time becomes usual ?

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

Will educational rounds have points for hacking??

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

Testing our patience? xD

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

Kickstart guys going to suffer

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

Guys, don't mess with cf. They will add 5 minutes delay for each meme xD

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

a contest with 100 min xD (until kickstart begins)

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

I am wondering how are you holding an onsite contest during the COVID-19 epidemic?

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

UnusualtimeForces × DelayForces √

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

delayforces :(

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

Yet another 5 minutes extended.

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

They should either reduce the length of the contest for everyone or postpone the contest altogether (IMO).

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

Is it rated?

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

for(;time<=4:30;start_time+=5)time++;

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

If they add 5 min more, I'll wait 5 min more

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

how to solve D? my q*lgn*lgn using binary indexed trees(bit) ofcourse times out :(

UPD — my same code with cin cout passes?!

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

    you don't need binary search, traverse the BIT to find the answer ~810ms

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

      And I kept getting Memory Limit exceeded for some reason!!

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

    Use binary jumps

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

    Either fast descent on BIT or segment tree (in $$$\log n$$$), or the following:

    Suppose we are trying to find the minimum element in the resulting multiset. To do this, let's implement a function that counts the number of elements not exceeding $$$x$$$ in the resulting multiset in $$$O(n + q)$$$ as follows: if we distinguish only between elements greater than $$$x$$$ and not greater than $$$x$$$, we can maintain the multiset as two simple counters. To find $$$k$$$-th statistics, simply check that the number of elements $$$\le x$$$ is not less than $$$k$$$; if it is so, $$$k$$$-th statistics is not greater than $$$x$$$.

    That way, we can count the number of elements $$$\le x$$$ in $$$O(n + q)$$$, and to find the minimum element in the resulting multiset, we may binary search the first $$$x$$$ such that the number of elements $$$\le x$$$ is non-zero.

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

    My q*log^2(n) luckily passed, please hack it https://codeforces.net/contest/1354/challenge/80496838

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

How to solve C?

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

    For C1,i solved it by finding the inradius of the polygon multiplied by 2.

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

    1.0/tan(pi/n)

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

    C1: 2 times the apothem of the polygon, meaning 

    tan(pi*(2*n - 2)/(4*n))

    C2: I have literally no ideea.

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

    C1: 1/tan(π/(2n))

    C2: cos(π/(4n))/sin(π/(2n))

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

    Here is how to solve C1 (C2 is a whole other story). It requires you to know a little bit of trigonometry (sin, cos, tan formulas)

    Take a look at the above image, what we are looking for is the blue line. If we find the length of the line we can double it and that is our answer.

    How to do that: We can find the angle x by dividing 360/n where n is the number of vertices. Now we need to divide that by two so we can have half the x angle, lets call v = (360/n)/2 = 360/(2*n)

    We managed to create an imaginary right triangle and we know one angle (v) and the opposite side (with length 1/2 = 0.5), notice that the blue line is the adjacent to the angle v.

    Tan formula: tan(v) = opposite/adjacent For our case we solve for the adjacent and we have adjacent = opposite/tan(v) = 0.5/tan(v)

    So i hope that now it is clear that our answer is 2*(0.5/tan(360/(2*n))), just remember to double the n value at the beginning because we look for a 2n-agon.

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

      I saw a bunch of submissions of c1 by doing some sort of summation of cosine of angles. what was that all about?

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

        Some people solved both C1 and C2 with the same code and made the same submission. I guess that C2 requires some addition. I didn't manage to solve it but I think that the solution can be broken down to finding two different sides that sum up to the total square side. (or at least that was my approach)

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

          So C1 and C2 are not suitable for pupils(I mean students of primary schools). :(

          Luckily I find out the solution :D

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

      why can't we use sin() to calculate directly please explain. My approach was same i just used sin, so that sin(x) = side(0.5)/radius hence radius radius = side(0.5)/sin(x).

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

        Because sin = opposite/hypotenuse in our case we don't need the hypotenuse but the adjacent. You could use both sin and cos to factor out hypotenuse and solve for the adjacent (because tan = sin/cos) but is simpler to use the tan formula instead.

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

What's the point of problem C?

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

    It seems C1 is without rotation, and C2 has a slight rotation, but I didn't manage to find out by how much

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

      Same with you, and for C1 I even dont know how to get the accurate answer, I just tried and tried and finally get the answer which I even dont know why.

      For C2, I just continued to try, but unfortunately, I didnt get the answer. I find some rotation might be correct but seems it is just my guess not the answer.

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

    Mathforcse /cy/qiang

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

Why does lazy propogation give TLE/MLE for problem D.

80500739

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

    Memory limit is 28mb.

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

      How can this problem be solved using segment tree WTF?

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

        A classic segment tree uses 4*N memory (I've heard this can be tightened, but I use the 4*N version). So you'll keep a leaf for every possible value in the set, representing the count of elements in the set with that value. Then you build the ST saving the sum of children. So, when you are asked to add an element K, you can do that in O(log(N)) adding 1 to every node in the path from leaf to root. If you are asked to remove the Kth element, you make a "binary search" over the segment tree. This is, if you are in node A:

        *Is the left leaf enough to find at least K elements? That means to check if ST[A*2] >= k. If it is, then you'll recursively find the Kth element in that branch *Is the left leaf not enough? Then you go to the right leaf, recursively, but the call will be query(A*2+1, k-ST[A]) because the left leaf will cover part of the "prefix" you are looking for, so you need to subtract it from K.

        There's a base case, when A is a leaf, you simply return the value associated to that leaf. Once you've found that value, you also need to update the ST by substracting 1 to every node in the path from leaf to root.

        So you see every operation is log(N)

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

        without using lazy propogation. https://codeforces.net/contest/1354/submission/80515718

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

    Use 4e5 instead of 5e5

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

Please miss us with the geometry problems.

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

    Normally I would agree, but it helped that all the formulas were online ;)

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

      I've always wondered: Is it moral/allowed/good practice to google formulas or algorithms? It feels wrong to me :(

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

        this argument can be used to saving code templates for speed , or having a text with for example a standard segment tree code.

        yes it is moral and good practice as in competitions like icpc or even actual jobs , you can get those easily.

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

          Hey, I have an exam in a month's time. Is it moral and good practice for me to use my phone to look it up on Wikipedia? When I'm doing an actual job, I can access wikipedia easily.

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

            if it is allowed to do so , totally acceptable ;).

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

      where did you find the formulas? i also searched for them in internet but couldn't find.

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

        https://www.mathopenref.com/apothem.html for C1

        http://www.murderousmaths.co.uk/books/longdiag.htm for C2

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

          I don't get how is that related to C2: The article you cite has the formula $$$1/2sin(pi/2n)$$$ when $$$n$$$ is odd, but here $$$n$$$ is the number of sides in the polygon. In problem C2, the number of sides is $$$2n$$$

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

            Wait hmm

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

              Lol

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

                Wait actually I incorrectly assumed that I was dealing with an odd polygon and I was somehow convinced that it worked. Even I am confused now :|

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

                  LOL, When see you post the link related to the C2, I just feel unhappy but now I feel better because it doesnt seem to work.

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

                  The link I posted for c2 and the formula in it DOES work, I’m just not sure why

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

                  Well, though upset but have no choice about it. Maybe because I'm not a native English speaker so it's hard for me to search a web like that. But during the contest I didn't get the idea to google because I just thought CF didn't have anything that can be googled. If I were at the contest again and I knew that could be googled, I wouldn't google it because I think that doesnt help you anymore as all of the region contests cant google anything!

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

            I don't how how, but 80516401 got AC with this formula.

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

              Same formula that I used but idk why it works.

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

          loyal reader of the murderous maths (I am a primary student)

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

how to solve C1 and C2 ?

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

Can anybody explain how to solve C2?

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

    If n is even, twice the apothem. If n is odd, just the diagonal. **Longest diagonal

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

      I tried it on the contest, did not work, are you sure you are not wrong?

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

      Hi! What do you mean by "just the diagonal". for C2, I tried this which worked for $$$n==3$$$ and $$$5$$$ but not for more: tilt the $$$2n-gon$$$ so that its longest diagonal and square's longest diagonal coincide.

      How did you get $$$1/2sin(pi/n)$$$?

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

        Longest diagonal Here

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

          OK, but how is that related? The article you cite has the formula $$$1/2sin(pi/2n)$$$ when $$$n$$$ is odd, but here $$$n$$$ is the number of sides in the polygon. In problem C2, the number of sides is $$$2n$$$.

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

            For problem C2, the answer for a polygon of 2*n sides is half the longest diagonal of a polygon of 4*n sides, i.e., 1/2sin(pi/4n)

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

    I don't exactly know why this works, but I solved it by inscribing the given polygon in another regular polygon with twice the number of sides, then inscribing that in the square like in C1. Only difference is that the side length of the new polygon would no longer be 1, so you need a little trig to find that new length.

    I hear some solved it by ternary searching for the optimal rotation angle, but I haven't yet mastered that technique

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

    I solved it post contest and I came up with few things.

    1. The previous orientation which was used for C1 for n being even would be suboptimal. (The hint comes from the obvious first testcase where n=3 and yet the answer is not 2)

    2. If you place it in the similar manner as done in C1 there will be some gap left both from top and from bottom to the horizontal sides (In this case if we take the hexagon and place it normally with the centre diagonal as the side of square the top and bottom leaves some space)

    So we have to re-orient the polygon and the rotation turns out to be 45 degrees. (I do not have a concrete proof but the square can be squeezed down the most in that orientation)

    I would like to explain further but it would require me to show it via illustrations and I don't know how to do so.

    The answer is sum of two particular lengths (which are within the polygon and make up for the length of the side of the square) which depend on the side length of the internal angle based triangles. (the 2*n triangles formed from the internal angle)

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

    http://www.murderousmaths.co.uk/books/longdiag.htm

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

Many java users including myself had intended solution with BIT but still MLE? I don't think its ok that even intended solutions fail, really ruined the entire problem for me.

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

    Likewise, I was spending the rest of time looking for memory optimizations to fit within 28Mb. [ https://codeforces.net/contest/1354/submission/80506407 ]

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

      If you look at the error you will see MLE is due to your input class which is using buffered reader. I am guessing it reads the initial array as a string which have max length of 8e6(n*(len(1e6)+1)) which exceeds memory.

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

    I was initially doubtfull if BIT would fit into memory but it luckily did. My solution is in Java

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

Problem-B was on Stackoverflow

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

    you can solve the exact same problem on leetcode only difference is they are considering alphabet instead of numbers

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

Video Editorial for today's D

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

Nice questions and good round! I only managed to solve A and B :( I couldn't derive anything for C1 because I was blank in the middle of the round. Anyone, ideas for C please? I tried D but TLE'ed on Test-9. It's probably one of those cases where I'd perform complete $$$O(nk)$$$ operations. I couldn't figure out how I could bring down complexity to $$$O(k)$$$ (I later tried a prefix sums like approach which I couldn't make work). Could anyone help me optimise my solution?

Code

EDIT: Okay, nevermind. I read BIT and Segment trees in a comment above and realised my approach is no better than naive approach. I don't know how to implement either of the two yet :(

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

    for C1, symmetry is the key! Seeing symmetry, what i did is i calculated summation of cosine of angle of every segment with horizontal axis till n/4. (I assumed i am placing the first segment horizontally.)

    I could not do c2.

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

How to use PBDS for multiset , on web i got i need to change less to less_equal , but after that begin() , end() operations were not working

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

Im waiting for someone to post the geometry meme under this announcement

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

Am I the only one who noticed that today's problem B == 701C? :D

UPD: Well, I wasn't happy for that. I was just astonished as I've solved the problem before with exactly the same idea. I wish they were all unique, but just saying. Thanks for efforts.

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

how to solve C2?

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

    Simulate building the polygon length by length, Keep track of the biggest & smallest x & y positions, and from this get the lengths of the square All that's left to check is the best rotation of the shape, My solution was to ternary search the angle of rotation between 0 degrees & 360/n degrees My solution — https://github.com/OisinDavey/CodeForcesRounds/blob/master/edu87/C.cpp

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

      Thank you!

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

      I wrote a code with ternary search with similar ideas. But after a rotation, I was finding the minimum length of the square in a slightly wrong approach.

      "Keep track of the biggest & smallest x & y positions"

      Then, this part of your comment saved me. Thanks :D

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

Math of C killed me . :(

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

    And me (I'm a real pupil which means primary school student)

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

oh my god i'm so dumb i thought it said 7:35AM again so i woke up at 6:20AM and didn't realize that the contest was running the whole time LOL

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

Why does std::multiset give memory limit error??????

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

    Maybe because it has high constant factor in memory consumption.

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

      if i use vector then will i succeed in time limit, insertion is quite slow :(

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

Can someone explain why this solution fails? Instead of finding the length of the side directly, I found it using an indirect approach. Submission

I found the length of the longest diagonal and then using Pythagorean theorem the side of the square can be found. I think there were some precision issues with square root calculation. How to go around this?

Edit: Got the problem. The setprecision() is in the wrong order :(

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

How did the solutions of D with complexity o(q * logn * logn) got accepted? In worst case the no of operations will exceed 1e8

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

    It seems that for people who had the same intended solution one might have passed and another didn't. That's mainly why I didn't like this problem, it is just optimization hell.

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

    There are 1.5s and the number of operations done in 1s can exceed 1e8, like <= 3e8, so it could get accepted

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

    Yes,it can pass.I just use BIT + binary_search.

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

      Exactly what I did but still MLE...

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

        No look at mine: https://codeforces.net/contest/1354/submission/80501761

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

          Yes, I have the same intended solution which has memory limit exceeded. [80506407]

          Actually you cant even read the input to memory unless you use byte arrays in java. I wonder if the testers actually solved the problem in java before using such low memory constraints. . There are only 6 accepted solutions so far in java for the problem. My solution (in which I always use StringTokenizers to parse input was failing to even read the input.!!!

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

          Your solution and my solution are almost the same but still, my solution gave TLE on test case 37. Why is it so? My submission: https://codeforces.net/contest/1354/submission/80507579

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

            Because of "long long".It is much slower!

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

              Thanks a lot for your help. The same code got accepted when I changed them to ints. Isn't it a little bit unfair to keep the time bounds so strong that the same solution fails just because of using long longs in place of ints?

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

                The intended has a lower complexity, so it's not really unfair. Solutions of higher complexity may or may not pass.

                Also, I would advise thinking whether the data type can reach long long. If there is no doubt it cannot, use int's because I have seen various cases recently where this is the difference bw TLE and AC.

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

          Gary2005 why have you taken the case of -1 as a query in a seperate case?

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

            Because it is special case.I thought it wouldn’t work well with binary search.

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

      I got TLE

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

I don't get why people hate C1/C2. Yes, it is a geometry problem, yes, it can be solved with pen and paper work.

But:

1) The geometry itself is very simple and does not contain any case-bashing, just a simple formula.

2) There is a way to solve this problem almost without any greedy ideas and formula-deriving, with standard algorithms such as binary/ternary search.

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

    Normally I dislike geometry problems but these were at least simple enough and good for an educational round.

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

    In fact they can be solved just with junior middle school math !

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

    How to use optimal searching (binary/ternary) in these problems as you mentioned?

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

    I think it's cool. I'm looking forward to the editorial!

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

    Probably because we're here for coding problems, not pen and paper problems. If I wanted that I'd go look for math tests online.

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

      If you're not here for pen and paper work, then you could code a solution that does not rely on pen and paper at all (except for rotation formula).

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

        I could write long code for all div2 A 1-liners too, but that doesn't mean it makes the problem any better from my view. It's usually easier to solve a 1 line equation problem in 1 line than doing something like b-search, it's less time consuming, and it's not very satisfying to finish when you've just written a single equation.

        If it wasn't a coding contest I think it'd be a good problem, but I didn't enjoy it here. Tbf I didn't solve c2 which probably makes me not like it more lol, but in general I don't enjoy 1 line sols.

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

    people like to code more than to solve by hand some geometry problem. This is codeforces not geometry forces. Also please ban pikemike from problemsetting.

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

      Seriously? Someone has set 80+ Educational rounds and you're requesting to ban the guy. Wow.

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

    actually a lot of people could guess both formulas for c1 and c2. And in educational rounds for each problem you get one point, so i don't think that's totally fair

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

    how to derive formula for c2... how to do this with binary search?

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

    Fuck you and your geometry problems
    We came here to write code and not to solve math problems

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

    Thanks BledDest for the problem. How do you solve it using BSearch/Tsearch? What would the check(int len) function look like?

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

      The problem is by adedalic, not me.

      Solution for C2 with ternary/binary search:

      Suppose that one of the sides of the polygon is parallel to the side of the square. When you start rotating it, the difference between its $$$x$$$-coordinates starts decreasing, and the difference between its $$$y$$$-coordinates starts increasing, until some moment when it begins to go vice versa (and, at some moment, the height and the width are the same). After the polygon is rotated by $$$\frac{\pi}{n}$$$, the difference between $$$y$$$-coordinates becomes maximum possible, and between $$$x$$$-coordinates — minimum possible.

      Since we want to find a moment when the difference between $$$x$$$-coordinates is the same as the difference between $$$y$$$-coordinates, we may use binary search on rotation angle to check whether the angle is too small or too big.

      Or, for a more straightforward solution, we can write a function $$$f(ang)$$$ which gives us the size of the bounding box of the polygon, if it is rotated by angle $$$ang$$$, and use ternary search to find its minimum. The proof that this works is the same — initially the width decreases and the height increases, and at some moment, they are equal.

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

    Yeah, C1 and C2 were excellent problems. I dont understand why people hate it. Its just basic high school maths.

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

    I don't get why people hate C1/C2. Yes, it is a geometry problem, yes, it can be solved with pen and paper work it can be easily googled .

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

Can anybody help me out in C2 with some proof .

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

General idea for C2 (without proof):

Consider the line segments connecting: - vertex 1 with vertex n+1. call these vertices V1 and V2. - vertex (n/2) with vertex ((n/2) + n). Call these vertices V3 and V4.

Let's assume vertex 1 is located at angle 0 (positive x axis direction) without losing generality. We need to rotate the polygon by an angle alpha until the horizontal difference between V1 and V2 and the vertical difference between V3 and V4 are equal.

let beta be the angle of V3 compared to the polygon center of mass. The goal above will be achieved when: cos (alpha) == sin (beta + alpha) in other words: (Pi / 2) — alpha = beta + alpha

Then you find alpha and multiply it by the distance from the center of mass to any vertex.

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

Oh... I miss the contest :'( I thought the contest starts at 14h30 utc.

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

    Oh Lucky You !

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

      Nah~, I really like join contests even I can make my rating down. I only care what experience I can get from it <3

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

How to solve E?

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

    If any component is not bipartite answer is NO. If you fix the vertices which will get color 2, then you can color remaining vertices as 1 or 3. Now it's just knapsack problem.

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

    The key observation is that colors $$$1$$$ and $$$3$$$ are interchangable: if we have a good coloring and change $$$1$$$ to $$$3$$$ in it (or vice versa), it is still good.

    So let's instead solve the problem where we paint the graph into $$$2$$$ colors: $$$1$$$ and $$$2$$$. To do this, find all connected components and check if they are bipartite. If there is a non-bipartite component — the answer is NO. Otherwise, we either assign $$$1$$$ to the first part of the component and $$$2$$$ to the second part, or vice versa.

    Our goal is to assign $$$2$$$ to exactly $$$n_2$$$ vertices, so if the number of vertices with $$$2$$$ in the $$$i$$$-th component is $$$cnt_i$$$, then we must have $$$cnt_1 + cnt_2 + \dots = n_2$$$. For each $$$cnt_i$$$, we have two possibilities: it is either the size of the first part of the component, or the second part. So we may write a knapsack-like dp to satisfy this equation.

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

      E is very educational,thank you for you effort!Though I didn't pass it during the contest because I forget that 'dp' starts from '0'.

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

    First, observe that there is no answer if the graph contains cycle of odd length.

    Second, observe that if we have fixed the position to fill the 2's, we are free to decide to fill 1 or 3 in remaining nodes (as long as we have enough such number)

    We can consider the answer in each connected component and do a DP, detailed as follows:

    1. Detect if there exists odd cycle (this can be done by considering the depth of nodes when visiting a already-visited node)

    2. Find the size of each connected component.

    3. For each connected component with size, try to fill 2 in alternate depths. There are only two ways of such filling, one of them uses $$$A$$$ 2's and another of them use $$$B$$$ 2's ($$$A+B$$$ is the size of the connected component)

    4. Do dynamic programming on the values of $$$A$$$ and $$$B$$$ you got in each component (you will need backtracking)

    5. With the DP table you have built, determine if you can have an answer having exactly $$$n2$$$ 2's. If so, also fill the remaining spaces with 1 and 3.

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

    Do check this , I have implemented this using top down dp (with comments). https://codeforces.net/contest/1354/submission/80571115

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

[Deleted]

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

Why was the limit on $$$N, Q$$$ for problem D so tight? To avoid a policy-based data structure solution to fail? Is it expected for an $$$Nlog^2(N)$$$ solution to pass system tests, given that it would take approx. $$$4.10^8$$$ ops?

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

    The intended was BIT sol and 1.5 seconds gives enough leeway for it, despite this many BIT sols failed so I am not entirely sure how the authors were trying to educate us with problem D.

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

      I think you're supposed to use nlgn sol using trick to bsearch on fenwick faster.

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

        I got MLE not TLE :think: also unoptimized bsearch passed for people

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

          I think it's because you used class, that adds extra memory overhead. Try getting rid of all template stuff to use less memory, though idk if that would work.

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

    To let the contestants using fhq-treap fail because of MLE.

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

For D, q*lgn*lgn passes with cin/cout but times out with print/scanf.

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

Do the organisers have any solutions for D that work with any version of python? Given that there were no accepted submissions during the contest (and at the time of writing still none)...

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

    OK there are now some (at time of writing 2 independent) accepted submissions in pypy3, so I take back what I said. Still incredibly tough for us python users, but I guess that is the cost that comes with using a more handy language...

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

smallest-square-that-can-be-fitted-outside-the-regular-hexagon

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

    The colon ':' is missing after https in your link.

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

E is a good problem. C1&C2 are too bad

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

    E is wack shit that shouldn't be in an Edu round in the first place. C is the real skill that one should hone.

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

      Why? C is simple formula problem and in fact, it should be a complete math problem instead of a competitive programming problem, which is not situable in an edu round.

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

      I agree E doesn't require much creativity but why E isn't suited for edu round(I think it bring concepts of bipartite graphs, knapsack and the building dp answer which is educational)

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

        For real, asking people to answer up to 3 (why not 2), tracing dp (which is an abomination) and leaving such problem in the E position.

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

          If only colors to be used are 1 and 2, arriving to the concept of bipartite will be instantaneous. And it's just a couple of more lines of code. Tracing dp is hated but so is geometry so your claim for C can be loosely applied here. Where do you suggest to place this problem in problemset?

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

    If you liked E, there's a similar problem on AtCoder that is very nice also:

    E — Independence

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

Formula for C2 (without proof):

C1: 1/tan(π/(2n))

Link: https://codeforces.net/contest/1354/submission/80516480

C2: cos(π/(4n))/sin(π/(2n))

Link: https://codeforces.net/contest/1354/submission/80516821

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

    Can you give at-least some intuition? How did you come up with this?

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

      https://codeforces.net/contest/1354/submission/80533336 First of all orient the polygon such that one of it's main diagonals(consider this x-axis) is parallel to a pair of sides of square.Then,you'll notice that if we rotate this diagonal by some phi say in counterclockwise direction.The length of projection(along x) of this main diagonal will shorten and become 2*circumradius*cos(phi).At the same time height one of the points belonging to the side of polygon that is || to the main diagonal starts increasing and it becomes 2*circmumradius*sin(psi+phi) where psi is initial angle made by this point with x-axis i.e psi=(n/2)*pi/n.So the optimal case is when cos(phi)=sin(psi+phi).So we get pi/2-phi=psi+phi i.e. (pi/2-psi)/2=phi.So our answer is 2*circumradius*cos(phi).

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

How to solve problem G?

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

    IDK

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

    Well, here is a solution (I think, I did not participate, and nor do I intend to implement this to check).

    First, we choose random 31 elements, and then find the maximum among them. This can be done in 30 queries. The probability of the maximum being a stone is atleast $$$1 - (1/2)^{30}$$$. Now, we have the index of one stone. Remove this index from the array.

    Now use this and query it against the first stone. If the first stone is lighter, it is a gift. Else, it is also a stone. Use the first two to query 2,3. If 2,3 is lighter than 1 and our stone index, then there must be a gift among them. Binary search that. If not, use 1,2,3 and our stone (4 stones now) to query 4,5,6,7.... etc. This whole thing can be done in less than 20 queries (10 for the "forward" binary search, 10 for the "reverse" binary search).

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

      Well, I too thought of a similar idea. But, I am interested in a deterministic solution.

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

        I think this was the intended solution, since "Hacks are forbidden".

        Note that obvious ideas to make the first step deterministic such as partition totally array in 2 and always choose heavier subarray fail on a case like [20 20 20 1 20 5 19 19] — the algorithm will end up choosing 19.

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

How to solve div 2 problem B

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

    well, this is pretty standard. You can use Two pointers and find the answer in linear time. Another approach is using binary search: If there exists a valid subarray of length $$$l$$$, also this is true for all $$$y \ge l$$$, so you can apply binary search over the length of subarray and check each subarray of current length in linear time, so complexity is $$$O(n\cdot \log n)$$$

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

Anyone has good solution for D?

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

    Imagine we have a frequency array that counts how many times each integer appears. Well, now use a Segment Tree of Sum over that array, you can do each operation in $$$O(\log n)$$$-time.

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

Was D added to fuck all Java participants?

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

    Yes, it was really unfortunate :(

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

    sqrt bucketing, solvable using O(n) memory.

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

      I do not expect to have to do that for a Div 2 D, though :/

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

        actually idea is not that hard, even easier than segment tree (but I guess we are more familiar with segment tree). Most of sqrt bucketing ends up with T: O(n*sqrt(n)) S: O(n)

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

          How would it use less memory than fenwick if implemented with just array?

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

            not talking about fenwick tree.

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

              I think what he is talking about is that the solution that most used is fenwick tree which is also O(N). So sqrt bucketing is probably worse>

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

    Even worse is that sometimes it passes with the same memory, other times it doesnt. [80497819 has the same memory used as my solution [80506407 but passes. I changed the way I read inputs from StringBuilder to DataInputStreams and that passes too !!

    awoo, is it possible to at least rejudge java solutions in the contest adding a little bit of memory overhead, otherwise I think its completely unfair!

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

      It's unfortunate, but it is well known java's limitations compared to cpp, so if you choose to use it that is at your risk, especially if there are solutions that do pass.

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

        How do you know it's well known limitation? Only 6 solutions in java passed during the contest. I have been doing CP for almost 8 years now, with the same (or similar input readers) and never had to face this kind of issue. On a positive note, I did learn a more efficient way to read inputs (but was that the intention of the problem authors?) A well known limitation of java is to use Scanner to read inputs vs other buffered readers, (and similar to output). But this is really new and one of a kind issue. If the authors had not intended it, they can just acknowledge and care about it from next time (would be nice of them to re judge the solutions of java in the contest, but not required). If they did intend it, then I can start looking for even more efficient ways to read inputs from next time :)

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

          I meant in general java is slower and uses more memory, which is well known, and this is why most people use cpp, so using java in general puts you at risk. I do think that the input method being the problem is pretty bs though, and that should've been tested.

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

For Problem D

CPP solution is working fine with memory = 4 * n

But Java solution is getting Memory Limit Exceeded for memory = 4 * n

This looks unfair, kindly let me know if I am missing anything.

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

    Java solutions using new StringTokenizer(in.readLine()) fail because the entire line is too big to fit in the memory constraints. Need to use a better I/O method to pass :(

    My solution and I/O method below.

    public int ipar() throws IOException
{
    int n = 0;
    boolean seenDigit = false;
    char c;
    while (Character.isWhitespace(c = (char)in.read()));
    boolean neg = false;
    if (c == '-') {
        neg = true;
    } else {
        n += c-'0';
    }
    while (Character.isDigit(c = (char)in.read())) {
        n *= 10;
        n += c-'0';
    }
    return neg ? -n : n;
}
    → Reply
»
5 years ago, # |
  Vote: I like it -23 Vote: I do not like it

First time I came to know that $$$π$$$ is not equal to $$$22/7$$$.

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

My submission for D got TLE on test case 37. Its time complexity is O( q*log^2(n) + n*log(n) )

Here's the link: https://codeforces.net/contest/1354/submission/80507579

But almost the same code which is O( q*log^2(n) ) got accepted. (I submitted it after the contest)

Here's the link: https://codeforces.net/contest/1354/submission/80514775

I don't understand why? Please help me out.

UPD- Found the mistake. I used long longs instead of ints :(

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

    The same thing happened to me but I didn't find any mistake. Even I compare them.

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

    Your same AC solution is giving TLE on test 13 Link

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

Problem B was available on GeeksForGeeks and Stackoverflow . So all those participants who copied from there would get plagiarism or not ??vovuh

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

    I guess number of dislikes is the number of people who took B from above mentioned platforms. XD

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

      1. It is totally fine to use code from other sources (as long as it is not from other participants during contest). Even ICPC allows prewritten material.

      2. This problem was easy enough to derive in like 1 minute anyway

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

        Yes it was pretty straightforward 2 pointer question but to save time things might have been copied .

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

          Yes and it doesn't matter. Most people have templates of code saved up anyway...

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

      I didn't take part in the contest and even more I didn't prepare any problems, but I disliked you because why do you need to mention me? How do you know if I'm tied with this problem somehow?

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

        I am extremely sorry. I didn't mean it that way. I just wanted to ask you about that fact that wether or not is there a plagiarism check for these kind of things since you are a problemsetter and you might know about it and I didn't tied you to that problem .Just a general doubt. I didn't mean to insult you in any way . Just curious.

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

80510010 It's very close for a problem with TL 1.5s. Will this pass system testing?

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

Did anyone else spend a long time on D bcz they thought the BIT sol was so standard you must have to use less memory than a 1e6 array? I was thinking for a long time how to only store value on input and compress, but then decided to try BIT and was dissapointed to see it worked.

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

    With simple maths we know that we can have around 28*1024*1024/4 = 7340032 integers, which is definitely more than 1e6. I think it's important to know how to evaluate the data we can store in such tight memory limit question. Yet this question is still very unfriendly to people using java and python :C

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

      I did that but assumed there would be memory overhead causing the need for a tighter sol, which happened to be the case with other languages, but not cpp.

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

    Btw BIT solution was already available on the web.

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

      Damn. I should have searched for Order Statistics tree implementation, instead of BIT implementation during contest.

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

    Umm say the multiset contains all numbers from 1 to n, then I would need an array of n size to store it, right? Otherwise I wouldn't be able to tell which number is there or not. And BIT uses the same amount of memory as the array. So I cannot understand how you thought that even lower memory must be used.

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

      I thought it'd be something similar to bloom filter, so I was thinking along that line.

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

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

I feel that all the java submissions for problem D should be re-evaluated as the contest seems to be biased towards cpp guys! The same code is accepted in one language and not the other. This is simply ridiculous,never seen this happen before!

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

Problems B + C1 + D + E

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

https://codeforces.net/contest/1354/submission/80472333 can somebody explain this code of c2

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

Why do you completely hate Python?

I like programming in python. I had a perfectly good solution for D with a segment tree. I created a list with around 2,000,000 zeros. MEMORY LIMIT EXCEEDED. in python3.7 python2.7, pypy3 and pypy2. And the sad thing is that it makes sense, because the memory limit was 28MB, and each int is about 32bytes. After the competition I transformed the solution to C++, and lo and behold, it was ACCEPTED. Would it have been so terrible to limit the memory to 80-100MB instead of 28? It just seems super unfair to me in this situation.

Also, you keep telling us to USE PYPY2. But on two separate occasions now (one in yesterday's competition as well, in young explorers), when you have to print many test cases,I get a time limit exceeded, which I DON'T get in python3.

You can check my profile to see I'm not making this shit up.

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

    No one cares about python..Understand it or accept it

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

      Dude, Atcoder, Google kick start (and other), leetcode are all accept python. CF is the last platform that has c++ benefits (even Java sucks here).

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

It's surprising how almost the same set of authors can set absolutely horrible contests (like this one) and very well balanced contests (like last Edu round).

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

    Is it horrible? Nope. How, I found this one interesting. Specially C1 and C2. You can get to a formula where you don't need to think of precession errors.

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

      C2 is too hard to be Div2C. D is just dumb. I do CP because usually getting the asymptotic complexity right is enough. Policy Based Data Structures also use O(N) memory, but memory limit on D is set too low just to fail PBDS. That's absurd.

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

        Nope, C2 isn't too hard for div2C. I am assuring you as a class 10 student with no prior math olympiad experience. And it would be like a cup of tea for an IITian because of massive difficulty level geometry questions they went through. You probably had a very bad day, in other day, you may get accepted in only 5 minutes.

        But D is just a trash. It's just an unfair advantage towards cpp guys

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +4 Vote: I do not like it
          Nope, C2 isn't too hard for div2C.

          Number of submissions to the problem say otherwise.

          I also don't know where you got the misconception but an IITian does not need to know proper geometry — it's only coordinate geometry and trigonometry which are part of the syllabus.

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

          yeah it requires some basic geometry only ....... as one can easily understand by taking diff values of n and fitting polygon inside a square that the square must have side equal to length of longest diagonal .......which is the line connecting exactly opposite vertices....... then do some geometry .... and get the results.... I am still not able to find the fact that why people are considering C2 as tough or maybe it was easy for me as maths and geometry are my fav topics being in ICSE board upto 10th i like goemetry very much

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

            You did not solve C2 and here you are talking about its solution and difficulty level. Its not that simple. Your statement — "that the square must have side equal to length of longest diagonal " is absolutely wrong. For solving c2, it won't be the case. You can fit a hexagon inside a square where none of hexagon diagonal is parallel to square side hence your statement is wrong. For solving it you can have diagonals making some angle with square's side and then computing this angle is the key part.

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

              question also says that you can rotate the polygon....please read the question first then give knowledge to others,,,,,,,,,

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

                Try C2 and solve it. I already gave you hint how to do it. You will understand what I meant :)

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

        If PBDS was allowed, the question would be like : Do what's written in the statement!

        I myself also tried a PBDS solution but I think low memory limit was justified (Not talking about Java/Python users..that's a completely different issue).

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

          Agreed. I am not saying they should have allowed PBDS. I am simply saying it's a bad question when you have to set constraints to fail one O(n+q) memory solution (PBDS), while allowing the other (Fenwick Tree) to pass.

          Any solution with correct asymptotic complexity should pass if the question is good.

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

Like almost all Educational Rounds, i think this round too lived upto its expectations. I personally found the problems very interesting, especially for a guy like me who is still in the learning phase. PS: I found an exponential jump in difficulty of problems after C1.

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

    C2 is not that hard man. Just similar to C1 with little observation. There is no big gap

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

      Can you prove your solution?

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

        Sure. Here is the square for hexagon.20200518_155238.jpg
        Rest is easier to do.

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

How to solve c2(without formula)?

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

The D problem was really interesting , same as that the problems C1 and C2 are really worst.

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

authors: make problems with simple geometry us: GEOMETRYFORCES XDDDDDDD

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

In problem G, is there any special use of the fact that k <= n/2 ? Won't just k >=1 suffice?

Just curious, why aren't hacks allowed in G? My very very incorrect solution to G passed.

Edit: Now I get, the intended solution was using random.

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

    congrats on kickstart rank

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

    It allows a solution to quickly check if an element is a stone, with high probability using ~ 30 queries. Probably hacks are forbidden to avoid hacking seeds etc.

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

I still don't see the point of adding math problems in a programming contest
Please can someone explain it!

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

when will the next normal round be held , cz from 29th may it's showing kotlin only

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

NEVER use problems like C1 & C2 ever again! it's a total time waste! what's the point of applying an equation you can easily find online to get the answer! either use quality problems or postpone the round till you have something worthy, but this.. this is not acceptable at all.

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

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

Can anyone tell me Why ordered_set gives memory limit exceeded in D?

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

    I too want to know, what ordered set gives mle and segment tree with lazy propagation got accepted? Thanks in advance.

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

      I guess MLE proves the high constants involved in the implementation of ordered_set. And by constants I mean memory — O(n*c) ,where c is quite high to fit in the memory limit of the problem.

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

This was one of the most unbalanced contest.
D was so unfair for various languages. Further C was designed to be a dull geometry problem.

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

Hi, I am facing an issue. My first Submission to the problem D was showing TLE during the contest but after the contest when I resubmit the exact code, it got accepted. why?

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

    what's the point of lying , it isn't the exact same code you added a new value (mx) and used it to change multiple conditions.

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

      Bro, I said First Submission you checked 4th submission. Why would I lie if anyone can check my submission? Please Compare 80504013 and 80527339.

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

        i apologize. this is actually quite weird someone should look into it.

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

          What should I do? I dropped a mail to the mike and problem setter.

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

            It is probably just barely on the edge of time limit. Problem D was super dumb anyway and designed to be on the edge of TLE / MLE which is absolutely dumb :/

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

        You are taking too close to the TL. During load (like a contest), the time taken is more than normal. So for unstable time taken, you may or may not TLE, it's luck then.

        Even I have had this happen in a round, sucks but is fair.

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

I solved C2 by searching the web Largest hexagon that can be inscribed within a square. hexagon

Then I guess the 2*n sided polygon should be put n/2 sides chord to the b right triangle hypotenuse, and n — n/2 sides chord to the c hypotenuse. Code

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

    please explain your code a bit .....thanks

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

      dia is the diameter of the circle which the polygon is inscribed in. You can computed it by half of the side length of the triangle and half of the center angle of each triangle, we get 0.5/sin(PI/n/2). The chord can be computed by the diameter and the center angle. n/2 sides center angle is PI/n (n/2) , half it we get PI/n(n/2)/2. The half of the chord is dia * sin(PI*(n/2)/n/2), the chord is dia * sin(PI*(n/2)/n/2) *2.

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

How could WindScanner solve C1 after D only 20 seconds? This comfused me:(

80460341 80460643

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

    Maybe he read both the questions and solved them, but didn't submit until he had solutions of both problems ready. tourist surprises us with this strategy many a times.

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

      And also in 1324 , as an untrusted participant, WindScanner solved D&F almost at the same time when it is only 10 minutes from the comptition started and got 4th place in the end. I don't think that is normal, I think he is just a cheater.

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

    Weird indeed, because it's not even the same code template. Hopefully, it won't be, but it seems like cheating. We have already seen here some cases of pair of cheaters on-contest

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

    fakeMatrixCascade Have you noticed his submissions still count? He ascended to candidate master

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

80530953

Inviting you folks to hack my F, it seems super simple and I cannot fathom why there's 6 second timelimit for this task.

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

    Time limit is set to $$$6$$$ seconds to allow flow solutions (I think that even though they are slower than exchange argument dp, they should be still allowed to pass).

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

      Thanks for the insight! Can you give a rough sketch of a flow solution?

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

        The answer looks like that: we choose $$$k - 1$$$ minions and place them in some order, then we choose $$$n - k$$$ minions which are placed and instantly destroyed to give a bonus to previous minions, and then we place the remaining minion.

        Let's analyze which value each minion adds to the answer. The first minion adds $$$a_i$$$ to the answer (since it doesn't give any bonus), the second one empowers the first, so it gives $$$a_i + b_i$$$, then $$$a_i + 2b_i$$$, and so on. The minions that are summoned and destroyed give $$$b_i \cdot (k - 1)$$$, and the last one gives $$$a_i + b_i \cdot (k - 1)$$$ power.

        For each minion and for each position, let's calculate the value we will get if we choose that minion for that position. Then we should distribute the minions into positions so the sum of values is maximized, and this is a well-known assignment problem which can be solved with Hungarian algorithm in $$$O(n^3)$$$, or with mincost flow in $$$O(n^3)$$$ or $$$O(n^4)$$$.

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

Most stupid round ever!

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

    Oh really? So you solved all the problems and got to the conclusion that it is soo stupid. The fun with this round begins with problem E (E-G). The first 4 problems (A-D) were just problems that somebody might enjoy, other's not so much, because of the math, memory limits or other things. I solved only the easiest problems from this round and the only frustration i have is that i didn't have time to think about E-G and i still don't think that it's stupid. For mediocre guys competitors like me there are the first few problems, for the cool guys there are the last 3. Why do you think red's are not complaining that C was sooo mathy and D was sooo tricky. It is because it's just too easy for them. There were problems for everyone. Who is good with math had C, who is good with DS had D, who is good with observations and maybe coloring problems had E, dp F, again observations and interactive problems had G. This round has it all and i really don't think that you are to say what is stupid or not.

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

      I agree with everything you said except for problem D. Many also saw the obvious BIT solution but were screwed over by the MLE. I don't know the hate for C since it seemed not too hard with only slight bit of math that you can find online.

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

        Well yes as i said, some might like some problems others might not because of various reasons (programming language, math background...).

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

    Also screw you for posting from a fake account.

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

Why is there a $$$6$$$ seconds time limit for problem F?

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

I was amazed by looking at the second question in today's contest. It's the same as this standard question which I was doing today at 1:00 PM IST as practice for LeetCode Monthly contest. I didn't even change the code a bit, I just returned the size of string instead of an original string as given in the question in the link. My code is here.

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

    yeah as it is a very general sliding window problem, so it can be seen on any platform!

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

The contest announcement post with negative votes! Rare records. Anyways, thanks for the contest.

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

Is there a simpler way to solve D without using a Segment tree/Fenwick or smth similar?

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

    Considering the memory limits, I doubt it.

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

      I mean it's interesting that they asked to output any element left. So I thought maybe there is a smart way to find an element which will for sure be left in the multiset. But maybe there is no such a solution so idk.

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

        Yeah I also thought it was a non-standard sol which you had to do something smart. I guess not

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

    Binary search like this(from rank2)

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

I'm really glad to see that the announcement of this round has negative contribution. No one wants to solve non computational geometry problems. Those are meant to appear in math competitions not in programming competitions.

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

    Totally agree.

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

    also they did not cared about kickstart......

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

      Why should they? Someone participating in Kickstart should have just skipped this round, after all, there are many contests ahead.(Downvotes incoming ig)

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

    you are a narc

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

    This round should be unrated.

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

    I didn't like many problems too, but c'mon, people still put time and effort into making the round, and I don't think it deserves downvotes. It was a functional round with semi-interesting problems (except D), and I don't wanna see 1-liner pure math geo either, but it was still decent problem for what it was. Just probably they should not have something like it next time, as now they see people's reaction.

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

    Why do you hate geometry problems?

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

    +1

    Round should be unrated!

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

WHY WHY WHY do those with a rating of more than 2100 stand in the standings as officially, will this change?

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

You guys need to stop laying bricks, math problems are tier 1 borderline chief. All hail Mikhail.

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

So you Div 2 trash have downvoted a round for a problem you can't solve? Well done, wish you stay in Div 2 forever and never realize geometry is not the worst topic.

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

    I downvoted because my solution for D gave MLE ,However the same idea passes using c++. I spent more than half the contest trying to optimize it which isn't fair, i even sent a message to the coordinators during the contest and their reply was "Unfortunately, the memory limit in this problem is tight. Make sure that your solution is memory efficient." Anyway apart from D ,the contest was good.

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

    Let me tell you, they cant see the bright side.

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

    Cuz C was only geometry problem, there wasn't any programming. And B problem was at the internet already

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

    I don't think that's C is really "geometry", imo it is "math". For me problem is "geometry" if it requires some shitty geometry algorithms.

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

People cannot understand why it is called Educational round

I think we people do not appreciate the efforts made to create such rounds. Authors and testers are not angles who do not make mistakes.

If you think you can create a better round, why don't you propose a round to codeforces and see how participants react to your work although you might have spent a month preparing the round(people might call your work trash).

People do not want math nor geometry problem because they cannot think. they want something they can solve, and when they cannot, they turn around and say it is a bad contest (nature of human).

I myself did not solve C1 nor C2 nor D but I think they are beautiful educational problems.

I just wanna say thank you for all the authors and testers.

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

    When i encounter a problem i cannot solve that's when the excitement starts

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

    You said my words, thank you for understanding.

    I am trying to make a contest by myself, and its never easy to make good problems, so even if the problems weren't as nice as hell, then its still fine.

    It seems the problems are too googlable, and so, i guess its not acceptable.

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

      all the best!! i hope you are able to make some very interesting problems

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

Just a shitty contest once in a while but please keep it unrated ! I work hard for ratings and I don't google during contests ! Today I payed a -80 rating drop for not googling between contests.

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

    If you're really worth your rating you will get it back later

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

    Atleast authors should say something about easily googlebale tasks ! why are they all just silent ?

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

      Because its an Educational round. Read the rules and you can see that these rounds can contain well-known problems.

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

    Yeah, you are totally right!1! I spent 10 minutes googling related formulas like incircle radius but that didn't help me to come up with my solution... So my rating should be bigger (xD, trolling)

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

When is the editorial coming ?

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

    Probably right after the hacking phase ends. Or some hours later than that.

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

Can anyone explain a simple O(n) solution for B?

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

    This can help you

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

    Convert 111333211123 into arr = [[1,3],[3,3],[2,1],[1,3],[2,1],[3,3]]. arr[I][0] represent number. arr[I][1] represent how much arr[I][0] was in a row. go:

    minimum= 99999999
for g in range(len(arr)-3):
if (len(set(arr[i:i+3]))): #if this subarray contains all numbers
   minimum = min(minimum, 2+arr[i+1])

    2+arr[i] cuz we need only this nums 1 1 1 2 2 3 3 3

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

How much long will it take to display the ratings on our profiles?

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

About problem C2, seems like the side of the square is equal to FJ(The samples matched). I submitted without proof why it works. Can anyone please check the math, and explain why it works. I can't figure it out!
code: https://bit.ly/2LFcU4A

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

    Angle subtended by an chord or arc of circle at circumference is half of angle subtended by same arc at centre(Its a properties of circle). So now we know one side and opposite angle and we can calculate the other side by using basic trigonometry(as triangle formed is right angled triangle).

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

      Hey man, I know that property, and that's how I came up with this sketchy solution. My question was, for 2*n sided (n is odd) regular polygon why the smallest square where the polygon can be inscribed has side length FJ (or Aj, since AJ = fJ)?

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

I think this contest should be made unrated for everyone because the solution of problem B,C,D could be directly found in google.This makes this round a test of our googling skill not coding skill.Many contestants have taken advantage of it.Even some of them copied directly from the source websites.I found some solution were directly copied from geeksforgeeks. It's really funny that they submitted the solution with the comments of the website.If this round is still rated, that would create a very wrong practice among the coders.Now everyone will google the problems in first place in the next contests. Anyway,happy coding.

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

    I mean like there is nothing wrong with googling. In most rounds google is not applicable (for the most part) and even if does create a "bad practice" people will immediately realize that they will not always be able to use google in future rounds. Also many use templates of prewritten code which is also allowed by ICPC so overall I don't see any problem with it. However, I will agree that problem D was terrible this round because of how it screwed over so many people with the intended solution.

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

      I don`t understand your position on D. Problem has straightforward O(n*log(n)) solution with segment tree. If you do not know that some intended solutions can get TL or ML than you should read name of the round. Otherwise, it is your risk to use intended one or think on better algorithm.

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

        Of course segment tree and BIT are the obvious solutions, especially BIT. I am talking about how many non c++ users used exact same solution as c++ users with BIT and still got MLE.

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

          That is not fair that you can read and split whole array in 1 line and I need to write whole for(;;) loop. Java have clear advantage. Sry for exaggerating but sometimes it is normal that a person in sneakers can run faster than in boots :)

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

        I realize that this is an educational round but I don't find anything educational about optimization hell.

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

          This exact thing happens to Python coders all the time. Is the solution then to throw out problems that can’t be solved in Python? Where is the line drawn?

          The reality of the situation is that you need to know how to handle stuff like this if you want to code in Java. Problems that are optimization hell get set in ICPC, two from the top of my head this year are ICPC Camp from NAC and Jumping from SER.

          A contest I went to earlier this year at Mercer had a problem where you had to print a double to 3 decimal places. It turned out that the data was written in C++, and the rounding procedure for printf in Java did not work. Thus, all the UCF teams there (except the one team with a Python coder) could not solve the problem.

          Stuff like that will continue to happen as long as the majority of the competitive programming community uses C++. It’s the reason I switched from Java to C++, and it’s the reason you should know some basic C++ if you want to be successful in Java.

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

            Yeah I guess you're right. I mean it doesn't typically happen where using a different language matters but I am just a bit frustrated because over the past few contests I have gotten screwed over for Java's slowness, and considering Java is the second most used CP language, I would think that there would be some care taken to make sure solutions for it pass. I am trying to make an active effort to switch to C++ but I am not sure how well that will go while I'm in the midst of learning new algorithms and such.

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

              Yeah, I understand the frustration.

              It took me about two months to reach the same proficiency in C++ that I previously had in Java. My advice (YMMV) is to just dive headfirst into coding in C++, and only submitting stuff in Java if you have no idea how you could do it in C++. At the start, you might only solve a couple problems per contest in C++, but over time that will increase to half, to most, and finally to all. It might cost you some penalty points, but if the reason you're doing contests on Codeforces is to practice for more important contests (like USACO or ICPC), then the practice you get for those is more important than your rating. Besides, if you deserved the rating that you have, you will get it back quickly once you are more proficient in C++.

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

For people who complain that C2 is non computational geometry problems, I share my binary search solution: https://codeforces.net/contest/1354/submission/80487561

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

    Can you explain the solution

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

      If the square is without rotation, the minimum square will have spare space on one side. We consider the minimum rectangle, and rotate it. when the rectangle rotate, the long side of it will decrease while the short side increase. when it becomes a square, it is the answer.

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

        i believe this is also the expected solution. going on the problem now shows binary search and ternary search tags.

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

    This is actually a cool solution

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

this is a great round. thanks pikmike. those who downvote this round dont love math and cant realize beauty of geometry. it was a classic problemset. however i cant solve problem c2 and d , but i learned very much from these.

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

OMG, I just looked at problom E and misunderstood: |colu−colv|<=1 , then got no idea...

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

Ok, thanks in advance, I need help to know a thing. Today's Problem D(MULTISET) I user policy-based Data Structure (Orderset) and I assume that my code took (2n) Space Complexity, it got MLE. But I saw some solution used up to (4n) Space complexity (Segment tree) and yet that solution got Accepted (y). Can someone please help me to know why??

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

    Policy-based data structure is implemented as a balanced binary search tree, if I'm not mistaken. BBST has hidden memory costs associated with pointers, as well as with the augmented information on nodes (if I'm not mistaken, subtree size, which is used to determine the index of elements). Hence, it actually takes a lot of space because each node in the BBST stores a lot of information.

    Also, properly implemented segment tree should only use up to 2n space complexity. For struct segment tree, you can prove this by drawing the structure of the tree and observing that it is a binary tree with n leaf nodes, which means it should have n — 1 internal nodes.

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

      By "properly implemented segment tree" do you mean the iterative one? (all the recursive segtree implementation I know uses 4*N memory ) If so, how do you binary search on it?

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

        The memory consumption of recursive segment tree is in fact higher than iterative, but that is more of the fact that you need to store pointers to the left and right child nodes. In terms of actual number of nodes created, it can be proven to be 2N-1: each internal node is a union between two disjoint sets of leaf nodes.

        I don't use an iterative segment tree, but I think a similar logic to "seg descend" method could work here: you start at the root and check whether the left child satisfies your requirement. If so, go to the left child. Otherwise, go to the right child. Just code it iteratively rather than recursively.

        Edit: for the specific problem given, I think there is a recursive segment tree implementation that stores 6N 32-bit signed integers. However, given that it is 28 MB memory limit and this algorithm uses 24 MB, plus probably some overhead here and there, I'm not sure whether it passes. Intended solution is probably Fenwick tree or iterative (array) segment tree, not recursive (struct) segment tree.

        Edit 2: Just to check, I coded the struct segment tree solution. It MLEs on test 4.

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

          The iterative segment tree I'm refering to is this (using 2*N memory) and it treats the segment tree as a forest of binary trees, which makes it tricky to do binary search like the recursive versions.

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

            Actually for this problem because the limit on n, 10^6, is so close to the next power of two, 2^20, I think you could just create an iterative segment tree as described in that post with 2^20 nodes, which means that it's always a perfect binary tree, which should make binary search easier.

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

              That's a nice idea xd. Anyway right after posting that comment, I actually mananged to do binary search without changing the size by just storing all the roots when initializing.

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

          I applied the same logic using recursive segment tree with 4*n size and it passes easily ..you can check my submission here https://codeforces.net/contest/1354/submission/80530927

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

            I was talking about pointer-based struct segment tree when I said "recursive". Sorry about the misunderstanding.

            Yep, yours looks about right. Because you're using array indexing to keep track of left and right children in your segment tree, you don't need to store explicit pointers, which was probably what caused MLE for mine.

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

Lol even rating update and editorial release has been delayed.

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

    Is the system test is done? I didn't notice it...

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

      Probably not. Well I may be wrong.

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

        Bruh, the contest evaluation status is seen in the “standings” column of the “contests” page. And its been “Final standings” (Was “Preliminary Standings before that) since about 5:30 IST for Edu. 87. So it is indeed the case that ratings haven’t been updated but system testing is done.

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

          Not exactly. For Educational Rounds, the Final Standing appears both before and after system test.

          When the test details contain the hacks, it means that the system test is done.

          Sorry for my bad English. :(

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

            I'm pretty sure I saw it change. But if you want further proof, enter the contest and check the status on the right hand side. It says "practice". It usually says "system test pending" in case it hasn't been done.

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

              Now the system test is on :D

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

                Yeah, sorry...my bad. The signs were misleading. And regardless, your English isn't bad :))

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

          Obviously, those are not the final standings. You can see that still grandmasters and masters are there in the final standings (even after you click on show unofficial button).

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

          I hope you are now aware of the fact that your perception was indeed wrong.

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

Why the editorials are not out yet after 12 hrs to Contest.

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

    Maybe because the system testing is yet to be done.

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

      Why does system testing matter for releasing the editorial?

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

        If the editorial is out then people will hack others weak submissions by reading all the conditions from the editorial and thus their rating would decrease and this would be unfair because person didn't put his mind to find the flaw rather used the editorial

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

          Since the open hacking phase is over, why would that matter?

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

          It doesnt matter since the solution is going to fail in system test anyways. The hacker is not going to be benefitted since there is no reward.

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

            there is no system test for educational round as solution is already accepted and if your solution is hacked after the open hacking it doesn't affects your rating but it would affect if done within hacking period

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

              Seriously? I had no idea.

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

Why there are no editorials for this contest ??

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

When will this contest be rated?

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

    The rating calculations include some manual actions. The most persons usually initiating these actions live in a timezone where it is currently more or less early in the morning.

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

my BIT & O((q+n)log(n)) solution for probloem D

https://codeforces.net/contest/1354/submission/80567274

Just change binary search strategy a bit.

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

    Hi, I was trying similar in the contest. I got a Memory Limit Exceeded on test 4 80499850. Can you explain your modified binary search a bit, I was doing a conventional binary search in the case of deletion to find the minimum index for which getsum function of BIT will return k[i]. Can you explain these lines of your code:

            else{
            x=-x;
            int ans=0;
            for(int step=m;step;step>>=1){
                if(ans+step<=n&&a.d[ans+step]<x){
                    x-=a.d[ans+step];
                    ans+=step;
                }
            }
            a.add(ans+1,-1);
        }
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      know little of python, sorry.

      In my BIT, I usd array d[n+1] to store the amount of numbers, like

      n=8

      mutiset: 1 2 3 4 5 6 7

      d: 1 2 1 4 1 2 1 7

      when get q: -6, I try to find bigest ans, while less than 6 numbers is in (0,ans]

      guess ans=8, d[8]=7 numbers in (0,ans], too big

      guess ans=4, d[4]=4 numbers in (0,ans], ok

      **so, the final ans is at least 4. I still try to find bigest ans, while less than 6-4=2 numbers is in (4,ans] **

      ans=4+2, how many numbers are in (4,6] ? d[6]=2 , too big

      ans=4+1, how many numbers are in (4,5] ? d[5]=1, ok

      final ans=5

      less than 6 numbers is in (0,ans]

      NOT less than 6 numbers is in (0,ans+1]

      so ans+1 is the 6th number

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

I read various comments regarding the quality of the problemset. I totally agree that B C D were easily found on web and this is a bad practice in rated contests . But frankly speaking, many might have learned binary search with BIT , lots of concept related to regular polygons. Atleast I have learned few new concepts. So until and unless there is some learning for everyone in the contest, it is a good one .

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

    Also, the Educational Rounds are for this purpose only. If somebody would read what the Educational Rounds are all about here: https://codeforces.net/blog/entry/21496, he/she can clearly notice that these rounds are not for competition but to gain knowledge about the data structure, algorithms or techniques that one might know already. And for those who know them, it is just a practice for them.

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

When will this contest be rated?

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

It was a good game! Many stupid people criticize the game just because they didn't finish the problem, it's ridiculous

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

editorial?

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

It's taking a longer time to get system testing started. I wonder when it will start.

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

I really liked problem G! I solved with a randomized solution. I assume $$$N \geq 5$$$ in the solution written in following.

Step #1. Find one stone between $$$3$$$-rd to $$$N$$$-th box
Because of $$$N \geq 5$$$ and $$$K \leq 0.5N$$$, there is at least one stone between $$$3$$$-rd to $$$N$$$-th boxes.
Let's take $$$G$$$ boxes randomly in $$$3$$$-rd to $$$N$$$-th boxes. Here, in my solution during the contest, I set as $$$G = \min(N - 2, 23)$$$.
Since at least half boxes contain stone, the probability for all boxes to be gifts will be at most $$$2^{-G}$$$, if $$$G < N - 2$$$. If there is at least one stone, compare weight of two boxes $$$G-1$$$ times, and the heaviest one is the stone.

Step #2. Find the range that "no gifts in box $$$1$$$ to $$$x$$$, but at least one gift in box $$$x+1$$$ to $$$2x$$$
First, we'll check if there's no gift in box $$$1$$$ or $$$2$$$. You can check by comparing weight of this box and the stone found in step #1. If there's, we got the answer. Otherwise, we ask the question like following:

  1. Is there any gift in box $$$3$$$ to $$$4$$$? We can get by comparing weights of boxes $$$1$$$ to $$$2$$$, and boxes $$$3$$$ to $$$4$$$. If there's, then terminate by setting $$$x = 2$$$.
  2. Is there any gift in box $$$5$$$ to $$$8$$$? We can get by comparing weights of boxes $$$1$$$ to $$$4$$$, and boxes $$$5$$$ to $$$8$$$. If there's, then terminate by setting $$$x = 4$$$.
  3. Is there any gift in box $$$9$$$ to $$$16$$$? We can get by comparing weights of boxes $$$1$$$ to $$$8$$$, and boxes $$$9$$$ to $$$16$$$. If there's, then terminate by setting $$$x = 8$$$.
We continue until we found and double the range for each iteration.

Step #3. Find the least-index boxes in $$$x+1$$$ to $$$2x$$$ that contains gift
We find the least $$$p$$$ by binary search that holds following:
  • (weight of boxes $$$1, 2, \dots, p$$$) to be larger than (weight of boxes $$$x+1, x+2, \dots, x+p$$$).

The $$$p$$$ will be the requested answer! If $$$N \leq 1000$$$, we will use at most $$$23, 2+9, 9$$$ steps in step #1, #2, #3, so it asks $$$43$$$ questions. My submission is 80502712. You'll learn a lot about binary search if you solve this problem.

Anyway, I'm so honored to get the 1st place (though system test is yet to start) in this round! Thanks to awoo and other writers for organizing this contest.
→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

by chance, the round didn't become unrated, creators((??

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

Wait, is there any test case with $$$m>5000$$$ in E? The constraint says $$$m\leq 10^5$$$.

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

So,after this round,Is it any round exists recently?(except Kotlin Heroes)

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

Is this round rated?

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

Why ratings aren't updated yet?

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

when do we get editorials for Educational Codeforces Round 87 ? waiting since yesterday

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

People who are waiting for editorials....

Try this

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

Comment deleted!

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

I want to know when to start the final system test

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

Seriously, someone should atleast confirm when would the ratings be updated. This is really sad and frustrating

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

    Yeah, its been almost 24 hrs to when the contest started yesterday and yet the ratings haven’t been released. Why isn’t the process automated?

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

what's going on?? it's almost 24hours

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

Why it happened again?

10enf1.jpg

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

when will the system testing start?

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

Please refrain from downvoting the announcement. Author put in considerable effort to come up with good problems. Late release of rating changes has nothing to do with him. Even if you are angry for late editorial and rating changes etc.. please don't downvote.. the author deserves that much atleast for his effort. Thank you.

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

Can somebody tell if this contest was up to the mark in any aspect? (2 times delay in starting time, delay in editorials, delay in system testing, delay in rating changes, googlable solutions for C1, C2, and D, it's more like a codeforces delay round instead XD)

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

    I agree with your point. But I hope as per submissions in C2, D there are very less submissions .So most does not get googlable solutions.

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

System testing finally started :D

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

OMG... Why can't you all just sit and wait? Instead, everyone would downvote the contest and add his "super important" comment about how much pain it is for him to wait.

You know what real pain is? I tell you what. Finding something relevant to the contest while reading your senseless comments about how long you've been waiting for your rating to be updated after crushing the round with getting accepted googled solutions with no idea of why they pass system tests. Not to mention the fact the browser goes mad loading all these comments.

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

    Waiting is acceptable, just worrying about waiting for so long but suddenly announce unrated.

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Screenshot-194.png

Alisher_Kamolov's hacks. Seems like cheating.

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

I tried to use segment tree in Problem D and I submitted exactly the same code twice. One using GNU C++17 (64) got TLE (80590272), the other using GNU C++17 got AC (80590625) with the time only 873ms.

Can anyone kindly provide an explanation on this? Thanks.

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

Rip no update yet, its been over an hour since the system testing finished...

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

    cf-predictor-frontend.herokuapp.com/ This is the link to get prediction of rating change. The rating may have error of +5 to -5. Thanks.

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

Is this announcement with maximum comment and minimum votes?

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

I am glad that my name is among yellow's and red's (in first to solve each). I never imagined that this is even possible (for a person like me).

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

In problem B, I have used the binary search logic by storing every occurrence index of '1','2' and '3' and submitted the code in the contest with verdict accepted. In the code I have checked whether it is possible to have substring with all the three characters present in it by multiplying the sizes of the 3 vectors storing the indices and compared it to zero. It went wrong on test number 41 in system testing as it gave output 0.When I submitted the code by comparing individual sizes to 0 it got accepted. Initial Submission(accepted in contest and wrong on test 41) — https://codeforces.net/contest/1354/submission/80476580 Final Submission (accepted on all test cases) — https://codeforces.net/contest/1354/submission/80621256 Can someone clarify!

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

    In your if statement, the product of all three vector size are overflowing. By just adding 1LL in front of it, your solution got accepted. https://codeforces.net/contest/1354/submission/80627780

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

      But can you tell me why is it overflowing insider_pants? It's well within the limit of LL

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

        what you did originally was you just multiplied the sizes of all three vectors but by default compiler typecasts the size of vector into int. So basically, you were doing int * int * int and int has limit of around 2*10^9. It can overflow as the size of the string is in range of 10^5. By adding 1LL in front of it ensures that the compiler typecasts all the sizes into long long and then multiply and now the product cannot overflow.

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

There is no upcoming div-2/3/4 or edu contest on the list. It made me sad.

→ Reply