PuRpLe_FoReVeR's blog

Codeforces Round #632 (Div. 2)
By PuRpLe_FoReVeR, 5 years ago, In English

Hello, Codeforces!

I'm glad to invite you to my first round Codeforces Round 632 (Div. 2), which will take place on Apr/08/2020 17:35 (Moscow time).

"Thank you" time!

I'd like to thank:

You'll be given 6 problems and 2 hours to solve them. Point distribution will be announced as soon as possible.

Hope you will enjoy the round! Good luck and have fun!

P.S: YES, IT'S RATED.

UPD: Score distribution: 500 — 750 — 1250 — 1750 — 2000 — 2500.

UPD2: Congratulations to the winners!!

Div2:

Wow, there is no unrated in div2 round!

All:

UPD3: I will post solution in several hours.

UPD4: It was very long several hours, I'm very sorry for that :( Editorial

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

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

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

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

I'm sad because I won't be able to score in this round

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

    why not?

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

      I think Masters aren't trusted participants in Div 2.

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

    Hope your dream of become rated in div2 contest come true one day

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

why aren't there more contests?? :(

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

    Because it takes time and effort. You can solve practice problems at any time.

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

      :v

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

        You can solve practice problems right now and become expert in only one rated contest!

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

          But... This requires work... I want instant gratification! (•̀o•́)ง

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

            But there is no shortcut for instant gratification in competitive programming.if u practice more then u will need less contests to become expert.

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

    You can find list of competitions on other platforms here

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

Good Job. It is your first contest. I hope it will be good

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

I think I saw a few days ago that the round was of 2.5 hours. Correct me if I am wrong.

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

    Its true and it was my mistake. Sorry for misleading. Round will be 2 hours long.

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

Hoping for no queueforces and strong pretests!

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

Is it really RATED???????

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

isitrated?

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

is it rated?

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

    Of course rated.It's a normal division 2.

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

    Why are so many people asking this question over and over again？

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

Many contestants had trouble entering competitions at work and study times, but now everyone in home, so let's have fun. good luck everyone ^_^

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

rtd?

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

Darn had to be one day before my birthday T-T

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

I hope strong pretests are there this time.. Can't we have both strong and small number of pretests?

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

I hope to become a specialist in this round!

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

*Codeforces round starts*
Codeforces servers:

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

    Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com.

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

I hope to get Candidate Master in this round!

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

    You didn't even participate...

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

      Perhaps he started, and did not submit anything. Like me.

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

        Thanks, you both didn't participate, otherwise my rank must be (current_rank + 2)

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

      I just had a sleepless night, so I skipped. It was unfortunate. However, I participated today but was slow on D. I will try my best on the next one!

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

Congrats on your first round. Looking forward to solve your problems

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

contest made life easier to pass quarantine

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

GO CORONA CORONA GO ....

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

Ｉ got 2 "fst" in the last round, then I became blue. So I hope this round will have strong pretests.

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

Any suggestion how should I practice to become a blue coder? Nowadays codeforces is giving hard implementation problems in c no and I find it hard to solve somehow.

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

    Solve a lot of Div. 2 C and D problems, they are great for practice. Also, try to upsolve at least one problem after each contest. For example, I see you solved A and B in the last contest. Try to solve C, it's a good problem.

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

May i ask how many hours you and whoever helped you with making problems in polygon spent on the contest?

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

    Hm, I don't know... Maybe about 15-20 hours I was spent only with polygon, without creating test scenarios and problems, just for writing code and statements. It took much longer to come up with the tasks (~1 year). But it was passive work. One month I didn't do anything, and the next I create 2-3 tasks.

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

      Thanks for reply, i hope you get better and better in problem-setting, i think 20 hour is very nice for the first time :).

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

      Thank you for putting in the effort to create the contest! Wishing everyone luck.

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

Congrats, I'm excited :) I hope there is going to be more contests.

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

Constest starts... ... Codeforces servers down

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

If we register for the contest but don't enter it. Will my rating still go down?

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

    If you don't submit anything, it doesn't count as a participation.

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

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

We want more contest!!!!!!!!!!!

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

    Don't be so entitled, just be happy for the contests we get and for the efforts that the creators put into it. If you want more contests you can solve old ones at any time.

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

Any particular reason for thanking antontrygubO_o twice for coordinating the round?

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

    This round would not have existed without his help during the entire preparation process. This is my way of especially thanking him :)

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

    I think if someone accepts my contest proposal after 3-4 months or more, then i would be too happy to just thank whoever accepted my contest less than 2 times, or maybe just because anton helped him with making problems(then its one for accepting the proposal and reading it perfectly, and one for helping with making problems as a coordinator).

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

Even if there aren't a lot of contests on CF,there are a lot of contests on different platforms.Stay inside and safe!

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

Codeforces contest coordinators have been pretty lazy recently. Bad pretests, not many contests to begin with. Out of all the contests they still turn out bad.

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

    I don't think you have a good understanding about coordinators' work, they are not making contests, they check contests made by Codeforces Community and help them to prepare the contest as well, which really takes time.

    Maybe it takes 2-3 day to prepare a contest, and there is tuns of contest proposals, it means tuns of tuns of problems, reading a contest should take about two hour at least, so even if 4 man are working 6 hours a day for preparing contests and checking contest proposals, then they can at most check 10 contest proposals in a day, which i dont think is enough for such a big community.

    So guess what, can coordinators spend some time on they're own?, far away from working and reading random proposals? for sure they have to sleep.

    I know there is few number of coordinators, and not all of them work full time for codeforces, probable the only way to increase number of good contests is to support community to make contest proposals more perfectly and prepare they're contests faster(codeforces is really doing it very well i think), or if the problem is the really long queue of contest proposals(which i think is the case), they may increase the number of coordinators and support them.

    Fully related to the topic: I wanna be a coordinator later in my life, so i should plant the seeds from now, yes? =P

    → 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 +1 Vote: I do not like it

@ReD_AwHiLe hoping for the short statements and strong pretest.....?

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

