DishonoredRighteous's blog

Codeforces Round #643 (Div. 2)
By DishonoredRighteous, history, 5 years ago, In English

Hello, Codeforces!

I'm glad to invite you to Round 643 which will start at May/16/2020 14:35 (Moscow time). Please notice the unusual time.

There will be 6 problems in round, one of them will be interactive. If you are not familiar with interactive problems, you can learn about them here.

Round is based on Team Olympiad in Lipetsk which is being held for the fifth time. Problems were prepared by fake123, iura, Masha237, Villen3tenmerth, Inessa Shujkova (Lipetsk teams' coach) and me. I would like to thank antontrygubO_o for CF round coordination and testers: KAN, I_love_Tanya_Romanova, vepifanov, Merkurev, golikovnik, Ekler and some other people who asked me not to write about them :)

Of course, I'd like to thank all Codeforces team for this beautiful platform!

Scoring distribution will be announced later.

Wish you good luck and high rating!

UPD.1 Scoring distribution: $$$750-750-1250-1500-2000-3000$$$.

UPD.2 Editorial is available here.

UPD.3 Congratulations to winners!

Official participants:

  1. NaimSS

  2. tianxiawoyou

  3. Lomk

  4. wisteria0410ss

  5. TheOneYouWant

Unofficial participants:

  1. risujiroh

  2. jiangly

  3. 244mhq

  4. hitonanode

  5. turmax

UPD.4 Full problemset from the olympiad is available on gym: The fifth Lipetsk collegiate programming contest. Finals. 8-11 form

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

Comments Comments (241)
| Write comment?
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).

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

    A bet:

    Spoiler

    So miserable.

    Just joking.

    Edit: Why are you downvoting me? I said I was just joking.

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

      I am the type of guy that don't want to hurt peoples.

      But really you are the worst joke teller I've ever seen.

      Sorry.

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

      Please don't spread this kinda demotivating jokes. Especially it's hurt peoples those works hard to make the round successful.

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

      People are downvoting as using nested spoilers doesn't make it a joke

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

Thank You MikeMirzayanov, for excellent Codeforces and Polygon platform.

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

is it rated?

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

    IT IS GONNA RATED OR UNRATED DOESN'T MATTER... MY COMMENT GONNA GET DOWNVOTE...i don't know why though.

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

Excited about the solo div 2 round after a long time.

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

Is it me or anyone else observed, bulleted list make announcement look bigger!

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

Yay! Another contest, hopefully I get a positive delta, as I have got a very bad feeling about my rating after how bad my previous contest went :P

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

it's been long time since we solved last interactive problem

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

Thank you Code forces Team and all problem setter for this contest frequency in this pandemic time.

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

Google jam round 2 is just after this round. 4500 participates has qualified for this code jam round and most of them wouldn't prefer to give two contests in a row... So wouldn't it be great if the contest is rescheduled to 18th May? So that more people could participate.

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

    I don't see any problem here. There is almost 30min break between contests, for some people it's even better to solve a few problems before contest. There were a lot of situations with multiply contests in one day.

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

      I am agreeing for some people there performance improves if they solve some problems before a contest but there is also another type of people who prefers a cool mind before a contest.So if the contest is rescheduled, then both type of would get the chance to prepare themselves to the fullest as well as participating in this round...

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

        See the point is, if you are in div 2 and thinking that you are going to be in top 1000 in codejam then you are either lying to yourself or living in world of fantasy or will be some mere coincidence

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

          Maybe you are right, it would super hard for me to be in the top 1000. I am still a beginner, I need to improve myself a lot. If I don't do different types of contest, how would I improve! I would definitely going to aim the top 1000, so that I can do my best and most importantly improve myself!

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

            I will also have to skip this round because of the Code Jam. Get what you are saying. I also perform poorly with 2 contests a day. But I think the unusual starting time is maybe because of the Round 2.

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

      25 minutes not 30 :D

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

    There are 25 minutes between Codeforces Round finishing and GCJ beginning. Of course it's not too much but in my opinion it's not a problem. I also don't think we can reschedule this round to 18th May because it's based on olympiad which is scheduled for 16th May. Some participants can start discussing problems and it will ruin the round.

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

