By awoo, history, 4 months ago, translation, In English

Hello Codeforces!

On Feb/15/2021 17:35 (Moscow time) Educational Codeforces Round 104 (Rated for Div. 2) will start.

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

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

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

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

Good luck to all the participants!

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

Codeforces and Harbour.Space

Amazing news, Codeforces!

As we promised last time, we are coming back with a new scholarship opportunity!

We have partnered with Coherra to open the door for an exciting career in technology for the most talented people in our network.

In partnership with Coherra, we are offering a full scholarship to study a Master’s in Front End Development at Harbour.Space while working as a Front End Developer at Coherra!

Scholarship Highlights:

Work in Europe’s most exciting tech cities

Scholarship value of up to €22,900 to study at Harbour.Space University

Competitive compensation for the internship at Coherra

Opportunity to join Coherra full-time after graduation

We have previously partnered with other companies like OneRagtime, Hansgrohe, and Remy Robotics to empower young talents around the world and help them boost their tech career. We’ve already filled a few of the positions with our partners including:

  • Full Stack Developer at OneRagtime awarded to Alejandro Martinez from Mexico
  • Innovation Designer at Hansgrohe awarded to Giorgi Zhuzhiashvili from Georgia

We are always happy to see Codeforces members join the Harbour.Space family. Apply now to get a chance to learn from the best in the field and kickstart your career!

Keep in touch and follow us on LinkedIn for more scholarship opportunities. And follow us on Instagram to evidence student life, events, and success stories from our apprenticeship programme students.

Good luck on your round, and see you next time!

Harbour.Space University

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Muffinhead 7 211
2 noimi 7 271
3 LayCurse 7 279
4 satashun 7 333
5 nhho 7 366

90 successful hacks and 1286 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A h__h 0:01
B noimi 0:04
C MurasakiShion 0:07
D peti1234 0:06
E Bhaiya_ko_nahi_batana 0:12
F uwi 0:51
G renascencepjw0510 0:27

UPD: Editorial is out

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

»
4 months ago, # |
Rev. 3   Vote: I like it -6 Vote: I do not like it

Thanks to awoo, Roms, adedalic, vovuh, BledDest and Neon for preparing the Div.2 contest.

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

I wish this contest took place today. For single guys like me this could have been the perfect valentine :'(

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

    But you are not thinking about singles who would have received negative delta.

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

      But he did not say that positive delta is a necessary condition for a contest to be the perfect valentine.

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

        For most of us it is, I would not call a large negative delta contest to be perfect for me and you would agree there would be participant falling into this category.

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

          Holding a contest on a given day may be a perfect gift to a person, even if the outcome might not turn out to be perfect.

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

What is the reason behind Educational round not having any testers?

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

I hope that the conditions will also be short and clear as in the last round :)

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

I will do a stream after the contest, on https://twitch.tv/AnandOza

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

    Can you please shift to YouTube, you'll certainly get a larger watch base over there. Who watches coding videos on twitch anyways?

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

      Twitch is objectively better than YouTube for streaming

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

        Maybe, but I don't understand very well why people are so obsessed with streaming. I mean, It would be much better to make and edit video editorials and then submit them. Viewers could ask questions in the comment section or the author could make a live broadcast for Q&A.

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

          It is more interesting for the content creator to stream and chat live with the subscribers than to record alone and then answer questions in the comments. Moreover, the content quality actually goes up if you are streaming, because all the frequent questions are answered directly in the video and not somewhere in the comments where you have to find them first.

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

      I upload my broadcasts to YouTube later, and post screencasts on YouTube as well. Feel free to subscribe at https://www.youtube.com/c/AnandOza.

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

Can we expect short statements? It would be very pleasant to see short statements on the problems :)

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

    Can we expect strong pretests? It wouldn't be very pleasant to see FSTforces. :) (FSTforces makes +136 for me) forgive my poor English:)

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

Just 1 day earlier and this contest might be my savior in the day that wasn't born for a single like me

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

    A Valentine's Day date with codeforces. :)

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

I hope the contest will be on time without any delay

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

delayed for 6 minutes to 6 hours :(

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

Yesterday was 3 years since my first contest, that was a Valentine contest. As luck would have it, problem A was the most difficult in the history of the Div2 rounds, its difficulty was 1400 !!!

Meme of that round:

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

All I wanted from Mike:

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

    You want negative delta?

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

      Reverse psychology, you know, all the time I was hoping for a good positive delta to become master (while also practicing), but you know what? Screw it! Let's have $$$fun$$$!

      So... I decided to take $$$a few$$$ days off! And now I just want chill around and do stuff I like.

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

Good luck for everyone! GLHF)

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

Is it not true that the round is Rated?

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

    no

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

    Is it (not true) that the round is Rated? => Is it false that the round is Rated? => is this contest unrated? This is what we expect from div2. A problem.

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

Тhe way to happiness is only through Educational Codeforces Round 104!

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

Hello guys finally i am back after a pause of 20 days because of my faulty laptop but hey... i have practicing on paper a lot ....so i hope today i become specialist . As always good luck to all. Keep Coding!!

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

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