We want more contest in this quarantine :(

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

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

    I don't understand why people commented asking this and got lots of downvotes, though it's clear in the post.

    Maybe people are getting bored staying home and commenting to have fun.

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

    Is she rated?

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

    And then you make memes xD

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

Div 1 coders in Div 2 contest everytime

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

Please arrange more contest during these corona days. :p

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

I can't able to submit solutions in JAVA, getting RUNTIME error, tried with previous accepted submissions. I don't know where to post this, this site doesn't even have a contact page.

Got it I forgot to remove package declaration at top.

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

    Better post a link to one of those submission, then somebody can tell you why it fails.

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

hope this contest not to be like previous one !!

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

!

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

I will provide you video tutorials for the round after it's done!

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

Your photo is so cute.

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

All the best for your first contest. Nice time to get better at CP in this quarantine. Thank you guys.

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

CF-Predictor, In the last 6 contests he was giving wrong results, I hope that the mistake has been fixed and gives correct results in tomorrow contest.

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

I am here after almost 11.5 months! 18 months if we ignore one-off contest I participated last year! Feels great to be back!

And I see that the number of participants has gone ~23-24k over past few contests. Used to be ~7-8k back in my days!

Great job guys!

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

Contest registrations are increasing at a higher rate than the COVID-19 cases.

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

I hope to become a specialist and stay that way .....

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

I cannot register for the contest.

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

I will be master tonight. Screen it

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

Dear Codeforces web developers, there is a typo in setting->social->city section which is "City where you live ot city you are representing"

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

    It is city where u are representing.

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

      I highlighted the typo! it should be or not ot

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

        ohh i mistaken it .I thought whether u are asking about the city.

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

Hope we can all score and make progress in this contest!

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

Finally, a contest after so long...

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

.

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

I think the round isn't simple(for a newbie) My English isn't very good，please forgive me.

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

    Why make such a pointless comment in the first place if you're so worried about your english.

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

Why hasn't the score distribution been published yet?

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

I am enjoying by reading comments.

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

I did some virtual contests of division 2 ,i would try to give my 100%. No matter whether my rating increases or decreases .wish me luck and beft of luck to everyone.

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

Hope this raund will help to me be 1600+, good luck all

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

22k participants ? can a rank under 3k will make me XXXprt

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

on each contests .. people ask "is it rated" for atleast 5 times.. probably gonna change my username to "alwaysRatedPleaseReadFirst".

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

thats moment when div1 participants not able to solve div2 D or even C

thats mean it will be fair contest for div2 participants!

thanks!!

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

nice round. I solve F and fail at C.

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

    Seriously man. After seeing div 2C, I was like I am no more div 1 :D

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

      I used Segment Tree to solve C:) It's more like a Div2D, if you ask me.

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

        Can you explain your idea on how to solve using segment trees.?

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

          Basically I try to count the number of bad segments. Lets fix the right border $$$r$$$. Now the segment is bad if it has some zero sum subsegment. For each $$$r$$$ lets find the biggest $$$l$$$, such that sum of $$$[l, r]$$$ is zero. Now if our right border is more (or eq) than $$$r$$$ and left border is less (or eq) than $$$l$$$ it's a bad segment. Now we are doing scanline and whenever we see $$$[l, r]$$$, we update some prefix with ones. You can do this even without sgtree, but I didn't think of it on the contest.

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

            My approach is somewhat similar, but I don't know why I'm getting TLE my code

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

              Try using map instead of unordered_map

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

                Thanks! It worked, but why unordered_map was giving TLE?

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

                  Welcome to the club buddy. C++ unordered_map uses a fixed modulo, so it can be blown up to $$$O(n^2)$$$. You can look at this blog, to know more.

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

                  Thanks for enlightening me :D

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

Interesting problems, but I think they are too hard for Div2

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

In Problem C I dont know what the Pretest 8 was but I wasnt able to pass it till end of contest

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

Why the hell would you make 4 heavy implementation problems in a row. We are so fucking tired of debugging and shit lord.

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

    What are you talking about? These problems required a few good observations and had simple implementation. I mean first three problems needed less than 40 lines of code.

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

    Hilarious

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

I Got Internet disconnection due to my provider problems and i got connected about 30 mins ago

Is there any solution for me ?

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

In Div-2B, I was first solving the wrong question and stuck thinking that we can a[i] to a[j] and a[j] to a[i], instead of only able to add a[i] to a[j] for i<j. Can someone tell me how to solve the above version of the problem ?

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

Video editorials for C and F out!

C

F

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

    I think it's great to have short explanations in video just after the end of the contest. If only I could press like multiple times!

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

    Still didn't get C. During the contest I figured out how to find out bad subarrays using prefix sums. But then I need to remove all superarrays of this bad subarray as well. I was counting it twice in some cases. How are you handling this? I didn't get that.

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

      Basically, I keep the rightmost starting position of such a subarray.

      This helps me to count only the subarrays starting at positions which are bigger than that position.

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

      for each index i, find how many subarray ending on that index have sum non zero, for that, we find the highest index j < i starting from which, sum is 0, then we know ans += (i — j);

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

How to solve C?

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

    Right above you :))

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

    I solved using map and prefix sum .We can calculate number of bad segments .Suppose while doing prefix sum we calculated value 'a' till position 'i' and suppose last such value 'a' has been found at position 'j' , then sum of numbers from 'j'+1 till 'i' is zero and number of bad segments it contributes is equal to (j+1-las)*(n-i+1) (provided (j+1-las) is positive) where 'las' is left position of previous such segment whose sum is zero. We include 'las' to avoid adding contribution multiple times.

    submission

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

      How comes that it contributes $$$(j+1-las)*(n-i+1)$$$

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

        suppose array has length 20 . Let first segment whose sum is zero is [3,6] then number of bad segment is contributes = 3*15 . Now let next segment whose sum is zero is [8,12] then number of bad segment it contributes is 8*9. But [2,13] is calculated for both segments . Hence we use las = 3 for second segment.

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

      Hey. I was trying on similar grounds during the contest and I am still trying to figure out my mistake. Can you please help me out?

      Here is my submission: 75899238

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

        I think it would be more convenient if you count the number of good subarrays. Just store last index position of the prefix running sum and the answer is equal to the i-map[prefix_sum], update map and last position at each index.

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

          It would be very helpful if I could get any feedback on my code.

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

      Your explanation is very clear, thanks!! I was just facing the problem of adding contribution multiples times.

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

Cheers, another crowded contest end. Look at the number of participants.

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

    The contest ran smooth tho (for me, atleast). Normally, I'd face lag while submitting and loading problems but today it was different. Submissions didn't last in queue for more than 2 secs. Really nice problems too.

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