I want to thank the author. Hope all the participants can achieve higher rating after this contest, especially me.

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

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

    and when mike actually considers your request making the contest rated

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

    "Decrease by -100" actually means "increase by 100"

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

.

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

Three contests back to back! Thanks for saving us this lockdown

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

what will i get if i get a succesfull hacking attempt? i mean how will it affect my rating?

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

    You will gain points, like when you solve a problem. So you will be better at standings.

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

      Thank you...But even in Div 3??

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

        In div.3 there's no points/penalty for (un)successful hacks.

        In div.2 100 points for a successful hack, -50 points for an unsuccessful one.

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

![ ](41h4pd)

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

    Oops, I am lated for the contest. Nevermind, I will try my best solving problems ^^

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

Can I get 100 downvote?

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

    You got 140 as of now, hehe peoples hands are itching to give down votes.

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

The starting time is very considerate for the contestants participating in Google Code jam :D

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

Long time no interactive problem! Look forward to it.

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

hoping for strong pretests this time

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

    please change your fucking profile picture

    edit: thank you!

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

I need to delete the original comment just to say this. For f*ck sake.

Seriously, Codeforces community has a major problem. Not all of them, but some of them. They keep disliking comments, whether it is good or not. This is not good and need to be changed.There are a lot of nice comments and they are so underrated.

I don't say this just for my comment, but for all negative comments out there.

Recently, arrogant and memes are getting so much upvotes, while others are not.

The underrated comments are having so much downvotes because they are having a movement against the commenter.

So please, vote properly. Every comment is just the commenter's ideas and doesn't deserve to be downvoted.

Again, I don't say this to my comment. But, if you downvote someone that has literally good comments and innocent, you are a loser.

That's all I have to say. Vote properly, or you will make the Codeforces community worse.

STOP BEING RUDE TO PEOPLE.

I tried to be polite, but I need to say this.

Thanks for reading.

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

    a simple advice .. don't take downvotes personally anyone's comment could be downvoted just don't post your meme unless you think it's funny in the previous contest I had no funny memes in my mind so I didn't post anything if I did put some meme that isn't really funny I'll get downvoted as well let your comment adds something new if it doesn't it will look like a noise and will get downvoted probably

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

      Thanks for your advice! It helped me so much...

      (hmm... Interesting.)

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

    The comment section of an announcement is supposed to discuss about the round such as time, quality of problems, solution etc. People looks for informative comments here.

    Making jokes, sharing meme on same topic and same idea doesn't make any sense. It gets boring. Discussion on irrelevant topic such as contribution, downvotes are also not good topics to discuss in an announcement.

    People gives contests here and solve problems so that they need to discuss something here. Don't make it like we need contribution so we solve problems and give contest.

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

      Nahh, As long as the memes are good it's a win-win

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

        But posting same memes or posting memes on same idea again and again is really irritating.

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

would be my first round as an expert

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

I am new in cp.i don't understand the contest rating system of Codeforces. Plz someone tell me about it.

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

I think Codeforces-Logo needs a Mask of different color as Masks need to be changed after some time !

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

There's much mystery in this contest announcement:

  1. Why is DishonoredRighteous righteous yet dishonoured?
  2. Who is I_love_Tanya_Romanova's love Tanya Romanova? (is she Tatiana Romanova??)
→ Reply
»
5 years ago, # |
  Vote: I like it -95 Vote: I do not like it

_**its iftar time in bangladesh. so u need to change the time otherwise contestants will be decreased dramatically. _

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

    otherwise contestants will be decreased dramatically

    Nice, smaller queue!

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

    .

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

      Every time it is on weekday during school days many American high school students can't take part, yet they don't complain every single time it conflicts, and that is many more times than because of iftar. It's not about religion or really even when most people can take round, it's about when problem setter can have round and have semi-consistency with times i.e. being within a few hours of normal time, and no matter the time some people will have conflicts. In other words, just deal with it.

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

It must be a good contest.

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

