By pikmike, history, 5 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 Ne0n25 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:

Hey Codeforces!

As you may remember, we have a free webinar series starring our all-star faculty members who share valuable content and insiders’ knowledge that you don’t get to learn about in traditional classrooms.

Join us tomorrow, Thursday, May 28 at 12h (BCN) / 17h (BKK) to watch Sergey Gordeychik, CIO of the Inception Institute of Artificial Intelligence, share his expertise and insights in his “Digital Lockdown: AI against COVID-19” session. Sergey will discuss how AI is being used both positively and negatively during the COVID-19 global pandemic. Tune in for some practical examples of how companies are using AI to innovate and disrupt during a time of crisis, exploring topics like Medical Imaging for CT analysis, diagnosis and mass surveillance.

By participating in this webinar you will get a certificate of participation, a special digital gift from Sergey, and stand a chance to win a FREE 3-week module at Harbour.Space University depending on the availability and prerequisites of the course.

See you tomorrow, and good luck on your round!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 kefaa2 6 174
2 bmerry 6 219
3 dlalswp25 6 233
4 hepth 6 238
5 Volkov_Ivan 6 251

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Hideki_Ryuga_L 37
2 KonaeAkira 19:-1
3 ujjwalsingh30 18:-1
4 veteran_ 14
5 hashlib 13
318 successful hacks and 469 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A andryusha_na_knopke 0:01
B thech0sen1 0:03
C IAKWF 0:11
D Kerim.K 0:06
E HeHere 0:06
F user202729_ 0:44

UPD: Editorial is out

• +355

 » 5 months ago, # | ← Rev. 2 →   +33 First comment! Thank you Codeforces and Harbour.Space University for these rounds in this tough time!
•  » » 5 months ago, # ^ |   +122 Don't know the reason of such hatred shown by the community here. I just thanked the organizing panel for their efforts, that's it, as a good gesture. No wonder why the community hated it so much. Maybe because I am a specialist and not a red, not really sure about it.
•  » » » 5 months ago, # ^ |   +18 Don't worry about downvotes too much. Your positivity will reach the people no matter what.
•  » » » 5 months ago, # ^ |   +10 This is one big problem with cf. On one side, there is Mike who is bringing out new div4 contests for not so high rated participants and on other side are these guys who boast a lot about their ratings.
•  » » » 5 months ago, # ^ |   +74 If everyone showed thanked the organizer in the comments, then we'd just have a thread of 19,000 people saying thank you. No one wants that, if you want to thank them give them an upvote.
•  » » » » 5 months ago, # ^ |   +2 Almost everyone is sad about this lock down (including me), and if these contests give hope to people or put a smile on their face or excite them, there's no harm in saying a "thank you" as a good gesture. And I think that it's nearly impossible for such a large number of people to post it in an announcement. It's just a few, which doesn't flood these announcements. In my case, I just got excited seeing the announcement and that there isn't any comment yet, so I thought why not write a good thing for the organizers, there's nothing bad in it. It gives hope (or just puts a smile) to some, if not all.I don't want to hurt anyone with my comments, and if I did, I am sorry about it.
•  » » » » » 5 months ago, # ^ |   0 Hey, don't worry both of the groups supporting/disagreeing with your comment are right in their point of view. The first group that supported you was for your pleasant thanksgiving and the other group that disagreed on you was because they want that more important messages/helpful messages are to be shown so that it would give way to more important messages in a bunch of good messages. That thanksgiving gesture was very pleasant hope it will spread positivity in this environment.
•  » » » 5 months ago, # ^ |   +4 I guess you've been downvoted for your 'First comment'. That's totally useless.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Codeforces community is weird. On one hand, it is made up of brilliant and creative people, but on the other hand you most of the codeforces community being receptive of people who show courtesy. It must be a nightmare to have these people in your team at work!
 » 5 months ago, # |   +59 Where's the unusual time ??
•  » » 5 months ago, # ^ |   +167 It's unusual that it's not unusual.
•  » » 5 months ago, # ^ |   +83 Whoops, you saw nothing
•  » » » 5 months ago, # ^ |   +6 Nice ...
•  » » » 5 months ago, # ^ |   +26 Your rating curve is inspiration to many
•  » » » » 5 months ago, # ^ |   +4 I like to watch other people's rating graph when cf predictor says mine is going to be -50
•  » » 5 months ago, # ^ |   0 Well it's still unusual for some people!
•  » » » 5 months ago, # ^ |   0 But this is the standard time of CodeForces
•  » » » » 5 months ago, # ^ |   0 Yeah I know, "standard unusual time" for us.
 » 5 months ago, # |   -141 GoogleforcesLet's goooo!
•  » » 5 months ago, # ^ |   +22 Rude
 » 5 months ago, # |   +8 Hope this educational round will be much better than previous one^_^
 » 5 months ago, # | ← Rev. 3 →   -66 Looking forward to more geometry problems! Especially, ones with subtasks <3
•  » » 5 months ago, # ^ |   -12 Me too.
 » 5 months ago, # |   +24 Lets hope we get to see problems involving both math and graph theory. It was long back when we had problems involving math as well as graph theory.
•  » » 5 months ago, # ^ |   +7 Let's hope your dream never comes true
 » 5 months ago, # |   0 Thanks for having back to back contests! Giving something to cheer for.
 » 5 months ago, # |   +33 Looking for a data structures problem ..
 » 5 months ago, # |   +2 I rarely see a Div2C or Div2D a graph theory problem I think in a while i have seen two only one livonia and kingdom and one from ehab and bla bla .... I am looking for good Problems rather than standard ones with unusual time limit and memory limit.
 » 5 months ago, # | ← Rev. 2 →   +51 I hope to see Tree , Data structure , Math Problem But i don't want to see geometry .... i am very weak of that
•  » » 5 months ago, # ^ |   +7 everything is fair until it's not one click away on google. specially when it's prob A/B/C/D. because that makes contest unfair for 80% rated participants.
•  » » » 5 months ago, # ^ |   +44 How did you calculate the percentage of the unfairness? Why not 0.4% or 5% or 15% or 146%? Please, provide some proof or stop speculating.Anyway, if you deserve your rating you'll gain it in no time. Otherwise, if you need to google A/B/C/D in ER you probably don't have the rating you can be proud of.
•  » » » » 5 months ago, # ^ |   0 Btw how did you generate such numbers .4%,5%,15%,146%. Any formulas for that or random. He is saying correct those who wasted time in solving that suffered. Googlers got Ac instantly. At least it should be not present on google
 » 5 months ago, # | ← Rev. 2 →   -35 Educational codeforces round exists * No one : Literally no one : People who get negative delta after the contest : Educational codeforces rounds should be unrated.