Was the n=3 case for E possible or not? I thought it wasn't (couldn't find a good proof but spent a while trying to construct cases to no avail, but I got WA and I was pretty confident about my construction for n > 4.

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

    It's possible

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

    Same problem, for n>4 you can just copy his solution and add stuff the border, but not sure for n = 3.

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

    1 2 4 5 3 8 9 7 6

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

    Seems to work for n = 3

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

    Hey man , How your contest rating went up ?

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

      ??? This has nothing to do with the contest lol you can just message me about that

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

what is pretest 5 in C

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

    I suppose this is the test like:

    5 -1 0 0 0 1

    or

    5 0 1 2 -2 -1

    or

    6 1 2 4 -5 -1 -1

    After I fixed this I got all pretests passed.

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

    the same as me
    my solution was failed at pretest 5 too!!!!

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

    I am not sure, but try this:

    4
3 0 1 0

    Expected answer should be 2

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

For me the text of problems was hard to understand. Especialy 1333A - Маленький Артем was demotivating, since the expectation to solve a more or less nice first prob was not met.

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

In D i was getting TLE just because i was using endl instead of "\n".

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

What is pretest 7 in D?

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

    I think it is something like 6 6 RLRLRL After accounting for this TC, i got AC. Previously, my solution too was failing on TC7

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

      My code gives the correct answer for this test case. So, it must be something else.

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

      I don't think so. My code is also giving WA on Test Case 7 but it is giving the correct answer on the Test Case that you mentioned. T-T

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

      I dont think so, i know what i missed and i got wrong answer in testcase 7, but i'm pretty sure that its not the case, i say something like 6 7 RRLRLL.

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

WTF, how to solve B and C?

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

    For C, check my video editorial, the comment is on the blog!

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

    For B, I think:

    If $$$B[0] != A[0]$$$, solution is not possible.

    Else, for every position starting from 1, if $$$A[i] > B[i]$$$, you need to check if a -1 exists in A [1...i-1], if $$$A[i] < B[i]$$$, you need to check if 1 exists in A[1...i-1].

    Something like this maybe:

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

      Can you tell me how did you post your code such that we can collapse it? I always wanted to know lol

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

My first two submissions in the contest: WA Time I finally solved A: 16 minutes into the contest Codeforces DELTA: +125

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

This round was so cool! Thank you all who preapred this wonderful competition!

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

when will the editorials be out??

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

The verdict I got for problem E seemed wrong to me, am I missing something?

Input : 4

Output:

1 2 3 4

13 15 16 5

14 12 11 6

10 9 8 7

Verdict: wrong answer rook teleports: 0, queen teleports: 0

Doesn't queen teleports 1 time?

Link to submission: http://codeforces.me/contest/1333/submission/75904855

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

    No it wont teleport at all, u could use the output examples in the statement instead of finding the answer for $$$n = 4$$$.

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

    No. The queens route is:

    1 2 3 4 5 6 7 8 9 10 12 11 14 13 15 16

    If I'm not wrong.

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

      oh i see now, i thought we cant go through visited cells. Thanks.

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

Can anyone explain how to solve C ?

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

    Its a simple prefix sum problem.

    For each index i, calculate the next index next[i] such that the interval [i..j] has a sum of 0 (this can easily be done with a map and prefix sums). If no such index exists, let next[i] = N+1.

    Then, the answer is just the sum from 1 to N of (next[i]-i), since these are the number of arrays that don't have a subarray whose sum is zero.

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

      Thanks for the explanation it really does make sense now. However, I am still failing test case 5, I have no idea why, do you mind taking a look at my submission (anything I am doing wrong)

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

    My solution: maintain on the prefix $$$ [0, p] $$$ such maximum $$$ i $$$ that there exists $$$ j $$$ such that $$$ [i, j] $$$ is a bad subarray.

    Then let's count the number of good arrays that end in $$$ p $$$. For that we notice that any array $$$ [l, p] $$$ with $$$ l \leq i $$$ is bad, and any with $$$ l > i $$$ is good.

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

    When I see such questions like counting subarrays I usually think in two ways:

    1. Iterate over lengths of subarrays i.e. count valid subarrays of length = 1,2,3,..,n and so on. OR

    2. Count number of valid subarrays starting from index i = 1,2,3,4 (assuming 1-based indexing).

    In this case, I used the 2nd way.

    For each index i, count how many good subarrays exist.

    How?

    1. Find ending indexes of 0 — sum subarrays starting from each index i. If there exist multiple such subarrays, take the subarray with minimum ending index. (Why?). If there is no such subarray starting from i and having sum = 0, then store (n+1) for that index.

    Let this be stored in subarray_becomes_zero_at[].

    subarray_becomes_zero_at[i] = j implies subarray from [i+1,....,j] is a 0-sum subarray. This basically happens when prefix_sum[i] = prefix_sum[j].

    1. For iterate from right, and store what is the minimum j >= i and k >= i such that subarray_becomes_zero_at[k] = j. Let this j be stored as can_go_till[i] = j. This means, from every starting index i you can go till jth index without having any 0 sum subarrays in it.

    2. ans = sum( can_go_till[i] — i ) for every 1 <= i <= N.

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

looks like Div 1.5

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

God I literally misread B and for the entire contest I thought there was no restriction $$$ l < r $$$.

It was a horrible feeling of absolute stupidity when you see over 9k people having solved it and having absolutely no idea of even approaching it.

Luckily I could notice it in the end and implemented it in the remaining 5 minutes but god was it stressful.

