Agnimandur's blog

Codeforces Round #736
By Agnimandur, 3 years 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. Monogon, 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. Rewinding, 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. _riceshower
  3. black_trees
  4. lajixtc
  5. soumilaggarwal

Fastest Solves

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

Comments Comments (278)
| Write comment?
»
3 years ago, # |
  Vote: I like it +83 Vote: I do not like it

Thanks for the early score distribution!

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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

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

    can newbies be testers?

    → Reply
    • »
      »
      »
      3 years 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

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

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

    → Reply
    • »
      »
      »
      3 years 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. :(

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

Div 2 Speedforces incoming

Spoiler

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

As a tester, let me participate officially

Spoiler
→ Reply
  • »
    »
    3 years 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 :)

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

Discrimination of testers on the basis of colour :(

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

As a tester, problems are great!

→ Reply
»
3 years 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...

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

As a VIP tester I recommend everyone to gain rating!

→ Reply
»
3 years 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!

→ Reply
»
3 years 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

→ Reply
»
3 years 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

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

I hope to become specialist after this round

→ Reply
  • »
    »
    3 years 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

    → Reply
    • »
      »
      »
      3 years 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)

      → Reply
»
3 years ago, # |
  Vote: I like it +99 Vote: I do not like it
lighthearted meme
→ Reply
»
3 years 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?

→ Reply
  • »
    »
    3 years 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.

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

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

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

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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 ;)

→ Reply
  • »
    »
    3 years 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

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

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

→ Reply
  • »
    »
    3 years 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

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
  • »
    »
    3 years 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

    → Reply
    • »
      »
      »
      3 years 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(

      → Reply
»
3 years 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)

→ Reply
  • »
    »
    3 years 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

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

and thanks MikeMirzayanov for this amazing platform

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

In this announcement

Total comments = 32
Tester's comments = 69

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

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

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

Positive post

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

2000 points for div1C OMG

→ Reply
»
3 years 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.

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

rainbow follows VIBGYOR btw

→ Reply
»
3 years 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 :)

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

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

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

I hope I become specialist after this one.

→ Reply
»
3 years 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. );

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

    dont bomb the contest

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

      I don't bomb on innocent platform like (Codeforces). Cz, Everybody loves it. I also love it.

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

        Is Codeforces halal, probably not

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

          I think, you should focus on yourself brother. It is not debating site.);

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

I trust a Game of Thrones fan

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

Did the newbie testers outperform the experts?

→ Reply
»
3 years 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

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

I hope i don't struggle with B again

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

https://millionaire.fandom.com/wiki/Shiva_Oswal
Agnimandur is it you? Amazing!

→ Reply
»
3 years 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

→ Reply
»
3 years 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

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

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

    → Reply
    • »
      »
      »
      3 years 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?

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

Better than contest with 750 as first problem :)

→ Reply
»
3 years 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

→ Reply
»
3 years 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.

→ Reply
»
3 years 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...

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

I hate div 2 C.

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

Statement of C was very confusing :(

→ Reply
  • »
    »
    3 years 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.

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

Thanks for such an amazing round!

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

Thanks for great round , solved upto C

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

RuntimeErrorForces

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

Getting wrong answer at pretest(5) for D

→ Reply
  • »
    »
    3 years 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.

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

      it's giving 1

      → Reply
      • »
        »
        »
        »
        3 years 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)

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

          Which terms did you take to compute gcd?

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

          welp, I can't read.

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

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

            ...

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

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

    → Reply
»
3 years 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.

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

    The second submission has been removed, thank you!

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

    I have faced same problem like u

    → Reply
  • »
    »
    3 years 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. :(

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

cf predictor not showing results anyone has the same issue

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

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

→ Reply
»
3 years 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

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

How to solve D?

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

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

    → Reply
    • »
      »
      »
      3 years 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.
      → Reply
      • »
        »
        »
        »
        3 years 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://mirror.codeforces.com/contest/1549/my

        → Reply
        • »
          »
          »
          »
          »
          3 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years 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.

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

              you are welcome.

              → Reply
  • »
    »
    3 years 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.

    → Reply
  • »
    »
    3 years 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

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

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

      → Reply
      • »
        »
        »
        »
        3 years 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.

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

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

    → Reply
»
3 years 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.

→ Reply
»
3 years 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)$$$.

→ Reply
  • »
    »
    3 years 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.

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

    TL was very tight :')

    → Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +16 Vote: I do not like it
      Hint
      → Reply
      • »
        »
        »
        »
        3 years 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.

        → Reply
        • »
          »
          »
          »
          »
          3 years 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.

          → Reply
      • »
        »
        »
        »
        3 years 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)

        → Reply
