By awoo, history, 2 months ago, translation,

Hello Codeforces!

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:

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
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

• +158

 » 2 months ago, # | ← Rev. 3 →   -6 Thanks to awoo, Roms, adedalic, vovuh, BledDest and Neon for preparing the Div.2 contest.
 » 2 months ago, # | ← Rev. 2 →   +51 I wish this contest took place today. For single guys like me this could have been the perfect valentine :'(
•  » » 2 months ago, # ^ |   +28 But you are not thinking about singles who would have received negative delta.
•  » » » 2 months ago, # ^ |   +6 But he did not say that positive delta is a necessary condition for a contest to be the perfect valentine.
•  » » » » 2 months ago, # ^ |   0 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.
•  » » » » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   +21 What is the reason behind Educational round not having any testers?
•  » » 2 months ago, # ^ |   -15 Because it is an educational round. Hueueue BAAZINGAA!
•  » » 2 months ago, # ^ |   +25 hackers are testers :D
 » 2 months ago, # |   0 I hope that the conditions will also be short and clear as in the last round :)
•  » » 2 months ago, # ^ |   +4 statements :)
•  » » » 2 months ago, # ^ |   -6 sorry for bad english
 » 2 months ago, # |   +27 I will do a stream after the contest, on http://twitch.tv/AnandOza
•  » » 2 months ago, # ^ |   -15 Can you please shift to YouTube, you'll certainly get a larger watch base over there. Who watches coding videos on twitch anyways?
•  » » » 2 months ago, # ^ |   +3 Twitch is objectively better than YouTube for streaming
•  » » » » 2 months ago, # ^ |   0 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.
•  » » » » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   +12 I upload my broadcasts to YouTube later, and post screencasts on YouTube as well. Feel free to subscribe at http://www.youtube.com/c/AnandOza.
 » 2 months ago, # |   0 Can we expect short statements? It would be very pleasant to see short statements on the problems :)
•  » » 2 months ago, # ^ |   -15 Can we expect strong pretests? It wouldn't be very pleasant to see FSTforces. :) (FSTforces makes +136 for me) forgive my poor English:)
•  » » » 2 months ago, # ^ |   -6 What +136?
 » 2 months ago, # |   0 Just 1 day earlier and this contest might be my savior in the day that wasn't born for a single like me
•  » » 2 months ago, # ^ |   +1 A Valentine's Day date with codeforces. :)
 » 2 months ago, # |   0 I hope the contest will be on time without any delay
 » 2 months ago, # | ← Rev. 4 →   -28 delayed for 6 minutes to 6 hours :(
 » 2 months ago, # | ← Rev. 2 →   +14 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:
•  » » 2 months ago, # ^ |   +10 1379A - Акакий и строка is rated $1500$.
•  » » » 2 months ago, # ^ |   +2 I don't check all rounds. But still it was one of must difficult A in div 2
•  » » » 2 months ago, # ^ |   0 I have just done the virtual participation of this round, the problem A is quite hard which is almost the most difficult problem A of Div.2 I have ever seen!
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +1 Ok,But this Div2_A is 2000 rated
•  » » » » 2 months ago, # ^ |   +3 Less than 10% of success
 » 2 months ago, # | ← Rev. 2 →   +45 All I wanted from Mike:
•  » » 2 months ago, # ^ |   0 You want negative delta?
•  » » » 2 months ago, # ^ |   +6 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.
•  » » » » 2 months ago, # ^ |   0 Same feelings, bro.
 » 2 months ago, # |   0 Good luck for everyone! GLHF)
 » 2 months ago, # |   0 Is it not true that the round is Rated?
•  » » 2 months ago, # ^ |   0 no
•  » » 2 months ago, # ^ |   +7 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.
 » 2 months ago, # |   0 Тhe way to happiness is only through Educational Codeforces Round 104!
 » 2 months ago, # |   +9 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!!