Also it is actually now interesting how to solve that (apparently MUCH harder) problem.

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

    same :-(

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

    Lol same here. I made the same comment above. I was stuck in B for a long time, then moved to C and was able to solve in 15 minutes and again came to B and thankfully saw it.

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

    same :P

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

    How could we solve the harder version B? If i<j constraint wont be there?

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

      I actually thought that this was B and was not able to solve it till the end when I noticed the constraint $$$i < j$$$

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

      I believe the question becomes slightly easier if the constraint i < j is omitted.

      If A does not contain -1, but B contains a number lesser than its counterpart in A, solution is impossible. Likewise, if A does not contain 1, and B contains a number greater than its counterpart in A, solution is impossible. 0 in A would not play any significant role.

      I think a harder version of this problem would be if we were only allowed to use a pair of indices (i, j) only once to construct B or maybe if A consisted of other elements instead of just (-1,0,1).

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

        It is not possible in those cases. But they are not the only cases where it is impossible. It gets very tricky to choose the order and which element to use first.

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

the hardest c I’ve ever met.

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

    Yup, A and C were extremely hard for their problem class.

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

      A was pretty simple. Just print white in the top left cell and black for all the rest.

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

        i am crying now!!!

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

        Yup, I figured it out too in 7 minutes. But still, I think A was extremely hard for a D2A.

        Doesn't make it a bad problem though, just should've been a B and C should've been a D.

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

yeh, 30 mins for solve A, unsolved C and -100 rating! Good job

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

Needed swap(E, F)

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

    swap(F,D) would be better

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

      Actually I think swap(C,D) and swap(E,F) would be ideal. D is more straightforward than C IMO.

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

        swap(A,B), since A has some pitfalls if you do not see one of the simplest solutions in the first place.

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

    I think F is even easier than C,it took me half an hour to solve C and got WA one time,an hour to solve D and got 3WAs and 1TLE,but only 7 minutes for F and passed it.

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

The problem C bothered me too much, This is not an enjoyable contest.

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

listOfAuthorsWhoSetBadContests.push_back("ReD_AwHiLe")

Why such a hard C?

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

You know it's a fair contest when div 1 Candidates have to go through div2 Problem C and D's editorial !

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

    I dont have any idea how people could solve problem D, the solution for E was expectable, sadly i got stuck in case $$$n = 3$$$ for an hour i guess, after all it wasn't a bad contest if it had a little less ad-hoc problems, in fact i say solving problems in this contest needed luck more than coding power and knowledge.

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

      It was a little modified bubble sort, you have to sort the array. Record all the swaps you can do in one pass, then make those changes, then do the same again. After we have all the operations required. Just distribute them into k groups.

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

        I tried this algorithm, but am getting Wa at test case 7 -> submission

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

          Here is my submission Let me explain a bit more

          We just have to sort the array. We traverse the array and store the places we can do an operation. Now after we have recorded the possible operations in one pass. Now make those swaps. This way do it n times. Store all the swaps required to sort the array in n arrays. So we store in a vector<vector> operations all the operations we can do in the ith pass.

          At the end, you will have all the swaps that are needed. Thus we also have the operations.size(), which denotes the number of passes required to sort. Let's call this min_operations.

          Total count of all operations is max_operations needed to sort.

          Now min_operations <= k <= max_operations

          Let's take an example k = 6 string = RRRLLL

          1st Pass: 3
2nd Pass: 2 4
3rd Pass: 1 3 5
4th pass: 2 4
5th pass: 1 3

          so min_operations = 5 (if we swap all possibilities at once) max_operations = 9 (if we swap one by one)

          now if k = 6, we divide them into 6 groups instead of 5 I just used greedy for that, I filled them by one by one and k-=1 Until k was equal to the number of groups(indexes left) So we got our final answer.

          Group 1:  3 
Group 2:  2 
Group 3:  4 
Gruop 4:  1 3 5 
Group 5:  2 4 
Group 6:  3

          Here is my submission for reference. https://codeforces.me/contest/1333/submission/75908994 Can you stop downvoting me now guys. T_T

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

            My approach was exactly similar, but couldn't pass TC 7. I guess there was some mistake in the implementation. Thanks a lot, bruh.

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

          @sonu628 The mistake you have made is you have made the changes while storing the swaps. So in a case like RRRLLL You first swap RR LR LL Then you can again swap here, which is wrong.

          So we will first record the indexes we can store in an array. And when the inner loop is over, then we make those changes. So you should do something like this

          Code

          Also note that inner loop goes till n-1 now everytime.

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

I had an off-by-1 error on D, which I noticed a couple of seconds after the contest ended. I haven't felt such frustration in a long time.

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

    Can you discuss your approach to D?

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

      You can notice that the head turn has the effect of turning a RL into a LR i.e. moving one L one position to the left. It's easy to see now how many moves you have to make (i.e. the number of times you have to move an L to the left, until all L are to the left). Let's call this number needed.

      The maximum amount of seconds you can have is if you do only 1 move per second, so that is needed seconds. Therefore, if needed is less than K, we have no solution. Then, during each of the K seconds, while needed is still bigger than K, greedily do as many moves as possible. Each move decreases needed by 1. At some point, needed will either become equal to K, meaning you will successfully finish with 1 move per second, OR it will stay bigger until the end, which means there is no solution.

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

        It's no were written that if "needed" is less than K, we have no solution.

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

          It says you have to do the process in exactly K seconds. If you only do 1 move per second, you will have needed seconds, and that is the maximum amount of seconds you can have. Therefore, if that maximum number of seconds is less than K, you cannot do it in exactly K seconds.

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

          It's written number of moves need to be exactly "K"

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

not even a single question...i dont know how long will it gonna take to score 1 !

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

Great first round, PuRpLe_FoReVeR, pretty problems :)

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

    Hey, I see you've submitted for Problem E. Would you mind sharing your idea? I came up with something in the last 30 mins but couldn't implement it correctly :(

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

      Find a solution for $$$n = 3$$$ (brute force seems good). For $$$n > 3$$$ we can add $$$n^2-9$$$ to each number (in 3x3 solution). In the remaining cells we put the numbers from $$$1$$$ to $$$n^2 - 9$$$ so that the paths of the Rook and the Queen are identical

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

        I can't see the idea behind how you came up with this but I can see why this may work, wow... and thanks. If you wouldn't mind, can you also explain how you came up with the idea (sorry for bothering if that's what I'm doing)?

        (smh I watch William Fiset and then try to model everything into graphs to do dfs/etc on :p making it harder to implement firstly, and then forgetting the idea behind what I'm even trying)

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

          Obviously, there is no solution for $$$n \leq 2$$$. For $$$n = 3$$$ situation is unclear, so anyway I should solve it somehow. To transform the problem into a simpler one is a typical idea in constructive problems, so it is easy for $$$n > 3$$$

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

How to solve D?

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

    Think of it as a modified bubble sort. We just have to sort the array. We traverse the array and store the places we can do an operation. Now make those swaps. Store all the swaps required to sort the array.

    If number of operations is greater than k no answer.

    Now divide these operations into k groups.

    Here is my solution https://codeforces.me/contest/1333/submission/75908994

    Just hoping it passes system tests lol

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

And the cheaters of today are:

julianferres and Monazo1997 !!!

Solution D of julianferres: https://codeforces.me/contest/1333/submission/75910458

Solution D of Monazo1997: https://codeforces.me/contest/1333/submission/75908368

And if you think admins are actually going to do something you can read this.

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

In CF haven't gotten TLE cuz cout before, until this D, and difficult gaps also seem strange.

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

    Same thing happened to me. Since the number of integers we output is not explicitly mentioned in question, I forgot about fast output.

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

amazing solve F (AC):

    int n;
    cin >> n;
    vector<int> ans;
    for (int i = 2; i <= n; i++) {
        bool good = false;
        for (int d = 2; d * d <= i; d++) {
            if (i % d == 0) {
                ans.push_back(i / d);
                good = true;
                break;
            }
        }
        if (!good) ans.push_back(1);
    }
    sort(all(ans));
    for (auto x : ans) {
        cout << x << ' ';
    }
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    daamn son...

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

    Can you explain why, please?

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

      i don't know))) just noticed))

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

      First of all, we can consider that there is a set of numbers and when moving from k to k+1 we just add a number to that set. Second observation is that if X is a divisor of Y then we will never add Y to the set before X. That means that when we add a number to the set, all of it's divisors are already in there and so the new largest possible GCD is this number's highest divisor. We can't get a GCD larger than this one with this number and some other number because this GCD would also need to be a divisor of this number. So, we can always add the number with the lowest highest divisor.

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

        Why do we select the largest divisor, instead of say the lowest (or any other) divisor?

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

          Because if $$$d$$$ is a divisor of $$$x$$$, then $$$gcd(x, d) = d$$$, so largest gcd = largest divisor

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

    Let's take a number $$$i$$$ and it's greatest factor $$$j$$$ it makes sense to add $$$j$$$ to the list before adding $$$i$$$. Now since $$$j$$$ has been added before $$$i$$$ the max gcd on adding $$$i$$$ will be $$$j$$$ only. So just calculate the greatest factors for all the numbers and sort this list and print.

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

    Another solution for F:

    we create the answer in reverse order(starting from n to 2). Initially, the set is {1,2,...n}. At any step, the imperfection of set is that number which has at least one multiple in the set. Now we know at each step the numbers for which at least one multiple is present in our set. So we greedily remove any multiple of the largest such number. code

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

I see some magicians over there. How DreamLolita did solve the first three problems in minutes 5, 6, and 7?

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

    it can be because of being late to contest, after contest begins for 5 minutes you cant register, then after 5 minutes he have solved these three problems and he just copy-pasted, i say he was too slow =P.

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

      Please tell me if you think i am wrong, it happened for me couple of times but i usually go for a harder problem when i'm late.

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

    I am wondering too. The codestyles of his A&B&C are totally different.

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

      The sad part is, if people worked together for algo and code is just written by one guy. We would never figure it out.

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

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

    That is the magic of teamwork LOL...

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

The difficulty gap is a bit big between B and C....in my opinion

Contests with reasonable difficulty gaps are more enjoyable.

Pretests are (somewhat) strong, that's good.

We hope to see your contests becoming better!

(Now hacking point plays its role

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

Hey folks,

Today I tried to hack a solution with a generator and got the "Invalid Input" verdict:

Validator 'validator.exe' returns exit code 3 [FAIL Expected EOLN (stdin, line 1)]

https://codeforces.me/contest/1333/hacks/628946/test

I still don't understand what exactly was wrong with my test, as I used writeln! operations everywhere to ensure the EOLN placement. Could it be a glitch in CF system, especially since I used Rust language which is not (yet) very popular for competitive programming?

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

    As expected, the solution I tried to hack didn't pass the systests. I want to make sure the above issue is resolved, so that I won't hesitate doing hacks with Rust in the future.

    cc: MikeMirzayanov, antontrygubO_o, PuRpLe_FoReVeR, can you please take a look?

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

    I know the exact reason why this happens (used to have the same problem in PyPy2). A less cryptic error message would be "Missing carriage return (stdin, line 1)". Normally submitting on CF, all whitespace characters are equivalent, eg. it doesn't matter if you print a space or a newline, but this is not the case for hacks. Also CF uses windows, so it requires the EOLN '\r\n' to be used to end lines in hacks. In C++ printing '\n' will on Windows automatically output '\r\n'. However in Rust writeln

    "Write formatted data into a buffer, with a newline appended.
On all platforms, the newline is the LINE FEED character (\n/U+000A) alone"

    meaning it does not print the '\r'. Here is a stack overflow discussion about how to make println output '\r\n', guessing there is a similar fix for writeln.

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

      Thank you, pajenegod! I don't know how to test it now, but it seems like a very plausible explanation. I appreciate you taking the time to dive into the docs, cheers!

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

In this April I see every round like making April Fool to me.

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

i think F problem was easier than C.

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

    Can you explain your solution

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

      i wasn't able to solve during contest but u can refer HannaYzade solution thats pretty cool my logic was little bit complex.i was thinking about prime number and all.

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

I can't believe that this soultion will get TLE for problem C of case 86。 https://codeforces.me/contest/1333/submission/75862488

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

    Everyone using unordered_map are getting TLE, not sure why..

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

      Worst case complexity of unordered_map is linear because it's hashmap.

      Use a custom_hash with that.

      Refer to this link

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

      Try using ordered map. Amazingly it passed the test cases.

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

    Probably it's anti-hashmap test.

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

      Everyone can downvote me, but I think it's not honest, when your algorithm is right but it hasn't passed by same way. "Thanks" to author, do it more.

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

    isn't the complexity of count method linear?

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

      But it may take up to $$$O(n)$$$ time to access element in unordered_map in an anti-hash test.

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

    Yes. Unfortunately got the same verdict.

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

https://codeforces.me/contest/1333/submission/75908627 My solution for C problem stuck at test case 9, can somebody help me in debugging(* please ignore the template)

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

    Same way brother my one also stuck on test case 9

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

      I don't know what happen to me...I started doing all contests on CF again from 1st April..even not a single time I am able to solve problem C in div2, which was not that too difficult 3 months before.. I guess there are 2 possibilities for this 1) I have to practice hard again to come on the track 2) they are making hard problem sets for contest

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

        This month less experienced setters are coming in front who are giving problems of very odd taste and of high on implementation part..

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

Nice contest. Special thanks for making strong pretests.

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

    I don't agree with second sentence. Pretests were very week on B and that is fine, but it's not fine that system tests are also very week. I've just hacked a bunch of people ( link ) with few TLE "edge cases" and still a lot of people could be hacked (just sort AC submissions decreasing by time and you will find a lot of O(N^2) solutions). I hope that the authors will make stronger tests next time.

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

MikeMirzayanov because of connection problems, my same code for D got submitted twice. Once through the problems page and the other through the submit page, and I got a 50 points penalty for resubmission. Shouldn't the system have checked my previous submission and not allow me to resubmit the same solution code again? I believe this might be a bug in the system. Please check.

Here are the 2 submissions: 75895126 and 75895561. They also don't have any difference even on comparing them using the compare button.

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

    Hi. Probably, you used a micro-website, it could be a reason. I have plans to implement it in the correct way there soon. We do some work on micro-websites. For example, today m1 worked via https + announcements have been implemented. Since you took part as an unofficial participant, I don't think I really need manually change submission verdicts.

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

      Thanks for replying.

      I don't need a manual change in my verdict but I brought this up since I think this might affect other people as well someday. I didn't actually use a micro website for this. My first submission was through the problem page by uploading a file. Since it was taking too much time to get submitted, so I opened the submit page and copied the code from my editor and submitted it, and it turned out that the earlier one had been submitted as well.

      Hopefully, codeforces team will work to improve this, so that it does not happen frequently.

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

I only got AC on the problem D after i wrote fast output. Before that, i always got TL10

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

Yet another screencast. The channel have focus in brazilian community so many videos will be in portuguese, but from time to time I maybe do something in english, or with no audio like this screencast

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

Why on earth did you guys make an anti-unordered_map TC(86)... Think its quite unsuitable for a contest like this which only has limited pretests. What this kind of situation means is that we can't use hash_based STL in contests w/o dirty tricks avoiding anti-hash testcases, which is not quite a necessary skill for Div.2 Contests like this one.

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

    I hacked a person with that test case and all successful hacks are usually put into system tests. So blame me if you want, not the authors.

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

      Wow, that's unexpectful... Respect on your hacks.

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

        If you have not read the blog post by neal on how to protect against unordered map hacks, I’d highly recommend. You can find it with a quick google search.

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

    There is no such test in original testset. I think such things are not what we want to learn from CP. But this trick exists and we must know it.

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

At the time of the contest i had 2 problems solved. Now I see that broblem B became unsolved. How?

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

    failed on system checking.

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

    There are pretests and system tests. While contest only the pretests are executed.

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

      what is the difference and what for system tests exist?

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

        While contest the queue of problems should be resolved fast, so participants get quick response after submitting.

        On the other hand, CF wants to do a lot of tests to be sure that everyting is tested fine.

        So, as a compromise, only a part of the tests are executed while contest. That are the pretests. The disadvantage of this is, that sometimes happens what happened to you. You think you submitted a correct solution, but it was errnous.

        On some platforms you get "full feedback", which means all tests are executed while contest.

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

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

I also learned it the hard way.

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

    Is there a collision linked to the numbers on the pill ? I have never experienced this before (but I haven't used unordered_map a lot either).

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

      Uhh... that's just the meme template. Nothing special about that. But you can refer to other comments in this blog as to why you shouldn't use unordered_map in a codeforces contest.

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

So this strange thing happened
I got the solution right down to the most basic detail of it
But apparently I got a TLE because I used an unordered_map and not a map
Can someone please explain this unanticipated issue
And then how to judge where to use map and where to use unordered_map
https://codeforces.me/contest/1333/submission/75869383
My solution for reference

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

    Check this out!

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

    see here

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

    Well unordered_map uses hashing to provide quick access to memory, but hashes aren't stable and there might be collisions in some points (especially when anti-hash testing) and that makes unordered_map to 'rebuild' itself and do a rehashing (depends on implementation). So if there is a lot of data to store it is more profitably to use normal map, or!!! use custom hash function for unordered_map watch here

    It is the usual problem with unordered_maps/gp_hashtable, but not the only one

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

Constructive A is a really good tradition :)

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

post the tutorial fast :(

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

great round with interesting problems! Hope I can become orange this time.

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

A simple solution for F: Just take maximum divisor that not equal to a number for every number in range 1..n. Then sort It and that will be the answer. You can check my submission. https://codeforces.me/contest/1333/submission/75915783

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

pls help me i dont know how to prove that by mistaken i have used ideone and someone copied my code what are next steps to get my rating back.

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

Thanks a lot PuRpLe_FoReVeR for preparing this round.. Finally became a Candidate Master....

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

https://codeforces.me/profile/AnsuFati Correct me if i'm wrong,but isn't Div2<=1900?

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

My submission on D took time limit exceeded because i used endl instead of \n. I know it is my fault but can you do anything about it? This is taking AC and this is taking TLE

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

Can team codeforces upload explanation videos for harder problems like-div2 D,E,F..It would be helpfull for budding programmer like me.. MikeMirzayanov

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

    There's tmwilliamlin168's channel on youtube with explanations of some rounds

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

lost the net connection and ... -161 points in rank rating . :?

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

problem C, TL86, fix: unordered_map->map

problem D, TL10, fix: I deleted ans vector and printed answer straight to stdout

My expert rank:

grob

Actually, good problems, but these things just killed me

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

I got WA test 76 in D any idea please my submission

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

    I think you forgot to check if k is below the lower bound of the possible answers

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

C was a tricky problem. One that makes you think it's easy, but has a bunch of traps. After reading some good solutions, here's some details on how to go about solving it:

Observations / Solution

1) Prefix sums are essential here. As you traverse the array, if you see a prefix sum you've seen before, that means the elements after the last index for that prefix sum to the current index of the same prefix sum add up to 0. For eg., if array is [3 -1 2 -1], the prefix sums would be [3 2 4 3]. Observe how 3 is seen twice since subarray [-1 2 -1] adds up to 0. So positions 2 through 4 constitute a net sum of 0.

2) You could calculate all the bad subarrays and remove them from the overall count of subarrays. But that seems to have many complications with overlaps and is not recommended (at least that's how I started solving this problem, and couldn't figure out how to do it).

3) The right way is to calculate all the good subarrays, piece by piece by systematically excluding the bad subarrays. Normally we compute all possible contiguous subarrays using the formula n*(n+1)/2. However, rather than rely on a one-size-fit-all formula, we should rely on first principles. A cleaner way is to just add up piece by piece as you move along. So for eg. [3 5 9] has 6 subarrays ([3], [5], [9], [3 5], [5 9], [3 5 9]), which can be computed as shown below :

Subarrays([3 5 9]) = (subarrays([3]) that include the first element "3") + (subarrays([3 5]) that include the second element [5]) + (subarrays([3 5 9]) that include the third element "9")

The length of each is simply the length of the subarray up to that point. So for subarrays([3 5 9]) that includes "9", it is 3 ([9], [5 9], [3 5 9]), similarly for "5" that could would be 2 ([5], [3 5]) and for the first element "3", it would be 1 (just [3]).

So Subarrays([3 5 9]) = 1 + 2 + 3 = 6

Basically this is analogous to having a string "abcd" and finding all the substrings (total of 10) : 

a: "a" (count: 1)
b: "b", "ab" (count: 2)
c: "c", "bc", "abc" (count: 3)
d: "d", "cd", "bcd", "abcd" (count: 4)

(If someone has an easier or more intuitive way to calculate/understand the above, please do share)

4) Once you encounter a bad subarray, then don't count it or anything to it's left. This is needed to avoid over-counting and to meet the problem statement requirement. Maintain a last bad position and keep updating it every time you encounter another "bad subarray". Bad_position is defined as beginning_Last_subarray + 1. This is because if you have a subarray like [1 -2 1 3] and you get to the last element "3", then you should still be able to use all but the first element (i.e. [-2 1 3]) towards the count. Simply removing the first element is sufficient.

