Agnimandur's blog

By Agnimandur, 2 months ago, In English

Hello, Westeros!

I'm glad to invite you to Codeforces Round #736 (Div. 1) and Codeforces Round #736 (Div. 2), which will be held on Aug/01/2021 17:35 (Moscow time).

The round will be rated for both divisions. Each division will have 5-7 problems and 2 hours and 15 minutes to solve them. There will not be an interactive problem, so yay!!!

This round would not have been possible without the following individuals:

  1. Aleks5d, for awesome coordination of my round.
  2. Benq, for extensive testing and contributions throughout the round, especially for 1548E - Gregor and the Two Painters.
  3. 1-gon, for discussing problems and statements with me for hours on Discord.
  4. amgfrthsp, for translating statements into Russian.
  5. MikeMirzayanov, for Codeforces and Polygon.

32 testers

The round had a total of 32 testers. I tried to get a "rainbow" of testers to help guarantee a most balanced round. Thank to you to each and every one of them!

This is my first round ever written, and I sincerely hope you enjoy it, regardless of your rating!

Score Distribution

Div 1: 500 — 1000 — 1750 — (2000 — 1000) — 3500

Div 2: 500 — 750 — 1250 — 2000 — 2500 — (2000 — 1500)


UPD: Editorial


Winners

Congratulations to all our winners in the round!

Div1

  1. Miracle03, congratulations on the AK!
  2. tourist, congratulations on the AK!
  3. yhx-12243
  4. heno239
  5. Isonan

Special congratulations to antontrygubO_o and Subconscious for definitely reaching the rank of Legendary Grandmaster!

Div2

  1. dingdingsb
  2. pAFOstd
  3. black_trees
  4. lajixtc
  5. soumilaggarwal

Fastest Solves

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

»
2 months ago, # |
  Vote: I like it +83 Vote: I do not like it

Thanks for the early score distribution!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +351 Vote: I do not like it

    Yeah no problem!

    There's no reason to needlessly hide the score distribution.

»
2 months ago, # |
  Vote: I like it -13 Vote: I do not like it

2 hour 16 min

»
2 months ago, # |
  Vote: I like it +49 Vote: I do not like it

Newbie Testers Go Here