Can somebody recommend me some basic problemset on DP and Graphs. I am able to solve standard problems but I struggle a lot on codeforces. Please recommend some good resources for the same too.

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

Valentine’s Day is the programmer’s holiday.

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

Really Excited for this contest, in last 2 contests I dropped down my from my Specialist spot. Hope I will regain it in this Contest. Good luck to everyone <3

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

those cyans who will be blue today will regret tomorrows div3

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

I haven't yet seen a comment with 69 downvotes. Hmm.. pretty disappointed.

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

do all questions have the same weightage?

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

Is this TypeRacerForces?

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

I didn't like a single one of the problems, and probably no one did. Is there a joke I didn't get? Why did you do this?

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

    I think starting from E they look nice to me

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

    Face reality: "Educational" means "to boring to be used in standard contest".

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

      nah bro educational means educational, "too boring" ain't educational.

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

I think I burned my every brain cell solving C. Atleast I succeeded.

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

How come (sqrt(2 * n + 1) — 1) / 2 isn't the solution in D?

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

    2*n-1 not 2*n+1 :)

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

      I know it's a dumb question, but I'm still not getting how.

      We have:

      a^2 — b = sqrt(a^2 + b^2)

      a^4 — 2a^2b + b^2 = a^2 + b^2

      a^4 = a^2 + 2ba^2

      a^4 = a^2(1 + 2b)

      => a^2 = 1 + 2b

      b <= n => 2 * b <= 2 * n + 1

      I'm sorry again if I made some mistake, but please correct me in the place I am wrong.

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

        c=b+1 so actually b<=n-1.

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

          Oh, I solved the system of equations wrongly, shame on me. Thanks for explanation.

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

        Hear me out!

        $$$(d(m^2+n^2))^2=(d(m^2-n^2))^2+(d*2mn)^2$$$

        then either:

        $$$m^2+n^2=d*(2mn)^2-(m^2-n^2)$$$

        or

        $$$m^2+n^2=d*(m^2-n^2)^2-2mn$$$

        first one gives

        $$$2m^2=d*4m^2n^2$$$

        so

        $$$1=2dn^2$$$

        which is impossible

        the second one gives

        $$$(m+n)^2=d(m-n)^2(m+n)^2$$$

        which gives $$$d=1$$$ and $$$m-n=1 <=> m=n+1$$$ so basically solutions are of form

        $$$(2a^2+2a+1, 2a+1, 2a^2+2a)$$$

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

    it is (sqrt(2*n-1)+1)/2-1

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