5) A special case here is when the sum of the first i elements is 0. To solve this, keep prefix[0] as 0. That is, build prefix sum index from 1...n (instead of from 0 to n-1) so the first time you see a sum of 0, it has been seen before.

The rest should hopefully fall in place when you see the source code for any of the top contestants. I've added comments to my submission as well. Feel free to ask questions.

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

    This is so well explained. Thank you for your observations.

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

    Hey!!. Can you please help me understand why this simple sliding window approached failed. I got WA on test case 5. Here's the link to my submission => 75925799

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

      It seems that you're not handling 0's properly. So if you have [7 0 0 0 0 0], it will account for [7], then [7 0], then [7 0 0], etc. However, you're only supposed to count the first one [7] as anything with a 0 is invalid (as any subarray with 0 is invalid per the problem statement).

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

    Someone upvote this guy .

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

    Can you tell me why my solution doesn't work? I used the n*(n-1)/2 approach(and counted the singles seperately). https://codeforces.me/contest/1333/submission/75916699

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

    This is even better than editorial!

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

    Why bad position is defined as beginning_Last_subarray + 1 ? Could u please explain it a bit more ?

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

      Let's take a string as an example as it is the exact situation and is a little easier to explain with. If the overall string is abcdef and one of the bad strings is abc, then you don't want to just drop abc altogether and count the substrings in the remaining portion (i.e. def). Instead, you need to start from bcdef to count all the valid substrings — you only needed to get rid of the first a and the rest became valid.

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