anyways I'm excited for this contest good luck to all those who are planning on participating

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    can newbies be testers?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      anyone can be a tester if he/she is a trustable friend of the author or the author himself asked someone for testing

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    I hope to be solved at least two problems...

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Codeforces, sorry for my comment, I will not write comments like this anymore. :(

»
2 months ago, # |
  Vote: I like it -132 Vote: I do not like it

Div 2 Speedforces incoming

Spoiler

»
2 months ago, # |
  Vote: I like it +268 Vote: I do not like it

As a tester, let me participate officially

Spoiler
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +76 Vote: I do not like it

    As a tester, zyzzsama stole my as a tester comment :(

    Anyways, I liked the problemset of this contest a lot, and I am sure you would also do the same ! Wish you enjoyable contest duration :)

»
2 months ago, # |
  Vote: I like it +87 Vote: I do not like it

Discrimination of testers on the basis of colour :(

»
2 months ago, # |
  Vote: I like it +47 Vote: I do not like it

As a tester, problems are great!

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Benq, for extensive testing and contributions throughout the round, especially for problem G.

1-gon, for discussing problems and statements with me for hours on Discord.

I tried to get a "rainbow" of testers to help guarantee a most balanced round.

check here for the hint-based editorial!

Stop it... don't give me this hope...

»
2 months ago, # |
  Vote: I like it +285 Vote: I do not like it

As a VIP tester I recommend everyone to gain rating!

»
2 months ago, # |
Rev. 2   Vote: I like it +62 Vote: I do not like it

As a tester, I think you will collectively get down on your knees and orz Agnimandur for his hard work and awesome problems after contest. I recommend you to read all of his problem statements and wish you good luck!

»
2 months ago, # |
Rev. 3   Vote: I like it +15 Vote: I do not like it

As a tester, this round is balanced for every participators in both divisions. I recommend you to read all the problem and try to solve as much as you can.

Good luck!

-QuangBuiYT

»
2 months ago, # |
  Vote: I like it +94 Vote: I do not like it

Thanks for a great set of problems. I recommend everyone to participate and gain rating! OMG My first "As a tester..." comment

»
2 months ago, # |
  Vote: I like it -15 Vote: I do not like it

I hope to become specialist after this round

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i want to do D nothing else matters, focus on action rather than outcome

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +68 Vote: I do not like it

    Biggest lesson I have learnt is to never target any certain color or rank in cp.I still don't forget the day I registered for codeforces. That is a memorable day of my life.A young kid ( I am still a kid ) had no other other thoughts in mind except writing some codes and how to get the AC verdict.As months went by,I slowly started to think about colors but recently I had come to some realisations :

    • My love for problem solving is greater than any random color

    • If I keep loving what I do I will eventually end up reaching my highest potential

    • Competitive Programming is something which has gifted me a beautiful life.I should keep loving it and not take it as a duty.I should take it as my passion and hobby

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Expectations: (see above) Reality: I solve contests to gain my rating (It's just a joke, don't be so serious <3)

»
2 months ago, # |
  Vote: I like it +99 Vote: I do not like it
lighthearted meme
»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Good to see that Problem A is of 500 again

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This may not be the best place to ask it but can we deduce the difficulty of problem from the scoring distribution? Like here in Div2, there is high gap between score for problem B and C.. does it mean the same for their difficulty gap too?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    There is no certainity about difficulty of a problem on the basis of a its score in the contest.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Scoring distribution is a hint to how hard the problem is, but it doesn't necessarily signify difficulty.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is Div2 for people <1900 or <2100 ? in these rounds.

»
2 months ago, # |
  Vote: I like it -41 Vote: I do not like it
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't know what's the benefit of ratings distribution. Problems will come and ratings will go.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good job

»
2 months ago, # |
  Vote: I like it -28 Vote: I do not like it

You should provide model solution in python too .

»
2 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

You got "rainbow" of testers, but not "rainboy". That might have led to unusual round ;)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +108 Vote: I do not like it

    That unusual round might have a scoring distribution like :

    (2500 - 2000 ) -2500 - 2000 - 1250 - 750 - 500

»
2 months ago, # |
  Vote: I like it +63 Vote: I do not like it

Now I wonder what will happen when the contest starts...

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    depending on your rating you are a rated contestant for one contest and unofficial contestant for other. But as long as you don't submit code on a single problem. It is taken as you not participating in the contest

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +69 Vote: I do not like it

      If so he can submit in div2 till pretest passed to avoid penalties in div1.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Well, I have seen a participant in situation like this, and he said 404 Error was displayed when contest started :D

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It seems that all registered participants whose rating is higher than 1899 have been deleted from div.2, so I can't find out what will happen(

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thx for nice score distribution;)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Tester squad from Errichto's Discord!!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope the problems with the scoring distribution 2000 will be like in previous round(not educational)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    ahahah that problem D in round 735?) yeah, it was to ooverrated, should be like 1000

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope the Difficulty level will not be like last Codeforces Round #735

PS: Puplis Like Me need +ve Delta :)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i feel like i was at fault at that round , b wasn,t that hard i realise now

»
2 months ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

and thanks MikeMirzayanov for this amazing platform

»
2 months ago, # |
  Vote: I like it +30 Vote: I do not like it

In this announcement

Total comments = 32
Tester's comments = 69

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Going to participate from beyond the wall.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

As a non-tester, I will participate this round!

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Positive post

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I would like to be a newbie tester.(and I will solve 0 problems)

»
2 months ago, # |
  Vote: I like it +40 Vote: I do not like it

2000 points for div1C OMG

»
2 months ago, # |
  Vote: I like it +9 Vote: I do not like it