•  » » 2 months ago, # ^ |   +4 welcome and good luck
•  » » 2 months ago, # ^ |   -13 huh, Nobody cares.
•  » » » 2 months ago, # ^ |   +5 You say that you don't, and yet you care enough to comment!
 » 2 months ago, # |   +8
 » 2 months ago, # |   +1 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.
•  » » 2 months ago, # ^ |   +1
•  » » » 2 months ago, # ^ |   0 Thanks
•  » » 2 months ago, # ^ |   +1 you can solve problems at http://cses.fi/
•  » » » 2 months ago, # ^ |   0 thanks
 » 2 months ago, # |   +8 Valentine’s Day is the programmer’s holiday.
 » 2 months ago, # |   +1 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
 » 2 months ago, # |   +3 those cyans who will be blue today will regret tomorrows div3
 » 2 months ago, # |   0 I haven't yet seen a comment with 69 downvotes. Hmm.. pretty disappointed.
 » 2 months ago, # |   0 do all questions have the same weightage?
 » 2 months ago, # |   +41 Is this TypeRacerForces?
 » 2 months ago, # |   +6 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?
•  » » 2 months ago, # ^ |   0 I think starting from E they look nice to me
•  » » » 2 months ago, # ^ |   -11 What? Did you even read E? It was easy, horrible and uninteresting.
•  » » » » 2 months ago, # ^ |   0 I think I am not able to solve it
•  » » 2 months ago, # ^ |   +9 Face reality: "Educational" means "to boring to be used in standard contest".
•  » » » 2 months ago, # ^ |   -8 nah bro educational means educational, "too boring" ain't educational.
 » 2 months ago, # |   +21 I think I burned my every brain cell solving C. Atleast I succeeded.
 » 2 months ago, # |   +3 How come (sqrt(2 * n + 1) — 1) / 2 isn't the solution in D?