Thanks for problem E! At start I thought that there is no solutuon for 3*3 so I built it for 3*4 and then added another numbers around this rectangle. Send it and got wa4, so I made solution for 3*3 and its accpted :)

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

Is there a place where someone can help me debug my code?

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

Problem D:

when using cout << endl, I get TLE on test 10. When using print("\n") I get WA on test 7.

Any explanation? 75936645 75936680

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

Sad story. I almost solved problem C, however, i used unordered_map<long long, int> in the competition and the hashmap solution failed in the system test with TLE verdict. I changed the hashmap into map<long long, int> and the balanced tree solution was accepted.

Should we avoid unordered_map when the key is long long?

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

    you should avoid unordered_map whenever you can.

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

      Can you explain why? I faced a similar problem and map worked much faster than unordered_map for adding and fetching elements.

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

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

Why this solution didn't get TLE if he used unordered map???

https://codeforces.me/contest/1333/submission/75932108 ecnerwala PuRpLe_FoReVeR

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

    I dont know, maybe because of int64_t instead long long

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

    I wonder if that's because I submitted with 64-bit GCC. You could try experimenting with that a little. I don't actually know any good reason, I guess I got lucky. I think in general, unordered_map is fine, unless you're worried about people hacking you with specialized tests. It's definitely slower than an array, though.

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

      Thanks for your response. :D

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

        I have AC with 64-bit GCC when submitted code that got TL before

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

      In general, is better use int64_t? or Why did you do?

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

        I do it because it's slightly more modern/idiomatic C++. I don't think there's any difference in practice.

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

    I used map => AC. But in time duration, I used unordered_map => TLE :<

    I copied code 75932108 and use GNU C++17 => TLE

    And I tried using GNU C++17(64) for 75932108 and my code before (map and unordered_map) => AC. In this case, I see unordered_map run slower than map. I think int64_t isn't related.

    Sorry for poor English :<

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

      Woww, That's right, was the compiler what make works the code. Surely in that version the hash is implemented of other way, I'll have to review it, thank you so much.

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

        I tried other alg (rather similar to alg I used before) to solve C problem.

        Result: map got AC (GNU C++17 and GNU C++17(64)) and unordered_map got TLE (GNU C++17 and GNU C++17(64)).

        So, I think unordered_map can not be stable like map.

        Just my experience, use map instead of unordered_map. (Not sure in any case :<)

        Check my submissions for details.

        Sorry for poor English :<

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