•  » » 5 months ago, # ^ | ← Rev. 3 →   +37 I enjoy every contest even if I get negative delta. I don't know why people complain a lot with the rating! Everyone should enjoy contest even if you get negative or possitive delta! I think that's the authors purpose and what really matters!
•  » » » 5 months ago, # ^ |   +11 Yes, even if there would be no rating system i would have given same or more number of contests. Its the number of questions i do make me feel good than positive or negative delta .
•  » » » 5 months ago, # ^ |   -9
 » 5 months ago, # |   0 Why score distribution is not given in any educational round announcements?
•  » » 5 months ago, # ^ |   +41 Because all problem has equal score in educational rounds.
 » 5 months ago, # |   +17 RUSH RUSH！！
 » 5 months ago, # | ← Rev. 3 →   -86 [deleted]
•  » » 5 months ago, # ^ | ← Rev. 2 →   +58 More than 3 years and you're still a newbie. It's your fault, not due to the statement
•  » » » 5 months ago, # ^ |   0 I never wrote that I have lower ratings due to the problem statements. I just gave an opinion what I felt and that's it.
•  » » » » 5 months ago, # ^ |   +7 I think the best solution is just practice because reading is also an important skill
 » 5 months ago, # |   -10 Who else is trying to solve their first div2 c problem
•  » » 5 months ago, # ^ |   +4 Not the first. But it's been a while since I solved my last C >.>
 » 5 months ago, # | ← Rev. 2 →   -47 Problem C : This Problem Can be Solved Mathematically using inequalities. Idea First we have to understand that whenever hot cup = cold cup = k, we have temp of barrel = (h+c)/(2). If hot cup != cold cup then let the no. of hot cups = n, therefore no. of cold cups = n-1 (As we started pouring from hot cup). So, after n hot cup and n-1 cold cup the temperature of barrel = (n*h + (n-1)*c) / (n+n-1). Solution We have f(n) = (n*h + (n-1)*c) / (2*n-1) , where n = no. of hot cup. This is a decreasing function and also bounded below by (h+c)/2 (As we increase n, denominator increases more rapidly as compared to numerator and also as n->inf , f(n)->(h+c)/2 or we can check using derivatives also) . Now, if given t <= (h+c)/2 it is optimal to only pour one hot and one cold cup. So answer in this case is 2.(as our function cannot reach below or at (h+c)/2) . And, if t>(h+c)/2 , we can find smallest n for which function takes value <= t using the t >= (n*h + (n-1)*c) / (2*n-1) which gives n >= (t-c) / (2*t-h-c) . We will check difference from t for this n (remember hot cups) and n-1 will be therefore cold cups (why?) and for n-1 (hot cups because it will give the lowest value of function >= t ) and answer will be the 2 * ( one which will give minimum difference ) — 1 . Link to my solution : 81821029
 » 5 months ago, # |   0 Woohooo Vovuh is back!
 » 5 months ago, # |   +32 Hope there are no geometry problems!
 » 5 months ago, # | ← Rev. 3 →   -24 sry, I LOVE MATH!
•  » » 5 months ago, # ^ |   +24 I love math...! :) Happy coding...
•  » » » 5 months ago, # ^ |   0 I guess should have enjoyed solving C question then?It was just an inequality question.
 » 5 months ago, # |   +62
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 humblefoolboi bhaiya please tell why if we choose n/i in our array elements in our array then given expression in problem E will not change if we permute array element... please........
 » 5 months ago, # |   +9 why has no one yet asked whether the round is rated or not!!
•  » » 5 months ago, # ^ |   -8 It is already written in bold, rated for participants with rating lower than 2100
•  » » » 5 months ago, # ^ |   +5 me .... literally after every "is it rated "comment in every contest
•  » » 5 months ago, # ^ |   -12 I feel like it's my first contest even if it's my 85th contest. Can you please tell me if the contest is rated or not. XD
•  » » » 5 months ago, # ^ |   +3 pretty clever username dude.
 » 5 months ago, # | ← Rev. 3 →   -8 Hey Guys! You have never upvoted me, so may you just wish me well to get cyan?! Thanks the guys who upvoted XD
 » 5 months ago, # |   -133 I give up Codeforces and leave this site because of problem C. I am 100% sure that my code is correct but I got 7 WA. I give up. Bye.
•  » » 5 months ago, # ^ |   +52 If you got WA then maybe, just maybe, it is not 100% correct..
•  » » 5 months ago, # ^ |   -14 You could instead try E which is easier than C
•  » » » 5 months ago, # ^ |   0 i place my trust on Ross over Chandler
•  » » » » 5 months ago, # ^ |   +3 just make sure he is not on break lol
•  » » » 5 months ago, # ^ |   +1 If only i knew it...
•  » » 5 months ago, # ^ |   +17 I passed pretests on second attempt. Its a pen and paper problem. Looked like binary search first, but its O(1) solution with some messy algebra, theory of increasing/decreasing functions, case work, simplifying fractions.
•  » » » 5 months ago, # ^ |   +3 Actually, C can be solved using binary search, I used it during the contest.You can see my solution for the same -> https://codeforces.com/contest/1359/submission/81760272
•  » » » 5 months ago, # ^ |   +3 Yes.. Very nice observation that it can be solved in O(1) using some mathematics. I just solved it after looking at your comment and turns out, we don't need any fancy mathematics. Just simple algebra works. After that just check at values (x-1), x, and (x+1)https://codeforces.com/contest/1359/submission/81874188
•  » » » » 5 months ago, # ^ |   0 thank's , but letters not understandplease explain more
•  » » » » » 5 months ago, # ^ |   +1 check this video for detail explanation C problem https://youtu.be/Ts6to-_N-Y0
•  » » 5 months ago, # ^ |   +6 I figured out that expected precision = 1e-15, I got it accepted when i incurred that change
•  » » 5 months ago, # ^ |   +10 I tried to read your code and saw this: 81775456. No pity you leave, since you would be banned for intentional code disguise anyway.
•  » » 5 months ago, # ^ |   +5 what with your weird way of writing code. it's like cancer, you write code using define.
•  » » 5 months ago, # ^ |   +10 I've never laughed so much looking at code (except maybe ArnoldC). Now I have.
 » 5 months ago, # |   -30 1937 : There will be flying cars in 2020Meanwhile in 2020 : brainless pupils and Newbies exist.