As a tester I can confirm that Agnimandur put a great deal of time and effort into creating a very clear and engaging problemset. I hope you guys enjoy the problems as much as I did.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for a good round.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Again I will participate and not answer anything . Cause this one be !easy too ...

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope the round will be interesting and i will cross 1350

»
2 months ago, # |
  Vote: I like it -44 Vote: I do not like it

![ ]()

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

rainbow follows VIBGYOR btw

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for putting effort for this round! Also hint-based editorial is nice :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Newbie Testers Go Here

POV: Newbie contestants are testers for future contests.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I hope the problem statements are short and the pretests are strong.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I hope I become specialist after this one.

»
2 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I Like Div2-735 round because of short statement and more interesting problem. Hope this round will be more interesting. );

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm exiting about the round. Thank You.

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I trust a Game of Thrones fan

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Did the newbie testers outperform the experts?

»
2 months ago, # |
  Vote: I like it +29 Vote: I do not like it

As a tester, I can confirm that this round has good problems and I hope that you will enjoy it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am really excited about it. By the way, how can someone become a problem test. Just asking out of curiosity.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can be a tester if you're a trusted friend of the author of the contest.

»
2 months ago, # |
  Vote: I like it -17 Vote: I do not like it

I hope I can solve the problem of 3 quickly

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I hope i don't struggle with B again

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

First round in August! Excited!

»
2 months ago, # |
  Vote: I like it +179 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

“regardless of your rating!”I hope so,but it keeps decreasing.T_T

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

so div1 has only one harder problem than div2? maybe it should have been div(1+2) in this case

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    Count again, for me it looks like the usual two.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      the last div2 is (2000-2500) and the one before last in div1 is (2000-2000) so it's the same problem which means div1 has one extra harder problem right?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck competitors.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Loved the testers section..

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What with the rating of E, is it easier than D?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Better than contest with 750 as first problem :)

»
2 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Oh f I just realised that you are shiva oswal ,champion of history bee tournament , see this, orz

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

My trash luck , I forgot to register so I have to wait for 10min. 5k submission for problem a . now when I can finally register, I am in long queue.

»
2 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Well Balanced Round. Thank you writers and testers :)

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

First few minutes problem statements to me (In m2 and m3. not able to check m1.)Your text to link here...

»
2 months ago, # |
  Vote: I like it -26 Vote: I do not like it

I hate div 2 C.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem D :( >>>> :) problem C

»
2 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Could not even get into codeforces/m1 codeforces/m2 codeforces during first 10 minutes!! Even after that it was loading wayyy too much. Then I panicked and could not even get B right for silly mistakes!!

»
2 months ago, # |
  Vote: I like it -18 Vote: I do not like it

speedforces!!!!!!!!!!!!!!!!!!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi,

Regarding problem D just to be sure I would like to confirm whether we are looking for a contiguous subarray or any subarray?

Thank you very much!