Is it rated? (Let's have -40 likes)

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

Educational Codeforces Round 87 (Rated for Div. 2) — May 17th (14:35 — 16:35 IST) clashes with Google Kickstart Round C 2020 — May 17th (16:30 — 19:30 IST). If this is a problem for many codeforces participants, please consider rescheduling Educational Codeforces Round 87.

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

That's great. Consecutive contests for 2 days.

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

am i the only one who can not spell Lipetsk (~˘▾˘)~ (~˘▾˘)~

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

Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).

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

My rating has been increasing since 7 contests, hope to continue streak.

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

I would compare div. 3 and div. 4 peape to paralympians. I hate pupils newbies and specialists. They should give up programming.

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

    first, change your profile picture. It scared me.

    second, you need to know that you are still a newbie. you shouldn't say something like that, especially when you are one of them.

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

      He got what he deserves Downvotes :P

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

      Lol this is my alt account, Can you guess? That's why you deserve to be noob...

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

        so be polite to everyone.

        You are not a noob for solving contests, but you are a noob at making content.

        Sorry for not being nice to you. I need to say this for everyone you hate, including me.

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

        Are you trying to make a record for most downvoted comment?

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

750 points for problem A. Is it for the first time?

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

While quarantine, time is always usual. Stay home, stay safe, do coding.

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

This is a friendly time for China.

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

Interactive?? In this round, Im in the rated ~~ BAAAAAAAAMMMMMMM

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

When you start to submit problem F...

Submit...

WA on pretest 5.

"WTF!!!"

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

Is the difficulty level of A and B same ?

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

bad time

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

I think A and B will have nearly the same difficulty and A might also be a little harder than usual A problem in the rest Div.2. Just guessing based on the Scoring! Hoping for a great contest!

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

Stop making contests with unusual time please :( many participants have trouble with this new timings, like coincide with university or school online class, Iftar time in Muslim countries, and ... You try hard about one week to make a beautiful contest but you annoy many participants because of the unusual timing(I'm sure you have your reasons for that but I think they aren't enough to change the usual time about 2 hours)

EDIT : Sorry, I didn't know the Google Codejam time :(

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

    First, you don't know about Code jam? It will be starting 25-30 minutes after the contest. It would be annoying to almost every Code jam users that is using both 2 webs if we delay the contest by 2 hours.

    Second, if you don't feel fine with unusual time, enjoy your thing with your family, friends, and participate in other contests in the future. Your rating won't change.

    If you want, you can give virtual contests a try. I hope it would be good for you :)

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

      Sorry, I didn't know the google Codejam time(Google Codejam is unavailable for Persians because of USA sanctions, so I wasn't aware of that)

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

Codeforces is the best platform to develop your cp skills. Thank you codeforces.

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

My first contest after Candidate Master.I hope good for me!

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

Why do I see all the normal comments downvoted?

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

The time is friendly to Chinese students!

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

The second earliest announced score distribution in Codeforces history !

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

I love Div.2.

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

Registration for educational codeforces started, so we would find masters in educp rated.

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

sorry-forces everywhere . . .

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

In problem D, does the subarry have to be consecutive?

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

I remember registering for this contest but am not able to make any submissions . the system message says that I haven't registered. where exactly am I going wrong?

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

C and D should swap their positions.

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

    so should A and B

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

      idk, i did A in one go but made 1 wrong submission in B, that was the case with a friend too, iterating through the array in reverse after sorting(ascending) seemed to be more intuitive for me, but that was obviously wrong.

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

If not F, it could easily be an Educational round.

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

F is so weird

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

how to solve A.I have know idea after two hours of thinking. Pls help me somebody.

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

    0 will appear some time, you can just simulate the process till a fixed point i.e a = simulate(a) then stop

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

    minDigit(a_n) will become 0 rather quickly and then your answer does not change anymore, because 0*x == 0

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

Video Tutorial for C

Enjoy watching!

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

Awesome contest!!! During the first 30 min, I was like holy shit!!! none accepted ...which question to try...

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

How to solve E?

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

Am I the only one, Who try to consider each one in one of the group. Problem B.

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