•  » » 5 months ago, # ^ |   +2 Please change your profile picture, it irritates me every time I see it.
•  » » 5 months ago, # ^ |   +5 For fuck's sake, change the dp otherwise don't comment!
•  » » 5 months ago, # ^ |   +11 Codeforces should introduce report feature.
 » 5 months ago, # |   +11 Speedforces!
 » 5 months ago, # |   +24 Last time I was lucky to notice the pattern in C task which resulted in formula answer, this time C revenged! :D
 » 5 months ago, # |   0
 » 5 months ago, # | ← Rev. 2 →   0 A great contest with beautiful problems and short statements for which Educational rounds are generally known.
 » 5 months ago, # |   +3 Can C be solved with the help of binary search ? If yes, how ??
•  » » 5 months ago, # ^ |   +23 For even number of cups, the resulting temperature is always the same.For odd number of cups, the resulting temperature decreases as we add new cups, but never becomes less than or equal to $\frac{h + c}{2}$. So if $t > \frac{h + c}{2}$, we can use binary search to find the first moment it becomes less than $t$, and check this moment and the moment $2$ cups before.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +6 Okay so i was doing everything right but failed to realize that i need to use binary search only for t>(h+c)/2. Changed that and accepted. Thanks !
•  » » » » 5 months ago, # ^ |   0 Or we can use section formula and solve some equations.. Geometry :)
•  » » » 5 months ago, # ^ |   +12 I suppose I have a constant time solution.
•  » » » » 5 months ago, # ^ |   0 You are not alone.
•  » » » » » 5 months ago, # ^ |   0 of course man..Its basic math and error analysis
•  » » » » 5 months ago, # ^ |   0 just saw your solution, can you explain why exactly: lli i = (h-c)/(2*eff); double boo = (h-c)/(2.0*eff); 
•  » » » » » 5 months ago, # ^ |   +3 boo is the value so that the error is absolutely 0.. i is the floor of boo
•  » » » 5 months ago, # ^ |   0 Here is the solution based on this https://codeforces.com/contest/1359/submission/81819508
•  » » » 5 months ago, # ^ |   0 Please correct me if I'm wrong, but consider $h=10$ and $c=1000000$Wouldn't the average temperature for odd cups be strictly increasing in this case?
•  » » » » 5 months ago, # ^ |   0 In the statement, it says: "1≤c
•  » » » » » 5 months ago, # ^ |   0 Oh, thank you!
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Considering the case 999977 17 499998, where hot temperature is 999977 and cold temperature is 17, target being 499998. Using 499979 pours, and, while using 499981 pours, we get the same difference with the target.So shouldn't the answer be 499979. While in the solution, the answer is 499981. Can anyone let me know what I am missing here?
•  » » » » 5 months ago, # ^ |   0 Try reading other comments. Comment
•  » » 5 months ago, # ^ |   +11 If we consider the case where we have $X + 1$ hot and $X$ cold, the temperature is a decreasing function, so binary search could work here. However you can also directly calculate the value of $X$ for which the intersection occurs and then check $\lfloor X \rfloor$ and $\lceil X \rceil$ for whichever gives a closer temperature.
•  » » » 5 months ago, # ^ |   0 Yes I did the same way by directly calculating the intersection value.
•  » » » 5 months ago, # ^ |   0 Can $\lfloor X \rfloor$ and $\lceil X \rceil$ and then temperatures at these points be calculated with good precision ?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 You do not need to calculate them as double, you can calculate as integers directly: either [t / (h + c + 1 — 2 * t)] or 1 + [t / (h + c + 1 — 2 * t)] where / is integer division. even if X is an integer, it would not hurt to calculate temperature difference at X + 1
•  » » » » » 5 months ago, # ^ |   0 Yeah, did the same when I finally got an AC
•  » » » » » 5 months ago, # ^ |   0 How did you get this formula? As far as I know, it should be [(h-t)/(h+c-2t)]
•  » » » » » » 5 months ago, # ^ |   0 no .,..yr formula will generate a negative value..which is quit absurd....in the numerator ,it will be(t-h)..so that both numerator and denominator are negative ...making a positive quantity...u can get it by simply equating t
•  » » » » 5 months ago, # ^ |   +1 I used double division followed by floor and passed fine. However you can calculate it exactly using integer division.
•  » » » » » 5 months ago, # ^ |   0 How did you derive the formula?
•  » » » » » » 5 months ago, # ^ |   0 First wlog let $c = 0$. Let $x$ be the number of cold cups. Then for the odd case we want $h(x+1)/(2x+1) = t$. This intersection point only exists if $t/h >1/2$. Otherwise we take an even number of hot and cold cups. Now just check if the floor or ceil of $x$ gives a closer answer.
•  » » » » » » 5 months ago, # ^ |   0 I did the same and used section formula to get this result.
•  » » » » » 5 months ago, # ^ |   0 I did the same. I think I am having precision issues. Help please. https://codeforces.com/contest/1359/submission/81752804
•  » » » 5 months ago, # ^ |   0 I did the same but still got WA in the third case can somebody tell why? My submission for C- 81790933
•  » » » » 5 months ago, # ^ |   0 same problem subcase 66 (getting 2 instead of 1).
•  » » » » 5 months ago, # ^ |   0 You have most probably missed out on cases where the the difference between h and t is the smallest possible difference and therefore 1 should be the output. Tc: 1 7 1 6 Your code fails for this and other similar test cases the answer should be 1 and not 3.
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   0 1 10 4 9 here expected 1 found 3.
•  » » » » » 5 months ago, # ^ |   0 Seems I forgot to exclude equal case here 1 and 3 both have difference 1 but minimum was to be considered. Thanks
•  » » 5 months ago, # ^ |   +1 Yes. Notice that the more cups you take (assuming it's an odd number), the closer you will be to the average of hot and cold temperatures. Use this fact to binary-search for the smallest number of cups such that the temperature is not more than the target. To deal with any precision issues, check 2-3 numbers above and below what you found and select the best one.
•  » » 5 months ago, # ^ |   +3 Yes. I solved it with Binary Search. However, my first few submissions for C got WA because of Double precision issues! If this hadn't happened, I would have reached master. :(Check out my submission here: 81789311
•  » » » 5 months ago, # ^ |   0 LOL The rating predictor was wrong, you reached master :v
 » 5 months ago, # |   +4 What is the testcase #4 of problem C ?