•  » » 2 months ago, # ^ |   +6 2*n-1 not 2*n+1 :)
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +3 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^2a^4 = a^2 + 2ba^2a^4 = a^2(1 + 2b)=> a^2 = 1 + 2bb <= n => 2 * b <= 2 * n + 1I'm sorry again if I made some mistake, but please correct me in the place I am wrong.
•  » » » » 2 months ago, # ^ |   +19 c=b+1 so actually b<=n-1.
•  » » » » » 2 months ago, # ^ |   +6 Oh, I solved the system of equations wrongly, shame on me. Thanks for explanation.
•  » » » » 2 months ago, # ^ | ← Rev. 5 →   0 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 impossiblethe 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)$
•  » » » » » 2 months ago, # ^ |   0 You need to use dollar sign($) for inline Latex. •  » » 2 months ago, # ^ | +3 it is (sqrt(2*n-1)+1)/2-1  » 2 months ago, # | +70 I can't be the only one who found D easier than B? •  » » 2 months ago, # ^ | +11 And easier than C as well ... •  » » » 2 months ago, # ^ | +3 I had a very easy solution to C •  » » » » 2 months ago, # ^ | ← Rev. 2 → 0 share with us the concept •  » » 2 months ago, # ^ | 0 I just searched it on Wolfram Alpha •  » » » 2 months ago, # ^ | +1 link please •  » » » » 2 months ago, # ^ | 0 •  » » 2 months ago, # ^ | +4 Yeah for me D was easier than B and far easier than C. How did you guys solved C? •  » » » 2 months ago, # ^ | 0 I used cyclic permutation •  » » » 2 months ago, # ^ | ← Rev. 2 → 0 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 •  » » » » 2 months ago, # ^ | ← Rev. 2 → 0 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 •  » » » » » 2 months ago, # ^ | ← Rev. 2 → +1 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$ •  » » » » » » 2 months ago, # ^ | 0 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). •  » » » » » » 2 months ago, # ^ | 0 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. •  » » » 2 months ago, # ^ | 0 Greedy))) •  » » 2 months ago, # ^ | 0 I misread the statement of problem B :( And stuck on it for an hour...  » 2 months ago, # | 0 can anyone explain how to approach question d..like i am failing in the tc. •  » » 2 months ago, # ^ | ← Rev. 2 → 0 From the two formulas it follows that $c=b+1.$ Moreover, difference between $c$ and $c-1$ must be a square •  » » 2 months ago, # ^ | +2 It involves a bit of mathematics. So you have 2 equations 1) a^2 + b^2 = c^22) 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: http://cf.yanyanlongxia.cn/contest/1487/submission/107441210 •  » » 2 months ago, # ^ | +1 Pythagorus theorem -> a*a+b*b=c*c , a<=b<=cand eqn in question -> c=a*a-bsolving both equation we will get c = b+1so let b = m then c = m+1 and a = sqrt(2*m+1) since c<=nso m+1<=n => m<=n-1 => 2*m<=2*n-2 => 2*m+1<=2*n-1sqrt(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. •  » » 2 months ago, # ^ | ← Rev. 3 → 0 c=a2-ba2=c+b 3*3=9=4+55*5=25=11+127*7=49=24+259*9=81=41+40  » 2 months ago, # | +5 Anyone have a clue what test 18 of E is?  » 2 months ago, # | 0 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). •  » » 2 months ago, # ^ | +3 Wrong answer on test 1 doesn't give penalty •  » » » 2 months ago, # ^ | 0 Oh ok I didn't know that thanks!  » 2 months ago, # | 0 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? •  » » 2 months ago, # ^ | +8 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. •  » » 2 months ago, # ^ | 0 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. •  » » 2 months ago, # ^ | 0 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))  » 2 months ago, # | -16 •  » » 2 months ago, # ^ | +22 Does this really constitute searchable? Its literally just substituting and expanding the equation.  » 2 months ago, # | 0 Wrong answer on test 40 on E :( This is annoying  » 2 months ago, # | +6 The risk I took while submitting C was calculated but I forgot that I'm bad at math (-_-)  » 2 months ago, # | +43 [pE] What's the point of having 4 things. •  » » 2 months ago, # ^ | 0 Exactly :( •  » » 2 months ago, # ^ | +30 SpoilerI really like to have a good dinner with many dishes.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.  » 2 months ago, # | ← Rev. 4 → +11 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! •  » » 2 months ago, # ^ | +63 How do you know that pretests are strong? •  » » » 2 months ago, # ^ | +3 For example, the pretests of prblem C is absolutely strong. I bet. •  » » 2 months ago, # ^ | 0 How you solve E if you can tell the idea  » 2 months ago, # | +10 ParityForces •  » » 2 months ago, # ^ | +4 Yet another round like [some]forces  » 2 months ago, # | +17 This contest was not at all educational. •  » » 2 months ago, # ^ | 0 How? Please elaborate. I found the problems interesting. •  » » 2 months ago, # ^ | +133 It teaches you "educational rounds are not educational" XD •  » » 2 months ago, # ^ | 0 Educational contests teach you to hack other's codes. This is useful for debugging own code  » 2 months ago, # | +3 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  » 2 months ago, # | 0 Any ideas why this gives wrong answer in test 24 for E:107463591  » 2 months ago, # | 0 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? •  » » 2 months ago, # ^ | 0 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. •  » » » 2 months ago, # ^ | 0 Yeah I am saying the same thing. But isn't finding minimum will be O(n^2)? How are you optimizing it? •  » » » » 2 months ago, # ^ | +1 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 . •  » » 2 months ago, # ^ | +1 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. •  » » » 2 months ago, # ^ | 0 Ohh great!! Deleting the elements and then adding the same elements in the multiset, I haven't thought of. Thanks !!  » 2 months ago, # | +1 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) ?  » 2 months ago, # | 0 Thanks for the contest, even though I couldn't perform well, I got to learn a bunch of things!Kudos to the authors  » 2 months ago, # | 0 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? •  » » 2 months ago, # ^ | ← Rev. 2 → 0 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) •  » » 2 months ago, # ^ | 0 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.  » 2 months ago, # | +23 Getting input on E was harder then solving real problem •  » » 2 months ago, # ^ | +7 Success in E today depended on how fast you solve A,B,C,D. It was bit lengthy implementation due to large inputs. •  » » » 2 months ago, # ^ | +3 Solved B in 45 minutes lol •  » » » » 2 months ago, # ^ | 0 i expected i will take more time to solve, so went with C lol •  » » » 2 months ago, # ^ | 0 25 minutes to solve ABCD another 25 to solve E but why are F and G so difficult?! :( •  » » 2 months ago, # ^ | +1 Write macros/functions so that you can input common data formats without much typing.  » 2 months ago, # | ← Rev. 2 → 0 Why always easier G than F in edu rounds?upd: sorry, it seems just last two round has easier G, but why?  » 2 months ago, # | ← Rev. 4 → 0 -  » 2 months ago, # | +11 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. •  » » 2 months ago, # ^ | +1 C and E where less complecated than B, but all 3 of them index fiddling. •  » » » 2 months ago, # ^ | 0 Once you get it the solution for B is not complicated. •  » » » » 2 months ago, # ^ | 0 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. •  » » 2 months ago, # ^ | +1 same here bro b ruined it  » 2 months ago, # | ← Rev. 3 → +3 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.  » 2 months ago, # | 0 Which formular we need to google or recite to solve D? •  » » 2 months ago, # ^ | 0 •  » » » 2 months ago, # ^ | 0 I also did read this page...and then? •  » » » » 2 months ago, # ^ | +4 $c+b=c^2-b^2\implies c-b=1\implies m^2+n^2-2mn=(m-n)^2=1\implies m=n+1$ •  » » » » » 2 months ago, # ^ | 0 I did not liked the problem, but this explanational formular looks good, thanks! •  » » » » » » 2 months ago, # ^ | 0 There should be some easier way to think but I've seen this formula before so I immediately think about this. •  » » » » » » » 2 months ago, # ^ | ← Rev. 3 → +21 $c^2 = a^2+b^2$ $c=a^2-b$ $(a^2 -b)^2 = a^2+b^2$ $a^4+b^2-2a^2b = a^2+b^2$ $a^2(a^2-2b)=a^2$ $b = \frac{a^2-1}{2} \implies a \ is \ odd \implies a=2k+1\ for\ some\ k$ $b = \frac{(2k+1)^2-1}{2} = 2k^2+2k = 2k(k+1)$ $c = a^2 - b=(2k+1)^2-(2k^2+2k)=2k^2+2k+1 = 2k(k+1)+1$ We already have $a\le b\le c$ (easy enough to check that this is true for every k) Therefore, imposing $c \le n$ would suffice. $2k(k+1)+1 \le n \implies k(k+1) \le \lfloor\frac{n-1}{2}\rfloor$ Therefore, $k \lt \sqrt{\lfloor\frac{n-1}{2}\rfloor}$ 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)$ :) •  » » » » » » » » 2 months ago, # ^ | 0 sqrt operation is $\mathcal{O}(\log{}n)$ right? •  » » » » » » » » 2 months ago, # ^ | 0 for n = 6 , answer will be 1 but from your formula root((6-1)/2) — 1 = 0 ...so can u clear this doubt ? •  » » » » » » » » 2 months ago, # ^ | 0 I only reach upto value of b in 6th step, couldn't go further. Thanks for the explanation. •  » » 2 months ago, # ^ | 0 The pythagorean formula, $a^2 + b^2 = c^2$, and the given formula in the problem, $c = a^2 - b$, are enough. •  » » 2 months ago, # ^ | +3 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. •  » » » 2 months ago, # ^ | 0 Well, I remembered pythagoras, the problem was more "to solve for bounds on the variables.".I assume that was in secondary school, too. •  » » » » 2 months ago, # ^ | ← Rev. 2 → 0 It was for me ¯\_(ツ)_/¯ •  » » 2 months ago, # ^ | +1 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)/2So 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. •  » » 2 months ago, # ^ | 0 The answer is just (int(sqrt(2*n-1))-1)/2 •  » » 2 months ago, # ^ | +12 Exclusive spoilersFirst: By Brute-force, get the answer for $n$ in range $1...30$, in one line separated by a comma.Second: Copy the result, paste in OEIS and you will have this. Finally: Get the fake Accepted! :) •  » » 2 months ago, # ^ | 0 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.  » 2 months ago, # | +3 Who else got memory limit exceeded in E? •  » » 2 months ago, # ^ | 0 i used dijkstra for E and got MLE as well. •  » » » 2 months ago, # ^ | 0 That means our solution is correct it's just that we need to optimize storage.  » 2 months ago, # | 0 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? •  » » 2 months ago, # ^ | +9 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. •  » » » 2 months ago, # ^ | 0 Omg this should be quite obvious! I don't know why I didn't think about this. Thank you for the explanation!  » 2 months ago, # | +4 E was so painful to solve! •  » » 2 months ago, # ^ | 0 Same here...haha  » 2 months ago, # | +6 Something is special with the number 1337. I see it everywhere :) •  » » 2 months ago, # ^ | 0 It's leet written in leet the langage where you change letters to other character in order search for words doesn't work  » 2 months ago, # | +7 Me whole time, during the contest.Kudos to 6th consecutive negative delta •  » » 2 months ago, # ^ | +1 Lol, Last 19sec saved you from much damage. Kudos for getting AC at 1:59:41.  » 2 months ago, # | +14 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? •  » » 2 months ago, # ^ | ← Rev. 5 → +12 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: invert every digit in $x$, or 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.  » 2 months ago, # | 0 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++; } }  •  » » 2 months ago, # ^ | 0 We have 2 equations. 1) c^2 = a^2 + b^2 2) c = a^2 — bIf 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) •  » » 2 months ago, # ^ | 0 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.  » 2 months ago, # | 0 Why does DFS by complement fail on E :(submission  » 2 months ago, # | +7 PatternForces  » 2 months ago, # | ← Rev. 2 → 0 Deleted •  » » 2 months ago, # ^ | 0 atleast check if it is in contest time or not!  » 2 months ago, # | +7 how to solve C •  » » 2 months ago, # ^ | +7 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 •  » » » 2 months ago, # ^ | -8 Can anyone help me with C solution. I'm getting WA. Submission link :- http://cf.yanyanlongxia.cn/contest/1487/submission/107476877 •  » » 2 months ago, # ^ | ← Rev. 2 → 0 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) X -1 1 0 1 X 0 -1 -1 0 X 1 0 1 -1 X --- -1 1 0 0 -1 1 --------------- X -1 1 -1 1 1 X -1 1 -1 -1 1 X -1 1 1 -1 1 X -1 -1 1 -1 1 X --- -1 1 -1 1 -1 1 -1 -1 1 -1  •  » » » 2 months ago, # ^ | 0 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....... •  » » » » 2 months ago, # ^ | 0 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. •  » » 2 months ago, # ^ | ← Rev. 2 → 0 You can solve C by induction. Odd N SolutionFor any odd N we always have a solution , each team will play with N-1 (even) teams , so we can always allot equal number ow wins and losses to each team. Even N SolutionFor any even N , each team will play with N-1 (odd) teams. Clearly for equal points , we will have to tie atleast 1 game of each team. Hence , if there are N teams , we will have to tie atleast N/2 games.One such method could be ending the games between (1,2) , (3,4) , (5,6) , ... , (N-1 , N) in a tie. ODD N ExampleN = 5 , W = WIN L = LOSS XWLWL LXWLW WLXWL LWLXW WLWLX   » 2 months ago, # | 0 Please, Can someone help me understand why below output(sequence) is wrong for Que C : Minimum Ties when input is n = 4my output(sequence): 1 -1 0 1 -1 0 I'm getting WA on testcase 2, my submissionThank You! •  » » 2 months ago, # ^ | +1 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. •  » » » 2 months ago, # ^ | ← Rev. 2 → 0 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 •  » » 2 months ago, # ^ | 0 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  » 2 months ago, # | 0 Why this solution is not getting TLE?Because the total number of times for loop is running = 22360*10000 ~ 2*10^8 •  » » 2 months ago, # ^ | ← Rev. 2 → +2 With O2 and Intel's good branch predictor, CF's judger isn't too slowSo it isn't TLE •  » » 2 months ago, # ^ | 0 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).  » 2 months ago, # | ← Rev. 2 → -11 I solved •  » » 2 months ago, # ^ | ← Rev. 2 → +8 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  » 2 months ago, # | 0 How do you solve E? •  » » 2 months ago, # ^ | ← Rev. 4 → 0 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. •  » » » 2 months ago, # ^ | 0 I cannot view it. •  » » » » 2 months ago, # ^ | 0 I tried giving spoilers , but I don't know what happened , nothing was displayed. Check it now. •  » » » » » 2 months ago, # ^ | 0 SpoilerYou need to write inside spoiler tag!  » 2 months ago, # | +16 I know math is very important in competitive programming. But isn't this too much?  » 2 months ago, # | 0 Please, Can someone help me understand why below output(sequence) is wrong for Que C : Minimum Tieswhen input is n = 4my output(sequence): 0 1 -1 0 1 1 I'm getting WA on testcase 2:http://cf.yanyanlongxia.cn/contest/1487/submission/107460842 •  » » 2 months ago, # ^ | 0 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 •  » » » 2 months ago, # ^ | 0 thanks a lot bro :) •  » » 2 months ago, # ^ | 0 Your output sequence doesn't give the same score for each team. 1->4, 2->5, 3->4, 4->3. •  » » » 2 months ago, # ^ | 0 thanks a lot bro :)  » 2 months ago, # | ← Rev. 2 → -13 the game may result in a tie, then both teams get 1 point. •  » » 2 months ago, # ^ | ← Rev. 2 → +3 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 :'(  » 2 months ago, # | 0 Editorial For Problem C is here :- http://www.youtube.com/watch?v=Kjj_BkRvYpQ  » 2 months ago, # | +9  » 2 months ago, # | +26 Joke problems in an edu — round . first 4 problems are joke.  » 2 months ago, # | ← Rev. 2 → +6 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 •  » » 2 months ago, # ^ | 0 I mean how to decide which pair will be loss , win or tie •  » » » 2 months ago, # ^ | ← Rev. 2 → +16 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. •  » » » » 2 months ago, # ^ | 0 nice way to think •  » » » » 2 months ago, # ^ | +5 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? •  » » » » » 2 months ago, # ^ | +20 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$.
•  » » » » » » 2 months ago, # ^ |   0 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
•  » » » » » » 2 months ago, # ^ |   +8 What a nice proof!
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   +3 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?
•  » » » » » 2 months ago, # ^ |   +8 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.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » 2 months ago, # ^ |   0 Simple way of ordering for odd value do this way.-LWLWW-LWLLW-LWWLW-LLWLW-For even do this way.-DLWLWD-WLWLWL-DLWLWD-WLWLWL-DLWLWD-alternate LWs only no complex logic as matrix is symmetric around the diagonal.
 » 2 months ago, # |   +18 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...
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   0 yaa!! you are right!!
•  » » » 2 months ago, # ^ |   0 How they would do E if they can't do B/C? There is some examples of opposite, but there is few of them
•  » » » » 2 months ago, # ^ |   +14 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.
 » 2 months ago, # |   0 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.