I solved D, but can't prove solution.

I can prove solution in C, but can't solve it :)

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

    How you have solved D? I solved C, but can't D.

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

      https://mirror.codeforces.com/contest/1355/submission/80328985

      $$$K = S — 1$$$. There should be no $$$i$$$, that $$$a[i] = 1$$$.

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

        Can u give the proof for A.How can we prove that the solution terminates after some number of steps?

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

          Firstly, $$$1 \leq minD * maxD \leq 81$$$. Secondly, let's notice that $$$0 \leq \frac{a[i+1]}{100} - \frac{a[i]}{100} \leq 1$$$. It means that $$$minD = 0$$$ in $$$a[901].$$$ Therefore, $$$a[901] = a[902] = a[903] = \dots$$$

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

      In D you could make the array like 1 1 1 1 n-1 times and then S-n +1. In this way only possible sums are between S-n+1 to S both inclusive and 0 to n-1 So Just check if the union of both ranges is not 0 to S , as long as its that a K can be found, n<=k<=s-n and s-k would also fall between that same range. So you can't find s-k also.

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

    My solution is easy to prove:

    https://mirror.codeforces.com/submissions/Leonardo_Paes

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

C: "Non-degenerate triangles".

CF users:

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

Solved C and D but couldn't solve A and B ,I was blank for the fist 30 mins XD

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

    When you will get to know the solution of A, then you will be surprised possibly. I was laughing at myself. peace!!

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

Specialist rank here I come...

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

lol I used FFT in C.

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

    Wait what?

    I still don't know where FFT is usefull and know even less about what FFT really do, and I destroyed two forests with draft copies, please, save the earth and tell me how to use it xD

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +32 Vote: I do not like it 
      tot = 0
for (x = a; x <= b; x++)
  for (y = b; y <= c; y++) {
    for (z = c; z <= d; z++) {
      if (x + y < z) tot++;
    }
  }
}

      The naive solution is like that. Basically, I just create two polynomials X and Y. X = 0 + ... 1x^(a) + 1x^(a+1) + ... 1x^(b) (everything is zero before a) Y = 0 + ... 1x^(a) + 1x^(b+1) + ... 1x^(c) (everything is zero before b)

      I multiply the two using FFT in O(nlogn), then we get polynomial product. We check all terms in the product, and count how many z (third side) can we build using it.

      I know there are simpler solutions, but my brain is tired today lol

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

    If you want to solve it without using FFT. It can be solved easily, by some pref arrays(two). you can see my submission.

    Note : x + y > z Hence i made a prefix array for all possible values of z — y.(x > z — y). and then make another prefix array in which, pref2[i] denotes total number ways to obtain sum < i.

    so we can simply iterate over all x.

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

      I didn't say there is a need.

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

        No offence, but i am trying to say like this. My intention is not to harm you, but just want to say that, there can be easy way !! sorry, if i offended you.

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

    what FFT means? i solved C by fixing x and finding optimum y and z in o(1) time https://mirror.codeforces.com/contest/1355/submission/80351154

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

Newbie rank here i come...

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

    IF D would be A it would have at least 10000 sucessful submissions. Poor score distrubution

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

Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).

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

I can say that when the writer(s) are writting problem F, they are listening to something interesting...

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

It's only my opinion, but I found the C waaaay more difficult than the D. It tooks me like one hour to do math and two paper sheets died in the C, and the D tooks me 10 minutes and 1 minute of thinking... or maybe there were some formula that I didn't knew about which would be very helpful for the C ?

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

Maximum solved doesn't cross even 8000.Hardest round without a doubt.

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

Problem writer should have boldened this line "It's not necessary to include every explorer in one of the groups: some can stay in the camp" in problem B. Created a lot of trouble for me today.

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

    Same, Like when there these types of conditions, Generally It is written in the Note section.

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

C and D should be exchanged.! C looked pretty easy at first, but gave a Hard time because of so many corner cases!

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


Tbh the contest is really good. Regardless the hard C.

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

    I found C rather easy to think but troublesome to implement. Had to think exhaustively forthe edge cases and ultimately that took more than an hour in the end. Let's hope it doesn't fail the system tests :)

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