Hey....something strange happened with me during contest i solved problem A and B but now when i checked result it showing only problem A has been solved and Showing TLE for prob 2.......but during contest it was solved and i scored a total points of 1165(450+615) but now 450 only

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

    Read contests rules. Your solution got TLE on system tests

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

    Hey men,this is a rule int div2,we'll have a system test after the contest.

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

Thanks for the contest! Problems E and F are really good, in my opinion!

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

Is C only 1250 Score? I think it would be the harder than D.

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

When and where will I get the editorial for this contest?

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

I participated in this contest and got only B problem solved. But my rating instead fell. Can someone please explain how? I am new to Codeforces.

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

    See your rank, it's a comparitively high rank as compared to your performance corresponding to the pneultimate rating.

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

      How to see the rank? or better yet, where can I see how the rating works here on Codeforces? Thanks.

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

Is C++17 faster than C++11 ?
The same solution gave TLE for problem D when submitted in C++11 and was accepted in C++17.
C++11 Submission
C++17 Submission

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

Hey guys!

As promised, I will upsolve the problems in a livestream on YouTube. Hope to see as many as you there!

https://codeforces.me/blog/entry/75777

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

Please post the solutions

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

When editorial will be posted of this round??

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

construction forces

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

Real order: A B D C F E

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

how to solve C ? idea needed

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

    For each index (let's call the current index B), find the largest index (let's call it A) such that a[A] + a[A+1] + … + a[B] = 0. Let's call the array of those largest indices X. You can do that using prefix sums. Then, you just run a for() loop over the array and, for each index (let's call the current index I), the number of good subarrays which end at that index is I – max(X[0], X[1], …, X[I]) + 1. The solution is the sum of those numbers. My code

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