•  » » 5 months ago, # ^ |   +6 I just changed double to long double and it worked.
•  » » » 5 months ago, # ^ |   0 Do you know what is the solution in Python for this issue? Submission failed on Test case 4I am failing on the test case 999977 17 499998I tried using the 'Decimal' module in Python for more precision. But, I am still getting an error.
•  » » » » 5 months ago, # ^ |   0 The Fraction class, fractions.Fraction worked for me (https://codeforces.com/contest/1359/submission/81820143) but only after the contest.
•  » » 5 months ago, # ^ |   0 Testcase #4 of problem C is some testcase which causes Double precision issues to cause WA>
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -10 Yes, Fu**ing precision error in python got me that answer wrong and that question sucked soul out of me.
•  » » » » 5 months ago, # ^ |   -10 Yes, it sucked the soul out of my rating :(I would have finished around rank 100 if I had solved C immediately without any errors...but instead I got 347 :(
•  » » » » 5 months ago, # ^ |   +2 Can relate. I wasn't able to overcome the precision error until after the time was over. :(
•  » » » » 5 months ago, # ^ |   0 Yes, same problem. Discovered after the contest that the easiest way round this is to use the Python Fraction class (fractions.Fraction), see https://codeforces.com/contest/1359/submission/81820143. I wasn't aware of this class before, so I actually learnt something from this "Educational" round!Not sure what one would do in other languages.
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 I was getting TLE on this test, so I think there is some stress-tests, for example:30000999999 2 500001999997 2 500000...and more
 » 5 months ago, # |   +4 How to solve D?
•  » » 5 months ago, # ^ | ← Rev. 3 →   +17 for each element in array .. assume the current element as maximum for segment under consideration.then find max_left_sum[i] and max_right_sum[i] (crucial part).ans will be max(all(max_left_sum[i] + max_right_sum[i]))can be done in O(N). once try for yourself, anything more i explained will be a spoiler. Spoileri will show how to compute the max_left_sum array you can figure out the construction of max_right_sum array from this.there are two for loops used. although you can do it single loop.in the first for loop we are calculating for each number in the given array the maximum we can get until we reached some x >= current element.In the second loop we are using the computation done some x in the left portion x == current element.(this step is to ensure that we achieve the O(N) complexity).Once go through the code with an example you will get it. left[n] = {0,0,0,0,...} a is input array for(i from 0 to n){ int j = i-1 , here = 0 , maxi = 0; while(j>=0 && a[j] < a[i]){ here += a[j]; maxi = max(maxi , here); j--; } left[i] = maxi; } for(i from 0 to n){ int j = i-1,sum = 0; while(j>=0 && a[j] <= a[i]){ sum +=a[j]; if(a[j] == a[i]){ left[i] = max(sum+ left[j] , left[i]); break; } j--; } } this is another question which can be solved using similar technique — Largest Rectangle from Hackerrank
•  » » » 5 months ago, # ^ |   +42 I overkilled D using 3 Segment Trees, that ultimately did exactly what you said...
•  » » » 5 months ago, # ^ |   0 Are you using Kandanes algorithm both side ? Can you please tell your solution since what you left is the hardest part . Your can put it as a spoiler .
•  » » » » 5 months ago, # ^ |   0 I have updated the comment with spoiler section(with explanation and code) and a bonus similar problem.
•  » » » 5 months ago, # ^ |   0 Is the complexicity of for loop is n*m where m is no of different value that array element can take m=60 in this case..
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Note that there is no need to check the negative values, since if the biggest value of the subarray is negative, it is better to use a single element subarray which results in sum of 0.
•  » » » 5 months ago, # ^ |   0 Yupp, that largest rectangle problem uses stack to get the next and previous greatest elements. I find stacks tricky hence used segment tree + binary search to find the next, prev greatest element
•  » » » 5 months ago, # ^ |   +3 for a decreasing array, the complexity is O(n^2) in the first loop itself. This code will get TLE. right?? Or, please explain why the complexity should be O(n).
•  » » » » 5 months ago, # ^ |   0 there is the condition for input -30<=ai<=30.this is useful to maintain O(N) if the diversity increases this algorithm reached O(N^2) as you said.
•  » » » » » 5 months ago, # ^ |   0 Thnks, got it, first i thought your solution will work for greater values of a[i] too.
•  » » » 5 months ago, # ^ |   0 Thank you so much man.The bonus question really helped me.
•  » » 5 months ago, # ^ |   0 I used same logic of Mike and Feet
•  » » 5 months ago, # ^ |   +8 Can we use stacks to solve this problem??
•  » » 5 months ago, # ^ |   0 You can also use DP with dp[i][j] := "maximum sum of subarray a[?:i] with max value j" which has pretty trivial transitions, and then maximize dp[i][j]-j, looks like this: 81795283
 » 5 months ago, # |   0 How to solve F?
•  » » 5 months ago, # ^ |   +26 My idea:Forget about starting at any time for a moment. Let all cars start moving at $t = 0$. For any $t$, Consider the line segments of each car whose endpoints are starting position of that car and position of that car at time $t$. Find the least $t$ for which there is an intersection of any two line segments. Then the answer is $t$, because if line segments corresponding to cars $A$ and $B$ intersect, then I can start one of them late and make them crash exactly at $t$. So binary search on $t$ and use line sweep to check if there is any intersection.
 » 5 months ago, # | ← Rev. 2 →   0 I solved C using ternary search . can some one please proof how the shape will be similar to parabola (I just assumed) .
•  » » 5 months ago, # ^ |   +6 You can use just Binary Search in the odd number of movements.
•  » » » 5 months ago, # ^ |   0 Can you plz tell me how? . I am able to find out that we need to search only in odd position but didnt find the how to solve it as brute gives tle and you said binary search . But I didnt get it how??
•  » » » » 5 months ago, # ^ |   +3 take one cup of the hot water and pour it into an infinitely deep barrel; take one cup of the cold water and pour it into an infinitely deep barrel; take one cup of the hot water and pour it into an infinitely deep barrel; take one cup of the cold water and pour it into an infinitely deep barrel; and so on... Here for every cup of cold water you have already poured a cup of hot water already. So whenever the even number of cups poured, the temperature will be constant which is the avg(h, c). After you pour the 1st cup of hot water. The temperature will be h. After you pour the 2nd cup of hot water. The temperature will be slightly low since you have poured one cup of cold water before.Therefore, the temperature will be decreasing monotonically towards the avg(h, c) when ever you pour a cup of hot water. So you can use this property to binary search the appropriate value.Link to my submission : 81771518 . Hope you find this useful
•  » » 5 months ago, # ^ |   0 No the shape would not be parabolic.
•  » » » 5 months ago, # ^ |   0 I meant convex or concave.
•  » » 5 months ago, # ^ |   +22 Assume you put x hot cups and x — 1 cold cups. Then middle temperature is (xh + (x-1)c) / (2x-1) If you put x + 1 hot cups and x cold cups then middle temperature is ((x+1)h + xc) / (2x + 1).Subtract second from first and you get (h-c)/(4x^2 — 1) which is always positive. So temperature is strictly descending function from number of hot cups.
•  » » 5 months ago, # ^ |   +32 I can be proved that $\frac {x} {2 * x - 1}$ (x = 1, 2, ...) is decreasiong.Proof:$2x^2 + x > 2x^2 + x - 1 $$x *(2x + 1) > (2x - 1) * (x + 1)$$ \frac{x}{2x-1} > \frac{x + 1}{2(x + 1)-1}$
•  » » 5 months ago, # ^ |   0 I just plotted the graph, and you can see it is a decreasing function for odd number of cups. and you can see it is constant for even number of cups.
 » 5 months ago, # |   +47 The ordering of problems was very bad E was even easy from C