I can't understand why am I getting a TLE if the code was submitted in C whilst the same code being submitted in CPP gives me AC.

My code : https://mirror.codeforces.com/contest/1355/submission/80368483

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

RIP codejam

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

If the problems are meant to be in the increasing order of their difficulty then the setters should strictly follow it.

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

Irritating A. I could not think of any logic, then I just wrote recursion, and surprisingly it was terminating to a single value every time. Can anyone explain why it settles on one value. Is it not possible for minimum digit to be never zero. And for the fact that C was much harder than D it should have more points.

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

    Maybe it's possible for the last digit to never be zero, but since the number increases by at most 81 every time (in the absolute worst case), the third last digit can't skip over zero, and since in each iteration (before any digit becomes zero) the number increases by at least 1, it will take less than 100 iterations.

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

    Note that the maximum term that can be added ever to a(i) is 81. We start from a[1] and keep adding terms to obtain new a's. Now as soon as the thousands place changes (i.e. increases by 1), the corresponding hundreds place will always be 0. This will obviously take less than 1000 steps.

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

      Thanks finally understood what you are trying to say. if a number less than 1000 (let's take 987), if it crosses 1000, than 100th place has to be zero because we can add maximum up to 81. In this case a(i+1) = 1050 (987 + 7 * 9).

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

ahhh shit, starting from C was bad strategy mehn

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

How to solve E? Is it 3-point search?

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

Solved A, B and D, but all of them just a guess. Would not be suprised to fail all three of them in system testing.

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

Difficulty level : A>B && C>D .. Not sorted and even I can not solve A but solved D .

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

    for A, key observation is when min_digit = 0 then next numbers will be equal

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

Constructive Forces!

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

Why problem E satisfy binary search?

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

    ternary search

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

    I solved it using binary search on the answer.

    The graph of the cost vs height would be a parabola. So the only thing monotonic is the slope.

    So find the cost of building walls of height mid and then also find the cost of mid+1 and mid-1.

    this would give you a fair idea as to where the slope is negative.

    The binary search conditions would be:

    • if ( val( mid+1 ) < val( mid-1 ) ) then high = mid-1
    • if ( val( mid+1 ) > val( mid-1 ) ) then low = mid+1

    and always keep updating the answer as minimum of previous answer and val(mid)

    Link to my code

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

The pretests for Problem D were weak. Solutions only considering K, not S-K were passed. They should have included test case like 

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

I solved C.

I guessed A,B and D.

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

How to prove that choose k=1 and a[i]=2(except the last one) in D is the optimum solution? I attempted to prove it in the contest but failed. Wasted a lot of time...

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

I wasted one hour on C, and still wasn't able to do it. Could have easily done D in that time. Waiting for the C problem editorial.

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

    Editorial is published? Why are you waiting?

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

A think more code less round. I like this although i can't complete thinking of C in time.

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

In problem D, can the selected array contain 0?

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

    Nah. Positive integers its integers >= 1. Non negative integers its integers >= 0.

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

      I see, Didn't know that. I thought positive integers include 0. Thanks.

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

    No, as described in the statement "positive integers".

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

    No we can only take positive numbers in array not non negative numbers.Though even if you have confused it with we can choose k=0 then the other player can always find S-k=S by taking the whole array

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

      what if we take (n-1) 0s and 1 S and take k = n/2?

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

        Yes that would have been possible if you could take 0 but since we can only take positive numbers it is not a suitable answer.

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

Can anyone please tell me why this submission for problem A got TLE? https://mirror.codeforces.com/contest/1355/submission/80313479 Similar solutions got ac.I don't know why!

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

    Does this cast work as expected? l = min(l, (int)n%10);

    If it casts n instead of the remainder it would fail.

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

    My bad, I thought of something else

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

    It is possible to get negative reminder, when n = 2^31, your cast will return -2^31.

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

How about we have strong pretests once in a while? D had >= 21 pretests, so I thought my logic was solid and I should not waste my time on thinking over it, and now I got it failed at test 24. Amazing.

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

Does anyone know why my solution for B got TLE https://mirror.codeforces.com/contest/1355/submission/80331871? I can see that other similar solutions submitted with PyPy2 got accepted.

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

    Use fast input/output. Did the same mistake :(

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

codeforces setters be like

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

I wonder what is this pretest 24 of D many people are failing on it

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

The pretests of F are extremely "strong". :)

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

Almost 70% of the pretest-passed submissions to Problem F failed on system tests... What a scary ratio...

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

I got a WA on test case 5 of Prob C. When I ran the same test case on the same code in my system, I got the right answer. Can somebody tell me when does such a situation arise? I had used the same logic as given in the Editorial.

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

    Link the submission here, somebody will tell you why it fails.

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

BADC

Find the minimum number of swaps to sort the contest. Still a good contest..Thanks for efforts :)

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