»
3 years 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 :(

→ Reply
»
3 years 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

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

→ Reply
»
3 years 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.

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

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

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

In my opinion, it was hard

→ Reply
»
3 years 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??

→ Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years 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

      → Reply
  • »
    »
    3 years 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...

    → Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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. :(

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

Div2 Problem C was elegant! Enjoyed solving it!

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

How to solve B?

→ Reply
  • »
    »
    3 years 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

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

      also keep updating those pawns that have already reached the end line.

      → Reply
»
3 years 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

→ Reply
»
3 years 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)

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

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

    → Reply
  • »
    »
    3 years 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
    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Div1 B is basically same as this problem

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

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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    → Reply
    • »
      »
      »
      3 years 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?

      → Reply
      • »
        »
        »
        »
        3 years 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

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

        Maybe ?

        1
1
1
        → Reply
        • »
          »
          »
          »
          »
          3 years 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.

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

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

            → Reply
»
3 years 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!

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

I HATE GCD

→ Reply
»
3 years 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

→ Reply
  • »
    »
    3 years 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

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

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

      → Reply
  • »
    »
    3 years 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
    → Reply
    • »
      »
      »
      3 years 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.

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

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

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

Great problems!

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

Great contest!

→ Reply
»
3 years 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"

→ Reply
»
3 years 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

→ Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
    • »
      »
      »
      3 years 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...

      → Reply
      • »
        »
        »
        »
        3 years 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.

        → Reply
        • »
          »
          »
          »
          »
          3 years 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}$$$.

          → Reply
        • »
          »
          »
          »
          »
          3 years 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 )

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

    This works in 764ms.

    → Reply
»
3 years 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 :)

→ Reply
  • »
    »
    3 years 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

    → Reply
    • »
      »
      »
      3 years 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

      → Reply
      • »
        »
        »
        »
        3 years 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.

        → Reply
        • »
          »
          »
          »
          »
          3 years 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

          → Reply
»
3 years 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.. :((

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

Editorial has been released!

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

why the system tests are so slow?

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

Seems like system testing stopped, does anyone now why?

→ Reply
»
3 years 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?

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

    Yeah, it was broken throughout the whole contest for me

    → Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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

→ Reply
  • »
    »
    3 years 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.

    → Reply
  • »
    »
    3 years 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.

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

system testing is teasing now !

→ Reply
»
3 years 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?

→ Reply
»
3 years 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.

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

    I was getting constant GOT nostalgia while solving D2C.

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

Best editorials <3

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

Why is system testing slower than my learning rate?

→ Reply
»
3 years 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

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

    I believe no XD

    → Reply
  • »
    »
    3 years 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.

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

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

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

    I did XD

    → Reply
»
3 years 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.

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

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

    → Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years 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.

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

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

→ Reply
  • »
    »
    3 years 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?

    → Reply
»
3 years 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

→ Reply
  • »
    »
    3 years 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

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

      Apparently you can't resubmit your same code.

      → Reply
  • »
    »
    3 years 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

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

    Come on, at least make an efford

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

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

      → Reply
      • »
        »
        »
        »
        3 years 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?

        → Reply
        • »
          »
          »
          »
          »
          3 years 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!

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years 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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years 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.

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

Did anyone else solve B by maximum matching? Yes, I'm that dumb!

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

time until sys test end

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

tl retest(tl retest)

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

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

I couldn't find problem F or G xD. I wonder what happened?

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

    Testers look at the round as combined, so G refers to div1E.

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

From problems to editorial, I can see that you have put in a lot of efforts to make us learn things. Thank you so much for this round!

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

Thanks for the contest <3. Hope you make more contests like this one.

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

During the contest Codeforces freezed! But I was able to submit the soolution for the second problem in main website. But it didn't show any confirmation of the submission. As a result, I assumed that my solution wasn't submitted hence I submitted the exact same solution again on m1.codeforces.com. If both the solution are exactly same why should the first solution be skipped and not the second one ?

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

I think problem D was pretty similar to a codechef problem Max Subarray GCD.

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

lol I thought in C you have to print the number of moves in which the process ends

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

Wait a minute, how am I on the fastest solves list? I didn't even close to be the fastest solve on A.

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

Does Gregor (in the problem statements) stand for Gregor Clegane (Game of Thrones character)?

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

As a code author, I hope you gained rating!

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

Tourist is at a point where 2nd place is also costing him some ratings!

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

    Let's wonder when tourist will lose rating at the 1st place XD

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

      But actually, maybe it's not realistic :(

      Only if tourist gains inf rating XD

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

Editorial dissapeared. Agnimandur take a look please.

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

Why does it says that I'm not allowed to see the editorial?

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

Why cant I access the tutorial?

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

How can I see the Editorial?I was told that "You are not allowed to view the requested page".

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

The tutorial seems still wrong now.I hope Agnimandur knows it.

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

Why can't I access the editorial? Is there anyone who has the same problem?

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

    I can't neither. I am not allowed to view the requested page

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

      That's so strange. Might check it tomorrow

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

Why can't I watch Editorial?It gives me "You are not allowed to view requestedx ..." warning.

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

    It will get fixed. Yesterday too same issue came up but got fixed after few hours :)

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

Can't access Editorial. Please fix it.

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

Do cp they said, It will be fun they said.. :_)

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

Thanks

→ Reply