•  » » 5 months ago, # ^ |   +13 I think it was easy to guess but not easy to prove .
•  » » » 5 months ago, # ^ |   +1 A somewhat loose proof for the solution to E is that if you consider a list of numbers [2,2x,2y,2z,...] such that every term divides the smallest number (for example, 2), no matter how you re-arrange the numbers, eventually, you will have to take it modulo the minimum number in the array, which will cause the result to become 0. Then, it is zero all the way to the end.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +17 How to prove that if there is more than one number not the multiple of $k$ then the final modulo is different?
•  » » » » » 5 months ago, # ^ |   +30 Suppose that there is a number $a_i$ that is not divisible by $a_1$.Let $x$ be equal to $a_i$, and let's take two following orders: $[a_1, a_2, a_3, \dots, a_k]$ and $[a_i, a_1, a_2, \dots, a_{i-1}, a_{i+1}, \dots, a_k]$. Then in the first case, $x \bmod a_1$ is non-zero (but less than all $a_i$, so it is the resulting value), and in the second case, $x \bmod a_i = 0$.
•  » » » » » » 5 months ago, # ^ |   -14 How to prove that array consisting of multiple of $a_1$ and of size $k$ will work ?
•  » » » » » 5 months ago, # ^ |   0 If the property isn't true, then there is some number (call it m), which isn't a multiple of k.Now, feed in X=k to the machine. If the permutation of A is [k,m,kx,ky,kz,...] then our answer is clearly 0.However, if our permutation of A is [m,k,kx,ky,kz,...] then clearly since m is not divisible by k (by definition), then the value will be (k%m), and the value after the second step will also be non-zero. The value of the result won't change after the second step, because kx,ky,kz > k. Therefore, the final result in this state is non-zero.So our array that included m was therefore unstable.
•  » » » » 5 months ago, # ^ |   0 take $n=4$ , $k=2$ , $x = 5$. Then $5mod2mod4$ is not $zero$ ,
•  » » » » 5 months ago, # ^ | ← Rev. 9 →   0 We can prove using mathematical induction. As BledDest showed that only those sequences may work which contain multiples of smallest number .Notation : $x$ mod $(a_1,a_2,a_3)$ = $((x$ mod $a_1)$ mod $a_2)$ mod $a_3$Base case : $size=2$ , consider $[a_i,v.a_i]$ where $v>1$ . Take any number $x$. Then $x = p.(v.a_i) + r$ , where $r •  » » » 5 months ago, # ^ | 0 suppose the gcd you'll take is g, then x=g*q+r, where r is x%g. now if you take x%(n*g) then x%(n*g)=g*(q%n)+r which is some g*q'+r. after repeated divisions when you finally do %g the answer will be q. •  » » 5 months ago, # ^ | 0 couldn't agree more •  » » 5 months ago, # ^ | -27 The round was very similar to AtCoder Beginner Contest, except for F (which I don't dare to even read lol)  » 5 months ago, # | ← Rev. 2 → +1 Why D gets WA on testcase 7.my submission : 81782286 •  » » 5 months ago, # ^ | +4 use kadane from left and then again right taking sum-max...i was stuck there as well •  » » » 5 months ago, # ^ | 0 Why? •  » » » 5 months ago, # ^ | 0 Whaaat??? What the hell?? I just did the left and got struck. But, well. Why we need to do again from the right?? •  » » » » 5 months ago, # ^ | +9 pointless...its wrong..my submission is hacked •  » » » » 5 months ago, # ^ | ← Rev. 2 → +5 Because the largest number taken at each step (subtracted from the sum) maybe different when taking from the right.Example: 11 3 0 1 -2 5 -5 -1 0 3 2 2 When taken only from left, the answer is 3 but when taken from right, the answer is 4 (3 2 2).However, even this solution doesn't work for cases like, 8 4 -10 13 -13 2 2 -11 6  •  » » 5 months ago, # ^ | ← Rev. 2 → +5 Couldn't solve it, but i changed my code for this testcasen = 6[9, 1, -9, 2, 2, 2] •  » » » 5 months ago, # ^ | ← Rev. 2 → 0 I didn't come up with a counterexample like this >_< •  » » » 5 months ago, # ^ | 0 Screw up +120 like that. No!!! •  » » » » 5 months ago, # ^ | ← Rev. 3 → 0 it is ok, if you use kadanes from left and right still you will end up in this case :P730 -20 5 1 3 -20 30ans would be 4 but by using two kadanes we get 0 :(  » 5 months ago, # | -43 C was really interesting...  » 5 months ago, # | 0 Solotion of C!!! Please! •  » » 5 months ago, # ^ | 0 Is'n it binary search on odds and also denote all evens are the same?! •  » » 5 months ago, # ^ | 0 I used two ternary-search (one for hot == cold + 1 and one for hot == cold) and compared two final results from each ternary search, but I think there are easier solutions •  » » » 5 months ago, # ^ | 0 You don't need to do any search for case hot == cold since the answer for that case must be (h + c) / 2 •  » » » 5 months ago, # ^ | ← Rev. 2 → 0 . •  » » 5 months ago, # ^ | +1 For all the odd pouring, the temperature at ith pour would be ((i+1)*h/2+(i-1)*c/2) and this has to be equal to t. Now on finding i, the answer would be 2*i-1. •  » » 5 months ago, # ^ | +10 C can be solved in O(1) time.This is my submission: 81757911If h == t, clearly the answer is 1. If h + c >= 2 * t, the answer is 2 as the most you can lower the average to the target is via the first cold cup.Now we consider the case where the average of h and c is less than t.We make an observation that now there will be one more hot cup than cold cup, so let the number of cold cups poured in be k. Inclusive of the latest hot cup, the average temperature would now be ((h+c)k + h) / (2k + 1). We would like to find the value of k such that the fraction is closest to t.We first solve the equation where ((h+c)k + h) / (2k + 1) == t. We can then obtain h-t = k(2t-h-c) and k = (h-t)/(2t-h-c). We can see that either floor(k) or ceil(k) will give us the closest value to the target, hence we check the difference between ((h+c)k + h) / (2k + 1) and t for floor(k) and ceil(k), thus solving the problem. •  » » » 5 months ago, # ^ | 0 Hi, I am unable to understand why when h+c>=2t, answer will be 2. Can you please explain? •  » » » » 5 months ago, # ^ | +3 When the average is greater than t, the smallest average is obtained by pouring 1 hot and 1 cold cup. The average is the same if there is an equal number of hot and cold cups, and it will increase when there is one more hot cup. Thus, 2 is the minimum number of cups for the average to be closest to t.  » 5 months ago, # | -10 One of the best contests ever. Got to know for the first time(or maybe noticed for the first time) about the modulus property that had to be applied in problem E. Thanks again !!  » 5 months ago, # | -6 The worse trick ever used in B.  » 5 months ago, # | +35 Task C took soul out of me but never showed Accepted •  » » 5 months ago, # ^ | -27 From when Irfan Khan started coding?after dying? •  » » » 5 months ago, # ^ | +11 Actor like Irrfan Sir never dies, he is immortal in our hearts. •  » » » » 5 months ago, # ^ | +4 Oh I love this man too.I was just joking <3Legend never dies. •  » » 5 months ago, # ^ | 0 Your dp explains everything, Irfan Sir please comeback xD •  » » 5 months ago, # ^ | 0  » 5 months ago, # | 0 I thought that the hotcups - coldcups = 0 || hotcups - coldcups = 1. Using that I derived a formula and took when the absolute difference is getting minimum of these two conditions. Why wasn't this correct?  » 5 months ago, # | ← Rev. 2 → 0 Please tell me what is wrong with this solouton for C 81802932 I know I've been silly there but please help me •  » » 5 months ago, # ^ | 0 Even if$\frac{h+c}{2}\neq t$,$2$may still be an answer. Since$\frac{h+c}{2}$may be closer to$t$than the answer you use binary search to get. •  » » » 5 months ago, # ^ | +1 that was the case I missed I forget comparing the answer of bs with the answer that I got (h+c)/2 i.e 2  » 5 months ago, # | ← Rev. 2 → 0 Can anyone suggest me an easy solution for 1359D - Очередная очередная задача?  » 5 months ago, # | 0 Can D be solved with the DP? •  » » 5 months ago, # ^ | 0 Yes, I solved with DP. •  » » 5 months ago, # ^ | +5 Idk about dp, but i'd like to say it can be solved in nlogn independent of ai's values. Sort a list of indices based where indices with higher ai values come first, and hold a segment tree of the prefix sum values. Now just iterate through your list of indices and add them as boundaries for querying in a set as you go, and for each index find the largest prefix sum greater than and index and the least prefix sum less than an index such that the range is within all the boundaries in your set, then update ret with subtracting those prefix sums minus the current indices value. •  » » » 5 months ago, # ^ | +5 It can be solved in O(n) as well independent of ai's value. You can maintain a stack to do so, https://codeforces.com/contest/1359/submission/81806616 . •  » » » » 5 months ago, # ^ | 0 Wow, very cool! •  » » » » » 5 months ago, # ^ | 0 Thanks :) •  » » » » 5 months ago, # ^ | ← Rev. 2 → 0 can you please explain your solution ? •  » » » » » 5 months ago, # ^ | ← Rev. 2 → +21 Basically for each index 'i' of array (1-based indexing), I found out what is the rightmost j for which a[j] > a[i] and j < i. Now Assuming this element has to be removed, I maintained a mxl array to maintain max. subarray sum that is ending at [i — 1] for a given 'i'. Note this includes a[i — 1], (no matter if its positive/negative). Now as per the implementation using stack, for left ('L') part, for a given 'i', s.top has 'i — 1' index, so I keep on removing indices from stack for which a[s.top()] <= a[i], but also kept on maintaining the max sum ending at 'i — 1', which includes a[i — 1]. If you observe mxl[s.top()] does not necessary means max sum goes up to indices 2nd topmost element of stack. So to find the mxl[i], you have to make the continuous sum starting from 'i — 1' to the current s.top(), and update the mlx[i] if valid.Similar goes for right part.And then for each element just assume you are removing it from its range, find what is the max left and right sum within the range.Also if you are still having difficulty in understanding this, I would suggest first try solving easy part of this question — Imbalanced Array. The editorial of it have a similar idea. •  » » » » » » 5 months ago, # ^ | 0 Thanks..! •  » » » 5 months ago, # ^ | ← Rev. 2 → 0 I solved it in O(n) . I first used Kadane algorithm and then i consider all subsegment which do not contain negative number .submission Edit : now hacked . •  » » 5 months ago, # ^ | +3 Yeah, dp[i][j] = max value you can get with a segment ending at i, with maximum equal to j. The transitions are pretty straightforward (just need to offset negative values).Submission: here •  » » » 5 months ago, # ^ | 0 Can you explain the transitions? I don't quite get it •  » » » » 5 months ago, # ^ | +14 Initially, you can start a new segment at some index, but it will be the maximum, so dp[i][a[i]] = 0 to start. But also, you could have extended some segment ending at i-1, so there are 2 cases to consider. j, the old maximum was smaller than a[i]. Then you get dp[i-1][j] + j, because a[i] becomes the new max (you already "paid" for j in dp[i-1][j], so add it back in to compensate). j is greater than a[i]. The maximum doesn't change, so you get dp[i-1][j] + a[i] I hope that helps. •  » » » » » 5 months ago, # ^ | 0 Thanks! This is a really cool solution •  » » 5 months ago, # ^ | +1$dp[index][maxval]$is the maximum sum ending at$index$containing$maxval$as the max value. Answer is$max (dp[index][maxval]-maxval)$ » 5 months ago, # | 0 isn't C binary search why alot of people wa on 2 testcase •  » » 5 months ago, # ^ | +1 Nope, it comes down to a simple tiny equation. •  » » » 5 months ago, # ^ | 0 help me understand ... whats the equation? •  » » 5 months ago, # ^ | 0 For me personally, it was using binary search even if t<(b+c)/2. As soon as i rectified that, I got it accepted. •  » » » 5 months ago, # ^ | 0 Same! T-T  » 5 months ago, # | ← Rev. 2 → +1 DELETED •  » » 5 months ago, # ^ | 0 help me with problem C •  » » » 5 months ago, # ^ | +2 I would love to help you, but I am not one of those 3167 people. :( •  » » » 5 months ago, # ^ | 0  » 5 months ago, # | +53  » 5 months ago, # | +9 In q C, my code gave wrong answer in C++17(64) but got accepted in C++14. Happened with anyone? •  » » 5 months ago, # ^ | +3 I guess you were working with double data type. •  » » » 5 months ago, # ^ | ← Rev. 2 → 0 Is there any problem with double in c++17(64)? Thanks •  » » » » 5 months ago, # ^ | 0 I don't know what is actually wrong but i faced problem while comparing two double few times. So i try to compare it keeping it integer.Say i need to compare x/a and y/b. I compare x*b and y*a (Multiply both a*b). In this case there is no chance of precession loss. •  » » » 5 months ago, # ^ | 0 what is wrong with double data type in c++17? •  » » » » 5 months ago, # ^ | 0 See This Comment •  » » 5 months ago, # ^ | 0 me too! this was really frustrating as i kept on changing my code and still getting the same wrong answer •  » » » 5 months ago, # ^ | 0 Same here. •  » » 5 months ago, # ^ | 0 Same is happening with me too. But I figured this out after reading your comment. Thanks for mentioning. Pupils, here I come.  » 5 months ago, # | +30 I feel if E was before C it would have more solves  » 5 months ago, # | 0 Can someone why my submission to problem D, received runtime error on test 2? It was working fine on my local machine. Thanks  » 5 months ago, # | 0 Problem F is already in emaxx. https://cp-algorithms.com/geometry/intersecting_segments.html •  » » 5 months ago, # ^ | +60 Good thing that pikmike found some tests to break that code if it is copypasted without any changes •  » » » 5 months ago, # ^ | +28 I got AC, copying and pasting that code, just changing EPS and using long double •  » » » » 5 months ago, # ^ | 0 Devil please explain how did you assumed the limits inside for loop like 100 and HI variable and also this part hi - lo > 5*1e-9 •  » » » » » 5 months ago, # ^ | 0 •  » » 5 months ago, # ^ | -38 its ok since even mifafao was not able to solve it  » 5 months ago, # | +3 In Problem C, I was worried about using floating point numbers, and then thinking about a solution using only integers ... •  » » 5 months ago, # ^ | +5 I used my own fraction class for the same, and it didn't even have a greater than operator, damn it sucked :( •  » » 5 months ago, # ^ | +5 You could have done it by holding best current value by numerator and denominator, then just comparing fractions.  » 5 months ago, # | 0 Not brute forcing to find a pattern do be like that sometimes. E would have been significantly easier if it was placed as problem C.  » 5 months ago, # | -29 hi guys why this solution don't work in pb b THANKS . #include using namespace std; typedef long long ll; int main() { int t; cin>>t; while(t--) { int n,m,x,y; cin>>n>>m>>x>>y; char mat[n][m]; cin.ignore(); int ans = 0; for(int index=0;index>c; if(c=='.') curr++; else{ ans +=min((y*curr/2+curr%2*x),x*curr); curr=0; } } ans +=min((y*curr/2+curr%2*x),x*curr); } cout< •  » » 5 months ago, # ^ | ← Rev. 2 → 0 Your solution will place a 1x2 block for this case: .*.* The problem states that you can not break the 1x2 block, so this block can be used only when 2 dots are together, like this: *..*  •  » » » 5 months ago, # ^ | 0 I don't think that's true. In your example, the innermost "else" triggers on each *, at which point curr has value 1, so x is added to the total and curr is reset to 0. •  » » » » 5 months ago, # ^ | +8 thanks guys for ur replyes acually , my solution work . i jut forget "(" in y*curr/2 cuz (curr/2)*y!=y*curr/2 . that why i get wrong answer.  » 5 months ago, # | +16 My AC solution of problem F is wrong. Can anyone hack me? Please (>__<). •  » » 5 months ago, # ^ | -22 still, I can't! i m so noob ༼ ಥ_ಥ ༽ •  » » 5 months ago, # ^ | 0 I know it's plan to waste everyone's time.... Im not gone a fall in trap •  » » 5 months ago, # ^ | 0 Did you think about the case when the two cars are aline? •  » » » 5 months ago, # ^ | 0 My solution can fail on normal case. You can see other Account solution is quite different with mine.  » 5 months ago, # | 0 AC problem F, just after the contest... WHY I DIDN'T REMEMBER TO USE 1e-10 INSTEAD OF 0.0 !!!  » 5 months ago, # | -6 For D, i took : max of (maximum subarray sum ending at index i — max element in that subarray) for all indices i, why doesn't this work? •  » » 5 months ago, # ^ | 0 did you use kadane? •  » » » 5 months ago, # ^ | 0 yes •  » » 5 months ago, # ^ | ← Rev. 3 → +7 Update: I did the same thing again from the right now it got AC. update: Got hacked. forget this •  » » » 5 months ago, # ^ | +4 lol that second update •  » » » 5 months ago, # ^ | 0 Yeah man same here. Any idea why is it so? •  » » » » 5 months ago, # ^ | 0 I guess the Kadane's Approach will fail when we have 2 subarrays having equal Maximum Sum Let suppose we have 2 sub-arrays having maximum sum equal to S, but having different maximum elements d1 & d2 in corresponding two sub-arrays, respectively. Using Kadane we'll take only the latest subarray sum( hence, Answer = S-d2). This will hold true only if d1>=d2. We'll miss the case where the Answer should be S-d1. •  » » 5 months ago, # ^ | +4 7 15 -14 10 10 10 -14 15 answer is 20 (pick subarray [3, 5]) •  » » » 5 months ago, # ^ | 0 thanks! •  » » 5 months ago, # ^ | +3 It fails on this case Spoiler430 -22 6 7Optimal answer is 6 but your algo will give 0 as answer. •  » » » 5 months ago, # ^ | 0 thanks!  » 5 months ago, # | 0 When you missed the last exercise because you didn't round an almost zero value to zero before comparing it with zero. So sad :(  » 5 months ago, # | +7 Can C be solved using ternary search? •  » » 5 months ago, # ^ | 0 Yes, it can be,Here is a link to my submission: 81816118  » 5 months ago, # | ← Rev. 4 → 0 Can someone explain the following case for problem D? 11 3 0 1 -2 5 -5 -1 0 3 2 2 `The answer is 4 but I'm getting 3 after trying it out by hand and with my code.Edit: Figured it out. In case anyone's wondering, the max_num at each step when taken from left maybe different from the max_num when taken from the right. •  » » 5 months ago, # ^ | 0 Choose the subarray [8,10] 0-index. That is [3,2,2]. •  » » 5 months ago, # ^ | 0 Segment [9, 11] gives answer 4. •  » » 5 months ago, # ^ | 0 Take the segment with last three elements answer will be 4 •  » » 5 months ago, # ^ | 0 Thanks everyone.  » 5 months ago, # | ← Rev. 2 → 0 can someone look this solution for C why it fails? submission  » 5 months ago, # | 0 Could someone tell me why https://codeforces.com/contest/1359/submission/81809462 gives TLE  » 5 months ago, # | +3 Can anyone tell hack for C? TIA  » 5 months ago, # | ← Rev. 2 → +4 Video Editorial :- Problem CI will add editorial for problem D using segment trees soon. •  » » 5 months ago, # ^ | 0 Can you explain in brief ? •  » » » 5 months ago, # ^ | 0 Editorial for Problem C — https://pro-coder.tech/cf-1359-problems/ I will add for rest soon!  » 5 months ago, # | +8 Hi! So I was going through the hacks and saw something odd...https://codeforces.com/contest/1359/submission/81798994So this guy made a smurf, submitted his own code, and intentionally added code which would fail on certain input. And you can even see that the author's name is still the same! There aren't any points for hacks in this contest, but shouldn't there be some action against this user?  » 5 months ago, # | +2 How to solve D without using dp ? •  » » 5 months ago, # ^ | +3 We can use sparse table and concept of NEXT GREATER ELEMENT.\CHECKOUT :81811299 •  » » 5 months ago, # ^ | +19 For each element ai find the range at which it is maximum, let the range be [l,r]. The sum it would contribute if Bob chose to remove ai is maxsuffixsum(l,i-1) + maxprefixsum(i+1,r). The first part can be calculated using stack and the second part with segment tree. My submission •  » » » 5 months ago, # ^ | 0 Brilliantly explained! •  » » » 5 months ago, # ^ | ← Rev. 2 → +3 Even the second part can be calculated using the same stack you are using in 1st part. Refer: https://codeforces.com/contest/1359/submission/81806616 , giving you an effective O(n) solution. •  » » » 5 months ago, # ^ | 0 can you also add the time complexity •  » » 5 months ago, # ^ | ← Rev. 2 → -6 See my solution, quite easy to code: 81741311You can even replace the segment tree with sparse table and set with stack to get an O(N) solution.  » 5 months ago, # | 0 For the problem C, I think there is always a way to achieve the average temperature equal to c. Let's say, x number of hot cups were poured and y number of cold cups were poured if we solve the equation assuming, the average temperature will eventually be equal to c, we have hx + cy = tx + ty from here, you get x:y = (t-c):(h-t) taking x and y in this ratio should give the answer, so final answer should x+y For example, in the second sample test case given, x = 15, y = 11, the average temperature will come to 30. So, the judgment is wrong for this question. Please advise on my understanding and correct me if i am wrong. •  » » 5 months ago, # ^ | ← Rev. 2 → 0 The problem requires that x-y is either 0 or 1. •  » » 5 months ago, # ^ | 0 You have to take hot and cold cup alternatingly. So either x=y or x=y+1 You are missing this condition. •  » » » 5 months ago, # ^ | 0 Same here •  » » 5 months ago, # ^ | 0 OK, here is the problem. You cannot pour the hot and cold water for an arbitrary number of times. You must start by the hot water, then cold, then hot, then cold, and so forth.So, the number of hot cups can either be equal to or one more than that of cold cups.More formally, according to your notations,$x=y$Or,$x=y$+$1$ » 5 months ago, # | 0 can someone hack my C? 81742048I believe it is wrong :) •  » » 5 months ago, # ^ | 0 I made some random tests for your code, and after 3000 tests, all answers were the same as my code. I think your code is correct! (Or we both made the same mistake) •  » » 5 months ago, # ^ | 0 long double is not hackable I think.  » 5 months ago, # | +3 Here's a proof for$E$.Take any index$i \neq 1$. The condition applied to$x = a_1a_2\dots a_k + a_i$in the order$a_1,a_2,\dots ,a_k$gives$a_i \pmod{a_1}$on each step since this is at most$a_1-1$and all modules are greater than that.Now evaluating in order$a_i,a_1,a_2,\dots a_{i-1}, a_{i+1}, \dots a_k$evidently gives$0$as$a_i | a_1\dots a_k + a_i$. Therefore$a_i \pmod{a_1}$must be zero, which means$a_1|a_i$for all indices$i$.Proving that the smallest element dividing all others is enough is not hard. Say$r_1 = x \pmod{a_{p_1}}$,$r_2 = r_1 \pmod{a_{p_2}}, \dots$.Notice that for any$r_i$by definition we have$r_i = r_{i-1} \pmod{a_{p_i}}$thus$a_{p_i}|r_i-r_{i-1}$where we define$r_0 = x$. Since$a_1|a_{p_i}$we must have$a_1|r_i-r_{i-1}$for all$i$. Thus$a_1|(r_1-r_0)+(r_2-r_1)+\dots + (r_{k}-r_{k-1}) = r_k-r_0 = r_k-x$.We also know that the result is a non negative integer at most$a_1$because once$\pmod{a_1}$is applied the result becomes constant as all other modules are bigger. Thus$r_k$is always$x \pmod{a_1}$no matter what order we do the operations in.Therefore the problem reduces to finding for each smallest element$a$, the number of ways in which we can choose$a_2 < a_3 < \dots < a_k$integers divisible by it in the range$(a,n]$.This is just$\displaystyle \sum_{a=1}^{n} \dbinom{\left\lfloor \frac{n-a}{a} \right\rfloor}{k-1}\$.
 » 5 months ago, # |   +3 Today's ques C went like a Game changer for many .
 » 5 months ago, # |   0 can someone please let me know why this one fails? (Problem C)I am quite new to this, so help for future would be apreciated.Also I tried https://codeforces.com/contest/1359/submission/81786741 (kinda naive solution I guess, but still wrong answer)
•  » » 5 months ago, # ^ |   0 Your logic is wrong.
•  » » » 5 months ago, # ^ |   0 can you be more concrete? when would that fail? because it seems that it works for most cases, I can't see why it doesn't for the few.
 » 5 months ago, # |   0 what is the approach for D except seg tree! can we solve it using kadane