C and D should swap their position

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

When does rating gets updated?

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove the cheaters, fix wrong division cases and update ratings them again!

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

Can someone pls explain me the 1st question ie Sequence with Digits of today's contest,I have seen the editorial ,but then also I am not getting the thought process behind the sol of other people. I would be so thankful if any body can help me

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

    Have you understood the problem? If yes then just implement it straight forward. Just keep in mind that once you get 0 as min digit then the no will never change. So you can break when you get 0 as min digit.

    The fact is proof of solution that it will not exceed tl and overflow 64bit integer.

    As min*max can be atmost 81 so you can't add more than 1000 as one of the digit will be 0 by this time.

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

Does anyone have a faster solution on E

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

@DishonoredRighteous It says TLE for O(n) solution in Pypy 3 after system testing, same code works in Python 3. Can you please check the time limits. Thanks

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

    Problem B

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

      There are many solutions that didn't pass TL on Python. It's hard to read $$$5 \cdot 10^5$$$ numbers in Python.

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

        So, will there be any changes in the time limit or shall we just take it as a lesson? :p

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

          It's a well known fact that Python is not very fast :) So there won't be any changes. What is more, there are some solutions on C++ that din't use fast IO and got TLE too. I think participants should know about their language's qualities.

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

            Is there any reason for rolling back the ratings?? Please let us know if you know. Thank you

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

Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).

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

Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).

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

Hello, I don't know why my solutions are giving TLE on Test Case 22 for Problem D. Can someone please help?
Solution 1
Solution 2 — this was taken from Ashish Gupta's C++ solution. I just wanted to check whether it is being accepted in my case or not. But its the same story.

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

I think problem E is so easy and I solve first 5 problems in only one hour while I only can solve less than 4 pronlems in others div2 rounds...

I can't believe it is div2(and thank for +83 lol).

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

Wrote in wrong competition :)

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

why set is slower than map in STL?
For 643 div2-B, the same algorithm with set TLE (test #26) but map AC.
set code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+10;
int T, N;
int e[MAXN];
int cnt[MAXN];
set<int> s;
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &N);
        memset(cnt, 0, sizeof(cnt));
        s.clear();
        int e;
        for(int i=1; i<=N; i++) {
            scanf("%d", &e);
            cnt[e]++;
            s.insert(e);
        }
        int ans = 0; int rest = 0;
        for(auto e : s) {
            ans += (rest + cnt[e])/e;
            rest = (rest + cnt[e])%e;
        }        
        printf("%d\n", ans);
    }
    return 0;
}

map code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+10;
int T, N;
int e[MAXN];
map<int, int> mii;
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &N);
        mii.clear();
        int e;
        for(int i=1; i<=N; i++) {
            scanf("%d", &e);
            mii[e]++;
        }
        int ans = 0; int rest = 0;
        for(auto e : mii) {
            ans +=(rest + e.second)/e.first;
            rest = (rest + e.second)%e.first;
        }        
        printf("%d\n", ans);
    }
    return 0;
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your set code seems to have a excessively common problem: the line memset(cnt, 0, sizeof(cnt)); dominates the running time for tests where there are very many small test cases, as it clears the whole array every time.

    → Reply