I can't be the only one who found D easier than B?

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

    And easier than C as well ...

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

    I just searched it on Wolfram Alpha

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

    Yeah for me D was easier than B and far easier than C. How did you guys solved C?

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

      I used cyclic permutation

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

      Parity of sum i+j. If the number of teams is even, game of teams $$$2k$$$ and $$$2k+1$$$ $$$(k=0...\frac{n}{2})$$$ is a tie

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

        My solution is very different and I am yet to prove why it is correct Basically we can find a formula $$$n(3n - 3 - 2s) = \sum{t_i}$$$ where $$$s$$$ is score of each team and $$$t_i$$$ is number of ties played by team $$$i$$$. Here comes my unproved assumption that each team will play same number of ties. Now to minimise total ties maximize score and then I just greedly assigned wins, loses and ties and I don't know why this is correct

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

          By giving explicit constructions, we can show that it is possible to have $$$0$$$ ties if $$$n$$$ is odd, and $$$n/2$$$ ties if $$$n$$$ is even. So, to prove correctness, we only need to show that when $$$n$$$ is even, then $$$n/2$$$ ties is the best number of ties possible.

          Claim: If $$$n$$$ is even, then the minimum number of ties must be at least $$$n/2$$$.

          Proof: If there are exactly $$$T$$$ ties among all $$$\binom{n}{2}$$$ matches, then the total score of all teams must be $$$3\left(\binom{n}{2} - T\right) + 2T = \frac{3n(n-1)}{2} - T$$$. Since each of the $$$n$$$ teams gets the same score, this number must be divisble by $$$n$$$.

          We now use the assumption that $$$n$$$ is even. We can assume that $$$n = 2k$$$ for some positive integer $$$k$$$, and hence, $$$\frac{3n(n-1)}{2} - T = \frac{6k(2k-1)}{2} - T = 6k^2 - 3k - T$$$. This must be divisible by $$$n = 2k$$$. It is easy to see that this is true when $$$T = k = n/2$$$, and there is no smaller possible value for $$$T$$$. $$$\square$$$

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

            I believe that this solution gives another nice proof of why the number of ties is optimal (since it argues in terms of in-degrees and out-degrees of a vertex which need to be equal).

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

            From this, we can also show that for any optimal configuration with even $$$n$$$, each team must have exactly one tie.

            Indeed, from the proof above, we know that the total score of all $$$n$$$ teams is $$$6k^2 - 3k - k = 6k^2 - 4k$$$, so the total score obtained by each team is $$$\frac{6k^2 - 4k}{2k} = 3k - 2$$$, which is not a multiple of $$$3$$$. On the other hand, if a team has no ties, then their total score is a multiple of $$$3$$$. So, it is impossible to have a team with no ties. Each team must have at least $$$1$$$ tie.

            Together with the fact that there are $$$n/2$$$ ties in total, it is easy to see that each team must have exactly $$$1$$$ tie.

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

      Greedy)))

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

    I misread the statement of problem B :( And stuck on it for an hour...

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

can anyone explain how to approach question d..like i am failing in the tc.

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

    From the two formulas it follows that $$$c=b+1.$$$ Moreover, difference between $$$c$$$ and $$$c-1$$$ must be a square

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    • `It involves a bit of mathematics. So you have 2 equations

    1) a^2 + b^2 = c^2

    2) c = a^2 - b

    • From equation 2, find the value of a^2, which is c + b and then substitute it in equation 1. From there, you will a relation of the form c * (c-1) = b * (b+1). On careful observation, you will see that this can be true only when b = c-1. So, the problem reduces to counting the number of pythogorean triplets having the length of the hypotenuse and the longest leg differing by 1.

    • As it turns out, such a triplet has the form (2n + 1, 2n^2 + 2n, 2n^2 + 2n +1). Here is the hypotenuse is of the form 2n^2 + 2n + 1 and hence you can easily loop until you reach the limit.

    • Link to my submission: https://codeforces.com/contest/1487/submission/107441210

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

    Pythagorus theorem -> a*a+b*b=c*c , a<=b<=c

    and eqn in question -> c=a*a-b

    solving both equation we will get c = b+1

    so let b = m then c = m+1 and a = sqrt(2*m+1)

    since c<=n

    so m+1<=n => m<=n-1 => 2*m<=2*n-2 => 2*m+1<=2*n-1

    sqrt(2*m+1) <= sqrt(2*n-1)

    so our ans is number of odds(since 2*m+1 is of odd form) less than or equal to sqrt(2*n-1)

    but we have to subract one from our ans since sqrt(2*m+1) cannot be 1(if it is 1 then m = 0, which is not possible).

    Hope it helps.

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

    c=a2-b

    a2=c+b

    3*3=9=4+5

    5*5=25=11+12

    7*7=49=24+25

    9*9=81=41+40

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

Anyone have a clue what test 18 of E is?

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

I think that there is a bug with the penalty for wrong submissions for this round. I made one wrong submission for problem B(and got no time penalty) and three wrong submissions for problem C (and got only two time penalty).

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

Is E just doing DP courses by courses and for storing DP values of previous course in segment tree to get DP values in current course i.e. for DP[i] in current course we will get $$$m$$$ segments in previous course to consider value?

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

    You don't need a segment tree, just a set that contains the previous dp values. For each dish, remove the dp value of dishes that don't go well with it and insert them back afterwards.

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

    We can see that m_i is less than 2000000, so we just sort the DP value of the last course. Then we just select the minimum DP value (and skip the DP value if they can't get well with each other) for each current course and generate a new DP value.

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

    We can solve E with brute force. For each vertice i from 2 to 0 brute the minimum valid vertice (i + 1). And it work O((n + m) * log2(m))

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

    Does this really constitute searchable? Its literally just substituting and expanding the equation.

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

Wrong answer on test 40 on E :( This is annoying

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

The risk I took while submitting C was calculated but I forgot that I'm bad at math (-_-)

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

[pE] What's the point of having 4 things.

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

    Exactly :(

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

    Well, the main reason is that, on 3 dishes, you can iterate on the second one and take the cheapest first and third option that goes well with it.

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

Maybe the gap between E and the last two problems are a little bit too large(which according to the statistics are solved by 973,14 and 42 participants respectively)

anyway,good problems and strong pretests!

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

ParityForces

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

This contest was not at all educational.

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

    How? Please elaborate. I found the problems interesting.

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

    It teaches you "educational rounds are not educational" XD

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

    Educational contests teach you to hack other's codes. This is useful for debugging own code

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

The formula of D is $$$ b(b+1)=c(c-1) $$$ i.e. $$$ b=c-1. $$$ Difference of squares $$$ n^2-(n-1)^2 = 2n-1. $$$ For all $$$i=3...10^5$$$ write down all $$$n$$$ such that $$$ n^2-(n-1)^2 = i^2 $$$ (or $$$i^2 = 2n-1$$$ or $$$n=\frac{i^2+1}{2} $$$) and use binary search to count the answer

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

Any ideas why this gives wrong answer in test 24 for E:107463591

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

Can someone explain the approach for problem E? I think we have to start finding the minimum value from each of the n3 values to n4. Now we will move to n2 and then find the minimum from n2 to n3 for each n2 and so on.... Am I correct? If the logic is same then how all of you optimized?

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

    I wasn't able to code completely but i think following would have worked :

    Consider a,b,c,d as arrays consisting of cost of first course, a second course, a drink, and a dessert.

    Now in array b , for each index we can add minimum cost in array a.

    Similarly for each index in c we can add minimum cost in array d .

    In both above we need to consider only those pairs which are not connected . It can be done with multiset .

    Now for each index in b find minimum cost in c and take the minimum.

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

      Yeah I am saying the same thing. But isn't finding minimum will be O(n^2)? How are you optimizing it?

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

        Suppose for each value in $$$b$$$ we need to find minimum cost in array $$$a$$$. You can create multiset consisting of pair $$${a[i],i}$$$ . Now you can create adjacency list for array $$$b$$$ such that for each $$$b[i]$$$ it contains all $$$i$$$ in $$$a$$$ which it cannot be paired with.

        While traversing $$$b$$$ , at particular $$$i$$$, remove all those pairs from multiset and then take the minimum value . finally add again all those values back.

        Similarly for all other parts.

        Complexity would be $$$O(max(n,m)log(max(n,m)))$$$ where $$$m$$$ is all the pairs which are incompatible .

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

    You can use multiset to get the minimum value. While looking at the i'th element delete the values of the food which doesn't go with i'th element. Now get the minimum value in multiset. At last of i'th step add those deleted values back into multiset.

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

      Ohh great!! Deleting the elements and then adding the same elements in the multiset, I haven't thought of. Thanks !!

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

the contest is done. Can I legally upload my solutions to github?

will there be information for the solutions of the problems(unhappy to say I need only for B and C) ?

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

Thanks for the contest, even though I couldn't perform well, I got to learn a bunch of things!

Kudos to the authors

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

I don't know why my D solution was giving TLE using C++14 and then got AC after I submitted with C++17. Can anyone please help me out?

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

    wait, your solution's time complexity is O(t * sqrt(n)), and in the worst case it has to do ~3*10^8 , how can it pass?

    I've submitted your solution and here is the result:

    • GNU C++11(or C++14): >2000ms

    • GNU C++17: 1965ms (surprised face)

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

    Probably some slight difference in the compilation process based on the chosen standard that leads to a small difference in runtimes, or just normal run to run variability, since you are very close to the limit.

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

Getting input on E was harder then solving real problem

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

    Success in E today depended on how fast you solve A,B,C,D. It was bit lengthy implementation due to large inputs.

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

      Solved B in 45 minutes lol

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

        i expected i will take more time to solve, so went with C lol

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

      25 minutes to solve ABCD another 25 to solve E but why are F and G so difficult?! :(

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

    Write macros/functions so that you can input common data formats without much typing.

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

Why always easier G than F in edu rounds?

upd: sorry, it seems just last two round has easier G, but why?

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

-

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

Solved A in 2 minutes and given rest 118 min to the B, finding patterns in the smaller input. But, was not able to crack it. WTH!! happened to my brain. Ahh... this feeling can't be expressed in words.

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

    C and E where less complecated than B, but all 3 of them index fiddling.

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

      Once you get it the solution for B is not complicated.

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

        I know now, Many times it happened that small things don't strike during the contest. Let's hope today things will go a little smoother.

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

    same here bro b ruined it

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

Approach for D :
c = a*a-b & c = a*a+b*b
c*c = (a*a-b) * (a*a-b)
a*a + b*b = a^4 + b*b-2*a*a*b
On simplifying,
a*a=2*b+1
Now you can do a binary search for this.

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

Which formular we need to google or recite to solve D?

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

      I also did read this page...and then?

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

        $$$c+b=c^2-b^2\implies c-b=1\implies m^2+n^2-2mn=(m-n)^2=1\implies m=n+1$$$

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

          I did not liked the problem, but this explanational formular looks good, thanks!

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

            There should be some easier way to think but I've seen this formula before so I immediately think about this.

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
              Rev. 3   Vote: I like it +21 Vote: I do not like it
              1. $$$c^2 = a^2+b^2$$$

              2. $$$c=a^2-b$$$

              3. $$$(a^2 -b)^2 = a^2+b^2$$$

              4. $$$a^4+b^2-2a^2b = a^2+b^2$$$

              5. $$$a^2(a^2-2b)=a^2$$$

              6. $$$b = \frac{a^2-1}{2} \implies a \ is \ odd \implies a=2k+1\ for\ some\ k$$$

              7. $$$b = \frac{(2k+1)^2-1}{2} = 2k^2+2k = 2k(k+1)$$$

              8. $$$c = a^2 - b=(2k+1)^2-(2k^2+2k)=2k^2+2k+1 = 2k(k+1)+1$$$

              9. We already have $$$ a\le b\le c$$$ (easy enough to check that this is true for every k)

              10. Therefore, imposing $$$c \le n$$$ would suffice.

              11. $$$2k(k+1)+1 \le n \implies k(k+1) \le \lfloor\frac{n-1}{2}\rfloor$$$

              12. Therefore, $$$k \lt \sqrt{\lfloor\frac{n-1}{2}\rfloor}$$$

              13. You have your answer $$$\lfloor\sqrt{\lfloor\frac{n-1}{2}\rfloor}\rfloor$$$ (or 1 less than this quantity, has to be manually checked) in $$$O(1)$$$ :)

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

                sqrt operation is $$$\mathcal{O}(\log{}n)$$$ right?

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

                for n = 6 , answer will be 1 but from your formula root((6-1)/2) — 1 = 0 ...so can u clear this doubt ?

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

                I only reach upto value of b in 6th step, couldn't go further. Thanks for the explanation.

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

    The pythagorean formula, $$$a^2 + b^2 = c^2$$$, and the given formula in the problem, $$$c = a^2 - b$$$, are enough.

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

    Pythagorean Theorem: $$$a^2 + b^2 = c^2$$$. Then you couple that with $$$c = a^2 - b$$$ to solve for bounds on the variables. I thought it was strange they didn't include that in the problem statement, but I guess problemsetters deemed the theorem fundamental enough, since most people learn it in primary or secondary school.

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

      Well, I remembered pythagoras, the problem was more "to solve for bounds on the variables.".

      I assume that was in secondary school, too.

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

    c^2 = a^2 + b^2
    c^2 = a^4 + b^2 — 2*a^2*b
    a^4 — 2*a^2*b = a^2
    a^2 (a^2 — 2*b — 1) = 0
    b = (a^2 — 1)/2

    So the maximum value of n was 1e9 so the max value of a would-be sqrt(2*n + 1) would be the order of 1e5(let us call this N). We will maintain 2 arrays, pref[N] and num[N].

    Loop a from 1 to N and calculate b and c. If b and c are integers and c <= 1e9, put num[a] = c and pref[a]=pref[a-1] + 1. Otherwise num[a] = num[a-1] and pref[a]=pref[a-1].

    For each test case binary search on num and get the index ind such that num[ind] <= n and answer would be pref[ind]. I am leaving the edge cases to you.

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

    The answer is just (int(sqrt(2*n-1))-1)/2

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it
    Exclusive spoilers
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don't need a formula besides the ones provided. Just need to know how to substitute one equation into another and do some algebra.

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

Who else got memory limit exceeded in E?

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

    i used dijkstra for E and got MLE as well.

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

      That means our solution is correct it's just that we need to optimize storage.

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

Due to a typo, I somehow found that min(v.begin(), v.end()) compiles, but will probably give wrong answer. It took me so long to find the typo. Can someone explain why it compiles and the result of it?

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

    min function takes two arguments of same type and returns the minimum value of them. It uses "less than" operator to find the minimum. Here if v is a vector then "less than" operator is defined for vector iterator. So it works.

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

      Omg this should be quite obvious! I don't know why I didn't think about this. Thank you for the explanation!

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

E was so painful to solve!

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

Something is special with the number 1337. I see it everywhere :)

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

    It's leet written in leet the langage where you change letters to other character in order search for words doesn't work

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

Me whole time, during the contest.

Kudos to 6th consecutive negative delta

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

    Lol, Last 19sec saved you from much damage. Kudos for getting AC at 1:59:41.

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

I solved F using a simple Dijkstra. I have no proof why the number of states is small enough.

Can you hack it or prove its correctness?

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

    The entire state space your Dijkstra routine is exploring is of size $$$O((\log n)^2)$$$. Consider the number $$$x = 9*\mathrm{curr}$$$, written with no leading zero. Then your two operations on $$$\mathrm{curr}$$$, viewed as operations on $$$x$$$, are:

    1. invert every digit in $$$x$$$, or
    2. subtract 1 from the leading digit of $$$x$$$, then add 1 to $$$x$$$.

    Then it should be easy to see that from a given value of $$$x$$$, there are at most $$$2 \times 10$$$ values of $$$x$$$ that can be reached with the same number of digits, and at most $$$2$$$ values of $$$x$$$ with one digit less. These $$$2$$$ values will (up to inversion of digits) differ by either $$$9$$$ or $$$10$$$. Extending this idea, up to inversion of digits, the ways to remove the first $$$k$$$ leading digits of $$$x$$$ fit within a range of size $$$10k$$$. This leads to there being at most $$$20k+1$$$ of them, which leads to the $$$O((\log n)^2)$$$ bound I claimed.

    EDIT: I made a dumb oversight initially, but the idea of this comment should still more or less work. I expect the constant factor is in practice better than what my revised argument suggests, by about a factor of 5.

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

i was counting the pythagorus tripets where c=b+1 by the loop of pythagoras generator and it is giving TLE error any easier method ??

void pythagoreanTriplets(int limit) 
{ 
  
    // triplet: a^2 + b^2 = c^2 
    int a, b, c = 0; 
  
    // loop from 2 to max_limitit 
    int m = 2; 
  
    // Limiting c would limit 
    // all a, b and c 
    while (c < limit) { 
  
        // now loop on j from 1 to i-1 
        for (int n = 1; n < m; ++n) { 
  
            // Evaluate and print triplets using 
            // the relation between a, b and c 
            a = m * m - n * n; 
            b = 2 * m * n; 
            c = m * m + n * n; 
  
            if (c > limit) 
                break; 
  
            //printf("%d %d %d\n", a, b, c); 
            int d=max(a,b);
            if(c==d+1)
            ans++;
        } 
        m++; 
    } 
} 
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We have 2 equations. 1) c^2 = a^2 + b^2 2) c = a^2 — b

    If we substitute the value of c from 2nd eqn. to first eqn. we get,

    a^4 + b^2 — 2*a^2*b = a^2 + b^2 ==> a^4 — a^2 = 2*a^2*b (By rearranging terms) ==> b = (a^2-1)/2 ==> c = (a^2+1)/2 (By substituting the value of b into eqn.2)

    We can see that c>=b>=a. For c to be less than or equal to n, a<=sqrt(2*n-1). Also for b and c to be integers a should be an odd number != 1.

    So the answer is number of odd numbers from 3 to sqrt(2*n-1)

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

    Yes...use the same function to precompute the all the pairs till 10^9 and store a,b,c in different arrays let's say A,B,C..now for each n..check how many elements in C are <= n as because C will be holding the max element of each triplet of a,b,c. This is not the best method to solve this question but yes this approach works for given constraints.

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

Why does DFS by complement fail on E :(

submission

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

PatternForces

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

Deleted

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

how to solve C

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

    The main idea is we can put the teams on a circle. Then if $$$n$$$ is odd team $$$i$$$ won from teams $$$i+1,i+2,...i+\frac{n-1}{2}$$$(with cylic shift). And if $$$n$$$ is even team $$$i$$$ won from teams $$$i+1,i+2,...i+\frac{n-2}{2}$$$ and tie with team $$$i+\frac{n}{2}$$$.

    code

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

    Solution. You can fill adjacency matrix with checkerboard pattern (if $$$n$$$ is odd), mirrored by main diagonal. Then every line and every row has the same sum. In case $$$n$$$ is even -- every team must play one game in a tie. Simplest way to put 'tie values' on adjacency matrix such that any two 'tie values' are on the same row/column -- put them on second diagonal by checking the sum of indexes $$$row + col == n$$$. Bus you also need to mirror values by second diagonal (only in case of $$$n$$$ is even).

    Example or filled matrix (according to described pattern)
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks for your efforts

      but after giving 2.5hours+ still i am not comfortable that how this is working ..... i know this is a valid pattern but unable to answers whether i can think this on my own in or after contest..

      at the end ..... waiting for editorial.......

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

        Think of parity.

        if n is odd, then the total number of matches for a team is even. So each team can alternately win and lose.(no tie).

        if n is even, then the total number of matches for a team is odd. So you need to make the parity even by (tie one match for every team) and now every team can alternately win and lose.

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

    You can solve C by induction.

    Odd N Solution
    Even N Solution
    ODD N Example
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please, Can someone help me understand why below output(sequence) is wrong for Que C : Minimum Ties

when input is n = 4

my output(sequence): 1 -1 0 1 -1 0

I'm getting WA on testcase 2, my submission

Thank You!

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

    According to your output sequence, scores are not coming out to be same for all the teams (1->4,2->3,3->4,4->5). I think you are taking the score of match tied as 0.

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

      ohhh, yaa you're right!

      I got confused b/w point values and sequence values. :'(

      i was considering 1 point for winning and 0 for tie. btw, thanks! now i can sleep peacefully

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

    Your output doesn't make everyone's score same...that's the problem I guess..for n=4..correct output is 1 0 -1 1 0 1

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

Why this solution is not getting TLE?

Solution Link:https://codeforces.com/contest/1487/submission/107421373

Because the total number of times for loop is running = 22360*10000 ~ 2*10^8

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

    With O2 and Intel's good branch predictor, CF's judger isn't too slow

    So it isn't TLE

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

    Actually, it still passes without pragma optimize. 2*10^8 is small enough on codeforces when having small constant(you only do a few operations in the loop).

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

I solved

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

    The O(t*sqrt(n)) solution can be optimized to O(sqrt(n) + t*log(n)) if one precalculates all triples and for each test case does binary search

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

How do you solve E?

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

    You can build up the answer in bottom up manner.

    Step 1 : Try to find answer for all drinks , given that it can go well with a few desserts.

    Step 2 : Try to find answer for all courses of Type 2 , given that it can go well with a few drinks.

    Step 3 : Try to find answer for all courses of Type 1 , given that it can go well with a few courses of Type 2.

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

      I cannot view it.

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

        I tried giving spoilers , but I don't know what happened , nothing was displayed. Check it now.

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

I know math is very important in competitive programming. But isn't this too much?

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

Please, Can someone help me understand why below output(sequence) is wrong for Que C : Minimum Ties

when input is n = 4

my output(sequence): 0 1 -1 0 1 1

I'm getting WA on testcase 2:https://codeforces.com/contest/1487/submission/107460842

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

    YOUR OUTPUT : 0 1 -1 0 1 1
    That is
    1 2 — TIE
    1 3 — 1 WON
    1 4 — 4 WON
    2 3 — TIE
    2 4 — 2 WON
    3 4 — 3 WON
    Total Points:
    1 -> 3 + 1
    2 -> 3 + 1 + 1
    3 -> 3 + 1
    4 -> 3

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

    Your output sequence doesn't give the same score for each team. 1->4, 2->5, 3->4, 4->3.

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

the game may result in a tie, then both teams get 1 point.

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

    you made the same mistake like me.

    did you consider 1(or 3) point for winning and 0 for tie?, right?

    i also made the same mistake :'(

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

Editorial For Problem C is here :- https://www.youtube.com/watch?v=Kjj_BkRvYpQ

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

Joke problems in an edu — round . first 4 problems are joke.

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

In C, I was able to find the solution pretty quickly but for 1.5hrs could not find a way to implement the ordering. Anybody faced the same issue, and then i matched i with i + n/2 (for tie ) and brute forced rest of the pairs and it passed (maybe it will fail later) ... The ordering of win and loss for any pair

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

    I mean how to decide which pair will be loss , win or tie

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

      Here's what I thought while solving problem C:

      Consider each team as a vertex in a complete graph. Then you need to direct edges (outwards for a win, inwards for a loss) such that the in-degree and the out-degree are the same for any vertex $$$v$$$, and we need to maximize the number of directed edges. The maximum in-degree or outdegree can be at most $$$\lfloor\frac{n-1}{2}\rfloor$$$ (since there can be at most $$$n - 1$$$ edges incident on any vertex). A construction for this is pretty simple too: For any team $$$i$$$, let it win against teams $$$i+1, i+2, \ldots, i + \lfloor\frac{n-1}{2}\rfloor$$$, where indices are taken modulo $$$n$$$. The construction guarantees that you assign one pair of teams a win/loss at most once, and since there are incoming edges from $$$i-1, i-2, \ldots, i - \lfloor\frac{n-1}{2}\rfloor$$$ (indices taken mod $$$n$$$), the constraints are satisfied as well.

      To implement it, you can simply create a matrix $$$a$$$ where $$$a_{ij}$$$ is $$$1$$$ if there is an edge from $$$i$$$ to $$$j$$$, $$$0$$$ if it is undirected, and $$$-1$$$ if there is an edge from $$$j$$$ to $$$i$$$, and print in the order specified in the problem statement.

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

        nice way to think

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

        Then you need to direct edges (outwards for a win, inwards for a loss) such that the in-degree and the out-degree are the same for any vertex

        Couldn't you have a case, in theory, where one player has 3 draws, and another one has 1 win and 2 losses, with them having the same number of points?

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

          Let $$$T$$$ be the number of tied matches. Then in a state with everyone having the same score $$$S$$$,

          $$$(SumOfScores) = N * S = 2 * T + 3 * (N * (N — 1) / 2 — T) = 3 * N * (N — 1) / 2 — T$$$

          Middle equality is just summing up scores for each matches (2 for each tied matches, 3 for non-tied ones)

          Odd $N$ case is very obvious so I'll skip.

          If $$$N$$$ is even, after dividing both sides by $$$N/2$$$, we get

          $$$2∗S=3∗(N−1)−T/(N/2) \leftrightarrow T/(N/2)=2∗S−3∗(N−1)$$$

          This implies $T$ is divisible by $$$N/2$$$. Since the right hand side is odd, we can't have $$$T = 0$$$, so the smallest candidate of $$$T$$$ is $$$N/2$$$.

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

            This is exactly how I also solved(1st two lines of your comment). but for distributing the win/tie match I didn't thought of anything just did a brute force my_sub. I didn't prove why this way of distribution work

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

            What a nice proof!

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

        As arman.t mentioned, it's not immediately clear to me why each team needs to have the same number of wins and loses in any optimal configuration. In fact, this isn't true if we modify the number of points awarded for wins/ties/loses. For example, if winners get 2 points instead of 3 points (and everything else is the same), one optimal configuration of 4 teams with 3 total ties is as follows:

        	A	B	C	D	Total	Wins	Ties	Loses
        A	-	1	1	1	3	0	3	0
        B	1	-	2	0	3	1	1	1
        C	1	0	-	2	3	1	1	1
        D	1	2	0	-	3	1	1	1
        

        Edit: On second reading, maybe I misinterpret your comment. Are you saying that a team must have the same number of wins and loses although the number of wins of distinct teams can be different?

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

          Nice catch, I probably should have mentioned why the number of ties is minimized there. Note that if $$$x$$$ is the number of ties, the total number of points is $$$3n(n - 1)/2 - x$$$, and this needs to be divisible by $$$n$$$. If $$$n$$$ is odd, we're done by the construction since there $$$x=0$$$, and otherwise, the first expression is $$$n/2$$$ modulo $$$n$$$, so $$$x$$$ needs to be at least $$$n/2$$$, which the construction achieves. As for your observation, replacing $$$3$$$ with any odd number works, but might not work when we replace it by an even number.

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

      Same. After grueling effort, I found the pattern.

      At each iteration, the first team beats its adjacent(right) team, So you can start from 1 and then alternate with -1, 1,.. since the first team is beaten by its left team in the previous iteration.

      But that's not the case, at n / 2 th iteration, the first team needs to tie with its adjacent team, leaving the sequence at the next iteration starting from -1, 1,... instead of 1 since the first team is not beaten by its left team in the previous iteration rather tied.

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

    Simple way of ordering for odd value do this way.

    -LWLW

    W-LWL

    LW-LW

    WLW-L

    LWLW-

    For even do this way.

    -DLWLW

    D-WLWL

    WL-DLW

    LWD-WL

    WLWL-D

    LWLWD-

    alternate LWs only no complex logic as matrix is symmetric around the diagonal.

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

Educational round is too harsh.....I solved A and D but still getting a negative delta in pupil.....If it was a point based div2 I could surely have got some positive delta.....Though i am very upset with my low performance of not even being able to solve B and C today...

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

    This round was pure garbage (and I am speaking regardless of my poor performance). First four problems were all of same level. E and onward are of decent quality, but most participants didn't make it 'til that point, because of B/C fails.

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

      yaa!! you are right!!

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

      How they would do E if they can't do B/C? There is some examples of opposite, but there is few of them

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

        I never stated they would solve them, it's just that the first four problems provided no value whatsoever. When I can't solve a nice D2D, I spend a few hours analyzing it, but I don't regret missing today's B at all.

        E. g. I got stuck on B for an hour or so, then solved C and D in no time (messed up the +/- thing in D, but still solved 80% of the problem), does that mean that B was super hard or that I'm stupid, no? There were just too many simple tricky problems in today's round, that's all.

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

Totally speedforces. You should have excluded one of the problems from A-D, because 4 div. 3 problems on educational contest is very unacceptable There are pupils and even newbies getting negative delta for solving 4 problems, This does not happen even in div. 3 rounds.

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

    That's not true no pupil or newbie is getting negative for solving all 4. (even with absurd amount of penalty).

    agreed with the argument that problems were easier than your typical educational round but it's always like this.. some days the problems are balanced, some days they are tough and some days they happen to be lenient.

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

Can someone explain the logic of problem F? Is it digit dp? If yes then how you used it?

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

How to do B? I have no idea...

»
4 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Here is my 1 line code of problem-D ..xD

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

    thats dope maths

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

code Problem C

Can someone please explain why my code written in C11 got a TLE? T_T

I wonder if it got trapped in an infinite loop or the code is just too slow.

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

    You can test the code yourself with Custom Invocation, right? Your code runs that test 3 in around 1500ms.

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

      I got AC when I submit the same code in C++17.

      what's the diffrence between submiting in C and C++ ??

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

Thank you so much for the Hardwork of making this Contest.Really enjoyed and learned new things.

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

Is this contest unrated?

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

When is editorial coming??

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

A good contest for me. Finally solving A & B both in educational round. Feeling good

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

In problem C. For n = 4 according to my approach the output is 1 -1 -1 1 0 0 and the compiler output is 1 0 -1 1 0 1. My output was shown wrong because the score of 1 and 2 are not same. But I didn't see anything difference between (1 -1 -1 1 0 0 and 1 0 -1 1 0 1). Can anyone explain it please?

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

Can someone explain on how to solve problem E ?

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

    Sorry for my poor English.I will try my best to explain my idea. First,divide the original into three parts:the first with the second,the second with the third,the third with the fourth.Then let's solve the first part:the first kind food with the second.What we want to know is for every food in the second list,which food can be selected with it and cheapest.To do that,we can form a graph and use a map to store all the price of the first kind.Then just iterate every second food,and delete the food that cannot be selected with it in map.Finally,we can easily get which one is the cheapst or clarify there is no food can be selected with it.After this,add the elements deleted before and do again for the next second food.
    To calculate the real answer,we can add the selected price with the price for the second food.Then do this for the second food and the third.Finally,the price of the fourth food would be the answer.
    Here is my solution link:107496598

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

      Makes sense, but isnt the complexity quadratic ?

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

        This confused me a long time.But the fact is O(n + m) multiply the complexity for the map's cost.You can spilt the procession into "iterate all the edges" and "iterate all the points",these are indivisual parts.So its complexity doesnt overcome the limit.Very interesting part for me.

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

    Sorry for my poor English, but I want to give an another idea for this problem.

    So if we want to know the best choice of group $$$1$$$, we must know that for each element in group $$$1$$$ we can choose which element in group $$$2$$$ to minimize the cost.For group $$$2$$$,we should know the choice in group $$$3$$$, for group $$$3$$$,we should know the choice in group $$$4$$$.

    Now the problem is how to make the best choice for each group. For one element, we can think that the elements which can't go well with it make some block point in number axis. The block point spilt the whole number axis into some intervals. So we can use some data structure to query the mininum for each intervals. I used Sparse Table to solve it :https://codeforces.com/contest/1487/submission/107467664

    This solution works in the time of $$$O(n \log n)$$$, if you choose the segment tree,this solution would work in the same time.

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

is this round unrated?

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

COPS IIT-BHU, has prepared a set of video editorials for the problems A to E of this contest.
Do check them out by clicking at This.
Hope you like the explanation

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

![ ](150927496-2854209298185767-1672263672911909316-n)

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

When will the ratings be updated? Its almost 5 hrs the system testing has been done.

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

    I too waiting for rating updates

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

rating has been updated for this round

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

Does Educational rounds have editorials?

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

When will the editorials be published?

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

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

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

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