»
2 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Statement of C was very confusing :(

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Yeah, like why use the word "die" in the statement. I missed the part where they are resurrected and all friendships restored. Wasted an hour trying to see what is wrong. Could've been much clearer with a better wording.

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Thanks for such an amazing round!

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for great round , solved upto C

»
2 months ago, # |
  Vote: I like it -11 Vote: I do not like it

RuntimeErrorForces

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Getting wrong answer at pretest(5) for D

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think the mistake you are doing is for test case :-

    [3,4] here ans should be 1 but my code was giving 2 and get wa in test 5. so you can verify from this case.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it's giving 1

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I created the difference array, computed the gcd of subsequent terms, but it's giving wrong answer at pretest(5)

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Which terms did you take to compute gcd?

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          welp, I can't read.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It is guaranteed that all the numbers in a are distinct.

            ...

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            elements are distinct

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
              Rev. 2   Vote: I like it -61 Vote: I do not like it

              .

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Anyone can tell me why i got wrong answer my code. Because 2 and n/2 should be answer on problem A of question A and my loop can easily got n/2 value.

              void solve()
              {
                  ll n;
                  cin >> n;
                  for (int i = 3; i < 1e6; i++)
                  {
                      if (n % 2 == n % i)
                      {
                          cout << 2 << " " << i << "\n";
                          return;
                      }
                  }
              }
              
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Does your code manage the case n=1? That was my problem.

»
2 months ago, # |
  Vote: I like it +38 Vote: I do not like it

I submitted B first time right when CF crashed, then I went to one of the mirror sites, the submission wasn't showing up. I submitted again, only after that did the first submission show up. Both were TLE, so I got penalty for both. Is there a way to remove the penalty, considering it happened because of the crash? The codes were identical, which confirms my story.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    The second submission has been removed, thank you!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have faced same problem like u

  • »
    »
    2 months ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    On the same question i submitted twice with just 31 sec gap one through codeforces website and second through m1.codeforces.com.First approach was correct so they took 50 points for resubmission.Those 54 points cause of codeforces crash is causing me 500 rank difference.The codes were identical, which confirms my story.Don't know why MikeMirzayanov is not looking into it.Maybe cause i am just a specialist. :(

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Submitted a problem 2 mins ago.. still in queue

»
2 months ago, # |
  Vote: I like it +51 Vote: I do not like it

cf predictor not showing results anyone has the same issue

»
2 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Congrats antontrygubO_o you'll be LGM for the first time!

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

the unclear problem c statement cost me -50 :( ,maybe they could have told something like "for type 3 queries, we want to give the number of invulnerable nobles, IF we start killing all vulnerable nobles till there are none left" maybe that could have helped

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve D?

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

    i think binary search can do it but my solution getting TLE

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

      i tried similar,

      detailed logic

      attempt1

      complexity is $$$\mathcal{O}(n \space \log^2n \space \log{10^{18}})$$$, first log from binary search , second from segment tree query, third log from gcd function.

      that is not suffucient for $$$n = 10^5$$$. because $$$10^5 \times 20 \times 20 \times 60 = 2.4 \times 10^9$$$ that is high.

      So i did second attempt turning my binary search into two pointer.

      attempt2.

      complexity is $$$\mathcal{O}(n\space\log{n}\space\log{10^{18}})$$$, first log from segment tree query and second from gcd function. this is similar to editorial's complexity. but still i am getting TLE and i am unable to figure where is it getting wrong.

      UPD: found it was a stupid mistake only and codes are working now.
      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can u please check my solution, I have used segtree+sliding window+gcd. Here is my solution https://codeforces.com/contest/1549/my

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          very first of all sorry for late reply.

          first of all , that is not sliding window, in sliding window we fix the width of window at first.

          you have implemented two pointer, same as mine (but slight differently). { min ran at <200ms all cases }

          i found one error in your code and three errors that have yet not gave you WA/RE.

          Error1
          Error2
          Error3
          Error4

          thats all what i could find out of first glance there could be more.

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks for such a detailed error analysis. Finally, I was able to get AC in it.

            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              you are welcome.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Computing the difference array and finding the gcd works (a-b)%m = 0 i.e a-b = k*m

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Binary Search on answer + segment tree for range GCD. The segment tree gives TLE in Python so I used the Sparse table for that.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i realized it in last moment and couldn;t able to write whole code before time

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

    Using two pointers work. The fact that the contiguous array of the difference array (array containing the differences of the original array) has to have gcd greater than 1 in order for a subarray to be good allows this approach (hopefully) works

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I DID THAT, BUT GOT WA IN PRETEST(5)

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The funny thing is when I got WAs, I just resorted to good ol' #define int long long and it worked for me, but I got WA in pretest 7 so this may not be applicable for you.

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    Hint
    Solution
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Video Solution for D, this is how i did it!

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

First contest where I was able to solve A, B and C. Maybe they were too easy but still.

»
2 months ago, # |
Rev. 2   Vote: I like it +49 Vote: I do not like it

Problem C is actually very nice if perceived through generating functions. We're basically interested in the sequence generated by

$$$F(x) = \sum\limits_{n_0=0}^n (x+1)^{3n_0}=\frac{(x+1)^{3(n+1)}-1}{(x+1)^3-1}$$$
Here numerator can be calculated in $$$O(n)$$$ after which $$$F(x)$$$ can be obtained by standard long division division also in $$$O(n)$$$.

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

    I figured out a different method : Lets start at second s, and say last second is e, then

    S(x) = -C(3s,x+3) + C(3e+3, x+3) — 3*(S(x+2) + S(x+1)). This can also help in solving it on O(n) I think.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    TL was very tight :')

»
2 months ago, # |
  Vote: I like it +22 Vote: I do not like it

It seems like none of the testers spotted the easy solution of Div1D1.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    What was the easy solution? I used pick's theorem for finding that number of boundary points should be multiple of 4.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +16 Vote: I do not like it
      Hint
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +30 Vote: I do not like it

        I'm pretty sure that was one of the intended solutions for D1.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Then I don't know how it is harder than C...

          C is such a troll problem.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        That's exactly what I submitted in testing... (Infact, mod 2 after diving all coordinates by 2)

»
2 months ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

Time constraint on problem C is too tight I think. Just calculating factorials caused tle :(

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

A moment of silence for those who read the announcement about C after 1 hour from reading the problem including me

Edit : it's actually my fault if i read the problem better i would have understood that but I did the same mistake again i should not hurry up solving before completely understanding the problem

»
2 months ago, # |
  Vote: I like it +17 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it +52 Vote: I do not like it

Way too many points given to Div1D1/Div2F1 for its actual difficulty, in my opinion.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Idk why but problem D seems to be easier for me.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In my opinion, it was hard

»
2 months ago, # |
  Vote: I like it -69 Vote: I do not like it

please try to avoid useless implementation problems like C.... couldn't the problem setters find any better problem??

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    You found it hard doesn't mean the problem was bad. And you can't just bash problem setters for the same.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      whether i find the problem hard or easy is irrelevant to the problem being bad... in my opinion that problem was just there to give people some typing practice

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    What implementation was there? The trick was to understand you only need to know how many nobles there are that are not friends with higher nobles. That's it. look at my solution...

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why? The best way to train is to focus on your weakness and improve it, even I got a little bit tricky on problem C.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

lmao, I was 7th person to solve D, yet I struggled to solve B for an hour. I sometimes hate myself. :(

»
2 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

Sorry guys, please don't downvote >_<

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2 Problem C was elegant! Enjoyed solving it!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

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

    Check if you can kill enemy pawn in the same column, previous column (if enemy exists) and then next column (if enemy exists) for each pawn. Submission

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I used Graph with Adjacency list implemented using a vector of sets, was getting TLE on pretest 4, what could be wrong?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because adjacency list can go upto size of O(n^2).

»
2 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

I have submitted solution for b twice within a interval of 30 seconds both the solutions are exactly same.Thing is when i was submitting my first solution the website crashed so i submitted again from m1.codeforces.com .I lost 54 points cause of that it would be great if someone can help me through this.MikeMirzayanov

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In Problem Div2B, Solution passed the pretest when I used string instead of char array. Before it was giving wrong answer verdict for test case 5.Wasted 1hr. Any idea, why it happens? Passed — 124580177 Failed — 124546623

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am 'newbie' I have solve 2 question from div2 do I will get rated ?

»
2 months ago, # |
  Vote: I like it -18 Vote: I do not like it

WEIRD CODEFORCES COMPILER and WHY DOES THE CUSTOM INVOCATION EVEN EXIST DURING THE CONTESTS.(T_T)

Hello Codeforces community,

I joined codeforces recently but faced a weird issue in todays contest. In the problem C.Web of Lies.

The answers to sample input were compiling and showing perfectly correct answer in my sublime code editor and even online on more than 5 different sites.

BUT, I don't know what sort of a compiler does codeforces have (T_T) it always showed wrong answers on the sample test case.

More over if I try to use the CUSTOM INVOCATION, it literally takes 10 minutes to compile 1 piece of code.

WHAT TO DO IN SUCH A SITUATION, when all other compilers are showing correct result but codeforces compiler doesn't and the custom invocation is almost useless through out the contest.

Please someone with prior experience EXPLAIN how to tackle.

I know something must be wrong in my code.... BUT WHERE DO I DEBUG IT? (T_T)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Your profile pic is violating CF terms and conditions, consider changing it.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had a similar issue in the last two contests. Last contest was from going out of bounds in an array, and this contest was accessing a key that did not exist in a map. You probably have some type of runtime error

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      bro.. the answer is being printed... no errors. Just the answers don't match on cf compiler but matches on other compilers

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Look, in some compilers, it ignores out of bounds or erasing elements not in the set and so on. but in Codeforces the compiler doesn't, it prints an unexpected answer. here are some tips when you face these problem:

    • You can check your code on custom innovation (in the contest the custom invocation takes more time to compile because there are others in the contest that are submitting solutions but at any other time it works fine)
    • Check if you call an index in the array which is bigger than size or smaller than 0 (out of bounds).
    • Check if you are erasing or poping an element from a set, vector, queue, etc... and the size is 0 or the element that you are erasing doesn't exist
    • Check for any overflows
    • I think that you can find an offline compiler that is similar to custom invocation also if you are using CodeBlocks you can edit the settings to not ignore these problems
»
2 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Div1 B is basically same as this problem

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div 2D? please write your solution in hints.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      I did the same thing. It failed pretest 5. Any idea what it could be?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I was stuck at pretest 5 TLE because i bugged two pointers inequality

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Maybe ?

        1
        1
        1
        
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ans is 1 right? I did handle n=1 and n=2 separately.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            not sure, I got two wrong answers because of that case :/

»
2 months ago, # |
  Vote: I like it -15 Vote: I do not like it

I love your problems <3.

E is #combinatorics

F is #geometry, Pick's theorem? I don't know for sure.

Not only the topic you covered but also: Short, clear statements.

You got my orz, sir!

Waiting for the solution!

»
2 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Great Round! Thanks!

»
2 months ago, # |
  Vote: I like it +9 Vote: I do not like it

I HATE GCD

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C ? I couldn't even get a clue after 1.5 hours

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

    All you need to do is maintain $$$indegree$$$ for each vertex and add initial $$$vulnerable$$$ vertices in a set . For $$$query$$$ of type 3 $$$answer$$$ will be $$$n-vulnerable$$$ $$$points$$$. For type 1 $$$query$$$ increase $$$indegree$$$ of smaller vertex by 1 and add it to the set if not already added . For type 2 $$$query$$$ decrease $$$indegree$$$ of smaller vertex by 1 and remove it from set if it's $$$indegree$$$ after update becomes 0

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Oh.. Thanks a lot. I was doing something complicated unnecessarily

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Make a frequency array $$$f$$$, where $$$f_i$$$ represents how many nodes $$$j$$$ are greater than $$$i$$$. The answer is $$$n - k$$$, where $$$k$$$ represents the number of nodes $$$i$$$ where $$$f_i > 0$$$. For each $$$1$$$ operation, increase $$$f_u$$$, where $$$u < v$$$ by one. If $$$f_u$$$ was initially 0, then increase $$$k$$$ by one. For each $$$2$$$ operation, decrease $$$f_u$$$ by one. If $$$f_u$$$ was initially 1, then decrease $$$k$$$ by one.

    Code
    • »
      »
      »
      2 months ago, # ^ |
      Rev. 4   Vote: I like it -12 Vote: I do not like it

      I submitted a similar solution during contest, but it failed pretest 4 as WA. Can someone help? 124599669 Edit: Just found out why. It was because I unnecessarily reset the states after doing query type 3.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me, what's wrong in my code.

my code
»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Great problems!

»
2 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Great contest!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really hope C task did not have any spoilers. T_T. Just started GOT. ><

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

i like the sentence "the wolf does not eat the little pigs, he only makes plans"

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E: The three Little Pig

Can anyone suggest any improvement to my code other than taking mod of 1e9+7 while output ans1 so that it doesn't show TLE. 124595320

»
2 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

is fft possible for d1c somehow? i understand that modulo is bad, but maybe it's possible with some magic

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, I designed the problem to be as hard as possible for FFT to pass. Maybe it works, IDK, but it would be a very very tight squeeze.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Any particular reason for this choice? I don't think FFT-based deconvolution is any more or less interesting than the long division approach I ended up coding.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +2 Vote: I do not like it

      It's barely even possible to calculate multiplicative inverses of $$$1, \ldots, 3N$$$. No way even a single $$$O(3N\log N)$$$ FFT would pass.

      Or so I thought...

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

        You can use the formula $$$(n!)^{-1}=((n+1)!)^{-1}\cdot (n+1)$$$ to calculate multiplicative inverses of factorials in linear time, and thus multiplicative inverses in linear time.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Ah, of course! I was always using the trick that $$$(2n)^{-1} = 2^{-1} n^{-1}$$$.

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

          Nice trick. I usually find inverse modulo $$$m$$$ for all numbers from 1 upto n with $$$i^{-1}=-[m/r] \times (m\%i)^{-1} (mod\, m)$$$ and then multiply them all together to get inverse factorials. (Proof can be found here: http://e-maxx.ru/algo/reverse_element#4 )

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    This works in 764ms.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For the last one hour I was stuck on D with this problem- "If I apply two-pointers on diff array, how can I find gcd of each segment?". At the last minute, it occurred to me that I can use Segment Tree. But it was too late by then. Looks like I have to practice more seg tree problems.

Great Problems tho. Loved them all :)

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

    Or if you are in the minority like me — use the sparse tables :P

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I also used sparse tables. I still don't know how two pointers works

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        Notice that for $$$i$$$ if it contributes to the final answer $$$f(i) >= f(i - 1)$$$ This essentially means that we should keep some suffix of the maximum result for $$$i$$$ in the result of $$$i + 1$$$. So just traverse left indices from $$$0$$$ to $$$n - 1$$$ and greedily try to match the maximum suffix of $$$i - 1$$$ to $$$i$$$. Take a look at my submission to understand it better.

        To practice this sort of things take a look at last educational round's E or CodeChef Lunchtime Div1A that was held yesterday. Both of them utilize two pointers in the same fashion this one does.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Got it, thanks. I confused myself. I thought there was some raw two pointers magic to solve it without using sparse tables or segtree, but the two pointers is just the alternative to binary search

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the contest.

»
2 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Good questions, Good contest . Hope the pretests are strong !

»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Why aren't they allowing segment trees to pass in D. I didn't knew about sparse tables.. :((

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Editorial has been released!

»
2 months ago, # |
  Vote: I like it +114 Vote: I do not like it

why the system tests are so slow?

»
2 months ago, # |
Rev. 2   Vote: I like it +68 Vote: I do not like it

Seems like system testing stopped, does anyone now why?

»
2 months ago, # |
  Vote: I like it +33 Vote: I do not like it

Cool contest!

Is it just me or did the expected rating calculator break during contest?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yeah, it was broken throughout the whole contest for me

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    Because the server banned the API for rating calculator during the contest,so everyone was affected.

»
2 months ago, # |
Rev. 2   Vote: I like it -40 Vote: I do not like it

Problem C- Web lies My code is giving memory limit exceed on pretest 4 Can anyone give an efficient solution ? so that i can check where I did wrong. submission :- 124601371

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    paste your code and run it on (https://ideone.com/) and share the link . It is very difficult for anybody to read your code now.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You seem to be using an adjacency matrix to represent your graph, which has O(n^2) space complexity. Try using an adjacency list instead.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

system testing is teasing now !

»
2 months ago, # |
  Vote: I like it +77 Vote: I do not like it

Come on guys, technical issues are unavoidable but at least you need to communicate. Or are we due for another donation campaign?

»
2 months ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

It was great to listening to Light of the seven while reading C.Web of Lies. that's why my fantasy drived me far away from the solution.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Best editorials <3

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when it is possible to virtually participate?

»
2 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Why is system testing slower than my learning rate?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am waiting for hacking

»
2 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Was someone as savage as me to submit a flow solution to div2B? XD

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I believe no XD

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Hopcroft-Karp-Karzanov algorithm with some optimization might pass the tests within the time limit. Because the number of edges will be at most 3n.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, sure. With Max flow I meant the max matching approach.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I did XD

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

SAAAAAAAAAAD man! I got MLE in problem D for not handling the case n=1 as I was using Segment tree. Even though I don't know why it gives MLE I think in this problem, it should give a runtime error.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same. Not handling n=1 case. And got MLE. (╯︵╰,)

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Same didn't realized that until I saw your comment, I thought maybe $$$4N$$$ was too large but fortunately writing iterative segment tree worked it didn't required handling $$$n=1$$$ case separately.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was thinking the same as you, typically! but the problem is that the contest ends before I finished writing the iterative segment tree as I haven't trained before on the iterative ones.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Time taken for system testing == Number of times the site crashed

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You didn't even took part in the contest, what system testing are you waiting for?

»
2 months ago, # |
  Vote: I like it -13 Vote: I do not like it

I submitted A first time right when CF crashed, then I went to one of the mirror sites Codeforces3, the submission wasn't showing up. I submitted again, only after that did the first submission show up. so my first solution was skipped last solution wask taken. Is there a way to remove the last submissions, considering it happened because of the crash? The codes were identical, which confirms my story.

→ Reply

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As a newcomer it's really frustrating for me. I think CF CF team will consider my situation.Thank you

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Apparently you can't resubmit your same code.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    You literally copy-paste this comment and moreover, YOU FORGOT TO ERASE THE "→ Reply" text

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bro i have faced the same problem but my english isn’t good at al so i copy past his comment.is there any problem.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    Come on, at least make an efford

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Hehe nice, imitation is the sincerest form of flattery...

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

        I replied it in your comment that i have faced the same problem like you.My english isn't good so i decided to copy your.by the way give me some pro tips that how can i be a master like you?

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +21 Vote: I do not like it

          No worries, I just found it funny. There aren't many pro tips I can give you, but here are a few notes for you current level: 1) don't focus on known algorithms, you will never see them in div2 A and B problems 2) focus on coding and learning to debug efficiently (you will always make mistakes) 3) always upsolve problems A, B and sometimes C from rounds, if you miss a round try to do it virtually.

          Biggest tip is to have fun and don't worry too much about rating. You are at a point where much improvement is possible. Best of luck!

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks for your valuable suggestions❤️

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it -6 Vote: I do not like it

              Anyone can tell me why i got wrong answer my code. Because 2 and n/2 should be answer on problem A of question A and my loop can easily got n/2 value.

              void solve()
              {
                  ll n;
                  cin >> n;
                  for (int i = 3; i < 1e6; i++)
                  {
                      if (n % 2 == n % i)
                      {
                          cout << 2 << " " << i << "\n";
                          return;
                      }
                  }
              }
              
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            what a person should focus on if the person can solve A,B,C(sometimes) in contest. Upsolve C,D ? or something else

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              If you're high pupil/specialist and solve ABC, at that point you should start learning some very basic algorithms, maybe about graphs (not above DFS and BFS!) and dp (again, nothing too complicated). Always upsolve C and D (D might be a bit hard, but try to read the solution anyways). If you're solving ABC and you're not at least high pupil, you should still follow the last plan and practice more coding.

              • »
                »
                »
                »
                »
                »
                »
                »