•  » » 2 months ago, # ^ |   +17 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.
 » 2 months ago, # |   +3 Can someone explain the logic of problem F? Is it digit dp? If yes then how you used it?
•  » » 2 months ago, # ^ |   0 Yes, it seems to be digit DP
 » 2 months ago, # |   0 How to do B? I have no idea...
•  » » 2 months ago, # ^ |   0
 » 2 months ago, # |   -6 Here is my 1 line code of problem-D ..xD
•  » » 2 months ago, # ^ |   +3 thats dope maths
•  » » » 2 months ago, # ^ |   0 Explain-DObserve the simulation (n*n)-((n-1)*(n-1)) -----from here u alwz found......consecutive odd value-- 5*5-4*4=9(3*3) 6*6-5*5=11 7*7-6*6=13 ---------- ---------- ---------- 12*12-11*11=23 13*13-12*12=25(5*5) And then..... square odd value are the target value.We can do it O(1) complexity :D Code-Dcin>>n; p=sqrt(n*n-((n-1)*(n-1)); cout<<((p+1)/2)-1; 107489793
 » 2 months ago, # | ← Rev. 2 →   0 code Problem CCan someone please explain why my code written in C11 got a TLE? T_TI wonder if it got trapped in an infinite loop or the code is just too slow.
•  » » 2 months ago, # ^ |   0 You can test the code yourself with Custom Invocation, right? Your code runs that test 3 in around 1500ms.
•  » » » 2 months ago, # ^ |   0 I got AC when I submit the same code in C++17.what's the diffrence between submiting in C and C++ ??
 » 2 months ago, # |   +3 Thank you so much for the Hardwork of making this Contest.Really enjoyed and learned new things.
 » 2 months ago, # |   0 Is this contest unrated?