My solution to Problem C

This solution is a bit different than most of the solutions explained here.

Also this is the first time I'm explaining a solution, so please feel free to share any feedback. :)

I used divide and conquer based approach to solve the problem. The idea was to keep finding a subarray with sum equal to 0 until we find one such subarray. After finding a subarray with sum equal to zero, we'll split the array into two parts, calculate the number of valid subarray for each of the two parts and add them to our answer. Also, we need to subtract something from our answer to eliminate overlapping subarrays in both the parts.

Let's assume that, we are trying to find number of good subarray of array a from index l to r (inclusive). We'll maintain prefix sum and keep on storing prefix sum along with ending index in a map. Whenever we encounter a prefix sum value, which we've found once before this(we've already stored it in the map), we know that there's a subarray with sum equal to zero.

For example, we found out that sum of subarray [i, j] equal to zero. We need to find sum of number of good subarrays in [l, j — 1] and [i + 1, r]. Also we need to subtract the number of good subarrays in the range [i + 1, j — 1].

In other words, if the range of our array is [l, r] and we've found a subarray with sum equal to zero which is [i, j] :-

Number of good subarray in the array [l, r] = Number of good subarray in the range [l, j — 1] + Number of good subarray in the range [i + 1, r] — Number of good subarray in the range [i + 1, j — 1]

If there's no subarray of the array [l, r], whose sum is equal to zero, then calculating the number of good subarray is pretty easy. For example if the array is {1, 3, 1, 10, 5}, then the number of good subarray is 1 + 2 + 3 + 4 + 5 = 15.

long long divAndConq(vector <int> &a, int l, int r)
{
  if(l > r)
    return 0;
  map<long long, int> m;
  m[0] = l - 1;
  long long s = 0, ans = 0;
  for(int i = 0; i <= r; i++)
  {
    s += a[i];
    if(m.find(s) != m.end())
      return divAndConq(a, l, i - 1) + divAndConq(a, m[s] + 2, r) - divAndConq(a, m[s] + 2, i - 1);
    m[s] = i;
    ans += (i - l + i);
  }
  return ans;
}

My Solution

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

What is the difference between (Div. 2) and (Rated for Div. 2) ? Also this was my first contest and got rating of 1406 with rating change of -94, HOW ?

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

    1) There's no difference between (Div. 2) and (Rated for Div. 2). It basically means that if your rating is < 2100 and you participate in the contest, your rating will be updated.

    2) If you participate in a contest for the first time, your first rating will be 1500 + dt, where dt is your rating change. Think of it as the time you create account, you get base rating of 1500.

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

      Thanks a lot for the reply, searched for this everywhere and found nothing.

      Rating change was -94 this time so does that mean my performance was relatively bad for the rating of 1500 ?

      Also can you also please explain how will my rating change in the next contest i.e. Educational CodeForces Round 85(Rated for Div. 2) ?

      I really don't understand how rating change works.

      Thanks again for the reply :-D

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

I hope several hours won't turn into several days. Please post the tutorials.

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

Hello, I want to ask a question which makes me feel so strange:

my solution for problem C failed in system testing because of 'Time limit exceeded on test 86', 75866276. While as I check the test data and test it on my computer(CPU: 2.6 GHz 6 cores, Intel Core i7), it runs very fast. My code accepted finally as I try to change the 'unordered_map' into 'map' 75972767. Is 'unordered map' runs with such a big constant? I am so confused about this situation as I used to think that 'unordered map' will run faster than 'map'

I still don't understand why. Can somebody give me some explanation? Thx!

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

Is it me or anyone else found F easier than C D and E? My Submission

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

can someone have a look on my submission for Prob C ?

https://codeforces.me/contest/1333/submission/75984070

I'm getting WA on Test Case 9 , I'm unable to find any error in logic / implementation , and the test case is too large for me to enter it manually.

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

    Perhaps map<int, int> M is the issue :)

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

      so what modification can I make?

      i read that using unordered map instead of map can help prevent collisions, but isn't that only helpful if I was getting TLE , how can using map get me a WA if my implementation and logic was correct ?

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

        You use long long ints elsewhere, so I thought you'll get the hint quickly ;) Anyway, my suggestion was to make sure that your indexes for sums are also lls, since 2 * 10^5 * 10^9 overflows with ints. map<int, int> --> map<ll, int> and try again

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

          usually codeforces marks the line with red where int overflow takes place, And as trying with map<ll,ll> is also not working, what do you think is my implementation / logic incorrect ?(tho I'm getting correct result for small test cases which I can calculate manually)

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

      https://codeforces.me/contest/1333/submission/75992773

      I just tried using map<ll,ll> , still I'm getting WA

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

        Hmm, I don't know exactly what's the further problem, but I don't quite understand why this line is necessary:

        Lstart=Lend;

        Alternatively you can double-check all your 0-based/1-based indexes.

        Since your output is larger than that of the jury's, it means your ans is not counting all the non-good subarrays. As you may have already noticed, test 9 starts with -816845378 816845378 ... which makes all the following subarrays which include these first two elements also non-good.

        Good luck!

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

Still editorial is not posted???

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

When will you post the editorial?

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

Geothermal I wish you'd publish unofficial solutions :)

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

seems like there is a problem so that the tutorial is not coming up... https://codeforces.me/contest/1333/hacks

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

    Interesting, some $$$O(n^2)$$$ solutions for B passed system test

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

Someone know what "several hours" mean?

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

I really want editorial

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

Isn't it too late for the editorials to be posted??

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

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

sir please upload the tutorials

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

Downvoted!! because of 23 hours passed since the contest was started and still no editorial!!

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

Waiting for editorial be like

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

can anyone explain how to solve problem "C" ....

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

deadly waiting for editorials!!!!!

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

Can anyone help why i am getting wrong answer on testcase 7 -76004123

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

    "Indexes must point to children with R-mark" This means that you type the index to the boy who is looking to the left. Search bug around this.

    → Reply