•  » » 2 months ago, # ^ |   0 no
•  » » » 2 months ago, # ^ |   0 I might cross 1600 based on this edu, will the div3 round be rated for me if I register now as the rating didn't change yet? or rated or unrated is decided based on the rating when the contest starts?
•  » » » » 2 months ago, # ^ |   0 No, I think
•  » » 2 months ago, # ^ |   0 When does the rating come out?
•  » » » 2 months ago, # ^ |   +7 Soon
 » 2 months ago, # |   +7 When is editorial coming??
 » 2 months ago, # |   +6 A good contest for me. Finally solving A & B both in educational round. Feeling good
 » 2 months ago, # |   0 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?
•  » » 2 months ago, # ^ |   0 The scores are not the same. Draw gives 1 point to both teams
•  » » » 2 months ago, # ^ |   0 Yes I got it now.
•  » » 2 months ago, # ^ |   +3 That's indeed wrong. Score distribution for each team(according to your output):3 - 8 - 5`
•  » » » 2 months ago, # ^ |   0 I got it. Thank you.
 » 2 months ago, # | ← Rev. 2 →   0 Can someone explain on how to solve problem E ?
•  » » 2 months ago, # ^ |   +8 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
•  » » » 2 months ago, # ^ |   +3 Makes sense, but isnt the complexity quadratic ?
•  » » » » 2 months ago, # ^ |   0 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.
•  » » 2 months ago, # ^ |   +1 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 :http://cf.yanyanlongxia.cn/contest/1487/submission/107467664This solution works in the time of $O(n \log n)$, if you choose the segment tree，this solution would work in the same time.
•  » » » 2 months ago, # ^ |   +3 I think it might be O(n + mlogn) for each one
•  » » » » 2 months ago, # ^ |   0 Sorry u r right(((
 » 2 months ago, # |   0 is this round unrated?
•  » » 2 months ago, # ^ |   0 no rating change
 » 2 months ago, # |   +9 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
 » 2 months ago, # |   +21 ![ ]()
 » 2 months ago, # |   +8 When will the ratings be updated? Its almost 5 hrs the system testing has been done.
•  » » 2 months ago, # ^ |   0 I too waiting for rating updates
 » 2 months ago, # |   0 rating has been updated for this round
 » 2 months ago, # |   0 Does Educational rounds have editorials?
•  » » 2 months ago, # ^ |   0 Yes.
 » 2 months ago, # |   +3 When will the editorials be published?
 » 2 months ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 2 months ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).