By pikmike, history, 8 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 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 participants!

UPD:

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

Codeforces! What is the next step in your development?

We understand all about doing things by yourself — after all, we are a startup university, and our student body is exceptional in part because of it’s made up of people who didn’t wait for anyone to show them the way.

If this is you, you belong at Harbour.Space. The purpose of our University is to create a global community of these kinds of people, regardless of age or nationality, because when you’re working by yourself, you can change for the better, but when you work with others, you can change the world.

If you believe you have what it takes, we want you!

The curriculum is part of what makes the modules so special, and the other half? Our outstanding teachers who are leaders in their own respective industries.

Our scholarships are set in such a way that doesn’t require additional applications — we believe in merit and potential, and so what you put in your application to the university will be our criteria.

You could be just the diamond we’re looking for, but you’ll never know unless you apply!

APPLY NOW→

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 mango_lassi 6 145
2 E869120 6 148
3 kefaa2 6 154
4 egor.lifar 6 154
5 Aria 6 157

Congratulations to the best hackers:

Rank Competitor Hack Count
2 test_hack 56:-37
3 alvinvaja 30:-10
4 AryaKnight 48:-48
5 nikolapesic2802 30:-14
779 successful hacks and 1077 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Geothermal 0:01
B mango_lassi 0:05
C nuip 0:07
D Yushen 0:04
E Sehnsucht 0:20
F osaaateiasavtnl. 0:05
G LgndryGrandmasturbator 0:47

• +181

 » 8 months ago, # | ← Rev. 2 →   -6 [deleted]
 » 8 months ago, # |   +3 Thanks for the consecutive contests! Wish that the problem statements will be neat and clean and short as the previous one. Eid Mubarak everyone!
•  » » 8 months ago, # ^ |   +8 Eid Mubarak ! Happy Eid-ul-Fitr !!
 » 8 months ago, # |   +515
•  » » 8 months ago, # ^ |   0 True Story.
•  » » 8 months ago, # ^ |   +10 This picture reminds me of this song.
•  » » » 8 months ago, # ^ |   +5 You want to be white rank?
•  » » » » 8 months ago, # ^ |   +7 No, I want you to be white rank! I want something just like this
•  » » 8 months ago, # ^ |   0 The story of my life.
•  » » 8 months ago, # ^ |   +91
•  » » » 8 months ago, # ^ |   0 true, but make your special girl unrated, not cm
•  » » » » 8 months ago, # ^ |   0 stef just reach 2400 instead of 2300 next time and i guarantee you will be more successful
•  » » 8 months ago, # ^ |   +32 The guy she told you not to worry about is Tourist.
 » 8 months ago, # |   -42 Comment "Is it Rated?" if you want to gain contribution points! (In the negative direction)
•  » » 8 months ago, # ^ | ← Rev. 3 →   -51 Let me do this job for you. Is is Rated (for Div1)?Ans seems Yes. MikeMirzayanov PikMike Please fix it.Everyone is registered as "Contestants".Mark me and others as "out of competition".
•  » » » 8 months ago, # ^ |   +4 No, it is not rated for you. It is rated only for those who are below the master
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +32 It is not a bug. In Educational Rounds no one is out of contest everyone can compete officially but it is only rated for Div2. And after contest in the Final Standings there are options (div1,div2) to see standings
 » 8 months ago, # |   +32 thank u, pik misha!!!!!!!!!!!!!!!!! i love you
•  » » 8 months ago, # ^ |   +50 we all love pik misha :D
 » 8 months ago, # |   +15 I never really understood the concept of Educational Rounds. Don't we learn something new from every contest? Why exactly term it Educational?
•  » » 8 months ago, # ^ | ← Rev. 3 →   -28 LoOOoOOooOooLoOOOoooOOOoOOLoOoOooOoooooOOL. ROFL. LMAO.Problems at usual contests: "use a segment tree with some trciky operations and tricky queries"Problems at educationals: "use a trivial segment tree, (yes) and queries are in the form of $[p_i,i]$didn't you feel that difference?"
•  » » » 8 months ago, # ^ |   +63 Finally found the person who uses the id LanceTheDragonTrainer.
•  » » » » 8 months ago, # ^ |   0 no, he uses id riela
•  » » » » » 8 months ago, # ^ |   +6 LoOOoOOooOooLoOOOoooOOOoOOLoOoOooOoooooOOL. ROFL. LMAO.marymarine is no longer my alt, we disbanded because he doesnt like twice.
•  » » » 8 months ago, # ^ | ← Rev. 3 →   +3 Yup, that makes sense. Thanks!
•  » » » 8 months ago, # ^ |   +2 And for us mortals, Educational rounds are ironically harder than the normal rounds, and the editorial comes the same way for both educational and normal rounds, so not even sure what's the point of calling it "educational".
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +33 it is your fault if you fail to solve problemsonce more:edu rounds -> hard problems with classical ideasusual rounds -> hard tricky problems
•  » » » » » 8 months ago, # ^ |   +1 Yes, I'm just saying how ironic it is for a round that calls itself "educational" is as educational as any other round and it manages to make itself harder than an average round.I just don't get it, I literally don't get why it's called "educational", it has no special property what so ever that would make it educational.I'm talking about ABC tasks, I'm not qualified enough to talk about the difficulty of DEF...
•  » » » » » » 8 months ago, # ^ |   0 Yes, DEF are actually educational
•  » » » » » » » 8 months ago, # ^ |   0 If educationals DEF are so much easier than normal round DEF then why does DEF get solved the same/less than in a normal round ? This EDU alone has only like 20 people who solved DEF, maybe 50 that solved DE, and the rest are D
•  » » » » » » » » 8 months ago, # ^ |   +10 i didn't say they are easier, i meant they are with classic ideas
•  » » » » » » » » » 8 months ago, # ^ |   0 You are not in Div2, so they may be classical to you, they're certainly not classical for Div2 users.
•  » » » » » » » » 8 months ago, # ^ |   0 The purpose of contests is for people to solve problems and learn from them I think.It doesn't matter if its name was "Educational" or something. If you are good you can solve problem. If you are not you need to learn more, tutorials is a good point.
•  » » » » » » » » » 8 months ago, # ^ |   0 I'm fine with the rounds, the more the merrier, just saying that EDU rounds are worse than normal rounds imo.
•  » » » » » » » » » 8 months ago, # ^ |   0 I enjoyed all of the problems. I mean we aren't allow to choose our life condition so we need to prepare for the worst.
•  » » » » » » » » » 8 months ago, # ^ |   0 I enjoyed the problems of this EDU as well, I'm talking about the previous EDU.
•  » » » » » » » » » 8 months ago, # ^ |   0 Yes, I'm talking about every problem :)
 » 8 months ago, # |   +18 PikMike is a boy or a girl?
•  » » 8 months ago, # ^ |   +180 I'm a wolf! awoo~
•  » » » 8 months ago, # ^ |   +3 awoo and uwu?
•  » » » » 8 months ago, # ^ |   +142
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   +8 why must you do this to me
•  » » » » » 8 months ago, # ^ |   0 UWU
•  » » » » » 8 months ago, # ^ |   +16 just awoo then?
•  » » » 8 months ago, # ^ |   +14 That moment when you realize that a wolf can code better than you.
•  » » 8 months ago, # ^ |   0 true
•  » » 8 months ago, # ^ |   +6 Best Girl is also Best boy
 » 8 months ago, # |   +30 yesKonstantin Mertsalov is a nice man , we discussed some math problems with him through skype
 » 8 months ago, # |   +43 Eid Mubarak to all Programmer.
 » 8 months ago, # |   +172
•  » » 8 months ago, # ^ | ← Rev. 2 →   +8 The.Last.Wizard ur logic hhhhhhh
 » 8 months ago, # |   -70 First question has wrong limits on K!! Because of this I lost valuable time
•  » » 8 months ago, # ^ |   -53 I wonder why im getting downvotes...am I wrong?
•  » » » 8 months ago, # ^ |   +20 what is wrong with the limits?
•  » » » » 8 months ago, # ^ |   -16 k = 1 in one test case but question says k>=2
•  » » » » » 8 months ago, # ^ |   0 Can you see the test case? How do you know that?
•  » » » » » » 8 months ago, # ^ |   -13 I added the check for k == 1 and it passed
•  » » » » » » » 8 months ago, # ^ |   +5 Is that the only difference in your solutions?
•  » » » » » » » 8 months ago, # ^ | ← Rev. 2 →   +9 If you want to be sure add assert(k >= 2) right after your read input and submit again! If you are right you should get a RuntimeError verdict.
•  » » » » » » » 8 months ago, # ^ |   +34 You changed types from int to long long
•  » » » » » 8 months ago, # ^ |   +19 I don't think it's true. My accepted submission would loop forever on $K = 1$.
•  » » » 8 months ago, # ^ |   +8 Yes.
•  » » » 8 months ago, # ^ |   -7 because you wrote very trashy comment.you are just a pupil after 4 years and you said codeforces contest has a problem ??how did you decide to write this comment ?
 » 8 months ago, # | ← Rev. 2 →   -21 Thanks for the round.
 » 8 months ago, # |   -28 The worst B problem I have ever solved
•  » » 8 months ago, # ^ |   +38 There is always "A worse" in CF...
•  » » 8 months ago, # ^ |   +12 why?In my opinion this problem is cool.
•  » » » 8 months ago, # ^ |   +3 IDK, maybe im stupid, but i couldnt find whats wrong with my code
•  » » » 8 months ago, # ^ |   -16 But tricky. Swapping C and B would be better.
•  » » » » 8 months ago, # ^ |   0 The same opinion
•  » » » 8 months ago, # ^ |   +1 How did you solve it? I got WA in test 5.
•  » » » » 8 months ago, # ^ |   +3 Think of following test case 10^5/2-1 nested for loops with add.
•  » » » » » 8 months ago, # ^ |   0 https://codeforces.com/contest/1175/submission/55150517 what's wrong with this? please help me in debugging.
•  » » » » » 8 months ago, # ^ |   0 for 100 for 100 .... .... .... add end end ... ... Like this?
•  » » » » » » 8 months ago, # ^ |   0 Yes. People who are storing value to add will result in overflow for long long.
•  » » » » » » » 8 months ago, # ^ |   +1 I didn't do that but still I'm getting wrong answer on test case 8. Please help.
•  » » » » » » » » 8 months ago, # ^ |   0 same here, can't figure out why am I getting WA on TC 8
•  » » » » » » » » 8 months ago, # ^ |   0 even got WA on tc8. I wasn't checking th condition when the answer was exactly 2^32.
•  » » » » » » » » » 8 months ago, # ^ |   0 pa.n.ik Can you please take a look at this ?? 55171711 I have checked for 2^32
•  » » » » » » » » » 8 months ago, # ^ |   0 amstan your code is too complicated to understand, here refer my solution
•  » » » » » » » » » 8 months ago, # ^ |   0 It's even easier to understand with recursion. Here: recursive_solution_to_B
•  » » » » » » 8 months ago, # ^ |   0 Can you tell why this code gives WA on test case 9?55158372
•  » » » » » » » 8 months ago, # ^ |   0 I guess you are using the accumulated sum and multiplying it for each loop. Check for input : 6 for 3 add end for 3 add end // output : 12 // should be : 6
 » 8 months ago, # |   +7 I really liked D there's a relation between each possibility but I don't know how this is going to help :/ how did you solve it
•  » » 8 months ago, # ^ |   +1 Expand the summation using prefix sums everywhere
•  » » » 8 months ago, # ^ |   +4 Is this correct k*ps[n] — (sum of small k-1 smallest prefix sum)
•  » » » » 8 months ago, # ^ |   0 Yeah
•  » » » » » 8 months ago, # ^ |   +3 Too bad I cannot implement it. Though this problem looks like some DP optimization which I am not familiar with and started searching articles for it.
•  » » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 don't forget to exclude ps[n] though, while finding k-1 smallest prefix sums.
•  » » » » » » » 8 months ago, # ^ |   0 it is easier to implement using suffix array
 » 8 months ago, # |   0 Problem B!! :'( made it the worst contest I gave on codeforces :/ and why cant we use python3 signal in codes :'/
•  » » 8 months ago, # ^ |   +1 Problem B is just a simple stack based problem of evaluating parenthesized expressions.And as for signal, check the documentation. signal.alarm is unix only
•  » » » 8 months ago, # ^ |   0 Can you tell why this code gives WA on test case 9? 55158372
 » 8 months ago, # | ← Rev. 3 →   +19 I'm so sorry of that. I just wanted to laugh and maybe some upvotes. I didn't think reminding some old joke would be that annoying. Maybe this cause more downvote, but I want to talk some more words. I'm just a kid, please just don't make me cry. :( Last day I started commenting and I got contribution +3. But now it is going down to -4. I'm so depressed by now. I promise I won't write something idiot more. I'm sorry again. Can you help me get my contribution up to 0 again?
•  » » 8 months ago, # ^ |   +44 throw new JokeTooOldException(); 
•  » » » 8 months ago, # ^ |   +4 Just a reminder. :D
•  » » » » 8 months ago, # ^ |   0 Which site you use to upload photos there's alot of memes in my mind to post XD
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   +4 I just got this from another comment on CFBut I found a site to upload.After that I disabled my antivirus and then something special happened to my desktop.(the backgroung and resolution changed suddenly)Be Carefull. Btw do you know how to get upvotes?
•  » » » » » » 8 months ago, # ^ |   0 Don't post all the jokes you think about because some of them aren't that funny the more unique and unexpected the joke is the more upvotes it will get also the right timing plays a role . Btw I did not understand what does the antivirus has to do with uploading a photo.
•  » » » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 After uploading I wanted to send it here. I copied the URL and posted it. Then the antivirus blocked it. Because I wasn't sure that it is sent correctly. I turned off the antivirus. And after a few moments that happened. It was my mistake to turn off the antivirus.
•  » » 8 months ago, # ^ |   +5 D was quite solvable
•  » » » 8 months ago, # ^ |   +7 Maybe not for me.
•  » » 8 months ago, # ^ |   +8 C is extremely hard to me. lol In my opinion D is easier than C. :)
•  » » » 8 months ago, # ^ |   0 Agree. 38 minutes spent on C, mostly staring at piece of paper. 30 minutes for D, no idea why it took so long.
 » 8 months ago, # |   +6 How to solve E?
•  » » 8 months ago, # ^ | ← Rev. 4 →   +15 Create sparse table such that nxt[i][j] is the maximum index sucht that [i, nxt[i][j] ] can be covered using atmost $2^j$ segments.
•  » » » 8 months ago, # ^ |   +20 Can be solved using binary lifting (this is the same, but actually easier to code).
•  » » » » 8 months ago, # ^ |   +30 Don't we call binary lifting on arrays as sparse table?
•  » » » 8 months ago, # ^ |   0 how do u prove this?
•  » » » 8 months ago, # ^ |   0 During the contest time I was thinking if I can create a sqrt decomposition solution.Couldn't find one. Can you think of one? ( I am pretty sure that the time limit can be tight)
•  » » » » 8 months ago, # ^ |   0 I have one in mind. For all precompute the ans for all [i, j] such that $j - i < \sqrt{n}$. Then the queries for $y - x < \sqrt{n}$ can be answered in O(1) and for others in $O(\sqrt(n))$
•  » » » » » 8 months ago, # ^ |   0 Yes, I had similar in mind.But I realized, it can be troublesome when an interval ( say [li, ri]) lies inside 2 blocks (say, [√n+1, 2*√n] call it block1 and [2*√n+1, 3*√n] call it block2).Because, that time when we loop through block1 and block2, I am not sure how to combine their answers. Are you able to feel the difficulty? Or do you have a better approach to it?
•  » » » 8 months ago, # ^ |   0 Would you like to elaborate more on how do you use the sparse table to find the minimum number of segments?
•  » » » 7 months ago, # ^ |   +3 I learnt about sparse table and successfully solved this problem.Thanks to you <3
 » 8 months ago, # |   0 How to solve D?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +7 Let 1, x2, x3,...,n be index where new subarray starts. Then answer is f(1)×1 + (f(x2)-f(1))×2+....+(f(n)-f(x_k-2))×k. Open it. f(i) is prefix sum till i'th element.
•  » » » 8 months ago, # ^ |   0 but how do you know which are the indexes where a new subarray starts?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +19 The idea is that once you expand you just get the sum of the suffixes that start with the left endings of the segments. Therefore the answer is the sum of the k-1 largest suffixes (without allowing the total complete string) plus the total sum.
•  » » » » » 8 months ago, # ^ |   0 Thank you Jefe :D
•  » » » 8 months ago, # ^ |   0 Do anyone know what test case 6 might be?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +11 test case 6 broke my solution and with a brute force I found this test case:5 3-1 -5 5 -3 6 Expected 16 but I answered 13.I can't be sure if your mistake is the same as mine though
•  » » » » » 8 months ago, # ^ |   +3 Thanks alot. Same mistake.
•  » » » 8 months ago, # ^ |   +2 If you need a lengthier explanation go here https://medium.com/@harryjobz/educational-round-66-a673621a3959
•  » » 8 months ago, # ^ |   +13 You can extend this proof to general k segments
 » 8 months ago, # |   +7 can't we solve C using the ternary search?
•  » » 8 months ago, # ^ | ← Rev. 2 →   -8 No you can't 55147246
•  » » » 8 months ago, # ^ |   0 but is there reason for it ?I mean isn't the function unimodal or some other reason ?
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 Why go for ternary when you can do with binary? Ref: 55155030 I used binary search on answer over f(x). Now if f(x) exists, it means that x must be equal array[i]+f(x) or arr[i]-f(x). Iterate over the array to find such possible 'i' where you get at least k-1 elements in the array which are less than or equal to f(x) (using upper bound). If you find any such 'i' then modify r, else modify l. f(x) = (l+r)/2 i.e. mid Hope it helps! :)
•  » » 8 months ago, # ^ |   0 No. because the f(x) might be something like sin(x) (just for imagination!). suppose there are k + 1 points close to each other, then a huge gap then again k + 1 points close to each other, then a huge gap and so on...
•  » » » 8 months ago, # ^ |   +8 Ok. to clarify my idea let's see this test case 4 0 10 20 30 40 k = 0 so $f_k(x)$ means the distance of the closest point to x for each integer x. the graph of $f_k(x)$ will be like this :
 » 8 months ago, # |   0 How to solve problem C?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +1 Average of points which have k-1 given integers between them.
•  » » » 8 months ago, # ^ |   0 Could you please explain the correctness of this approach?
•  » » » » 8 months ago, # ^ |   0 If the solution you get from that is not correct, that means you could move left or right. If you move left, you will be further away from the point on the right, which means you are no longer at the minimum. If you move right, you will be further away from the point on the left, which means you are no longer at the minimum. So, you just want to find the 2 given points that have k-1 given points between them, and the average of those 2 points will be your answer.
•  » » 8 months ago, # ^ |   0 you need to find k nearest points (summ(a[j] — a[i]) -> min, j = from 0 to k) in array and calc its middle point
•  » » 8 months ago, # ^ |   +16 My solution lets find minimal distance using binary search. Suppose the answer is X.Then, our answer point should be in the distance X for at least k points.Second part is just easy to check if there is a point where k segment intersect [a_i — X, a_i + X].Complexity O(n * log^2)But can be easily implemented in O(n * log)
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 why are you using binary search? if you already knows the greedy approach to check the answer, you can just do it without guessing the answers ... just get the mininum distance that a X point have the elements. The X with this minimum distance is the answer.
•  » » » » 8 months ago, # ^ |   +9 The problem that I don't know the minimum distance, I use binary search to find it.
 » 8 months ago, # |   +1 What is the proof of correctness of C?
•  » » 8 months ago, # ^ |   +3 Have you solved it? Well, supose X is outside the range we are right now. Then its better to put it inside the range, to decrease the distances of the k consecutives elements. The ans is the min middle point of all ranges with lenght K. (the best point is the middle one because it gives us the least k minimum differences).
•  » » » 8 months ago, # ^ |   +3 Thank You.
•  » » » » 8 months ago, # ^ |   0 ^.^
 » 8 months ago, # |   0 when will tutorial soln for educational contest will come
•  » » 8 months ago, # ^ |   0 After the Hacking Phase
 » 8 months ago, # |   0 How to solve D?
•  » » 8 months ago, # ^ |   0
 » 8 months ago, # |   0 How to solve G?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +3 D̶&̶C̶ ̶D̶P̶ ̶o̶p̶t̶i̶m̶i̶z̶a̶t̶i̶o̶n̶ I'm actually not sure(there is no editorial for task, so I wrote what i remembered it was), thx for pointing it out
•  » » » 8 months ago, # ^ |   +8 Are you sure that it is D&C DP optimization? I thought for a while, but it doesn't look like D&C working there. And much more people would solve it in this case.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 It looks like Convex hull Trick https://codeforces.com/contest/1175/submission/55157777
•  » » » » 8 months ago, # ^ |   +3 Thanks for pointing out :)
•  » » » » 8 months ago, # ^ |   +3 I tried to solve it using D&C DP and got wrong answer on test 4. Any idea why D&C DP doesn't work on this problem?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +35 I have an $O(NKlog)$ solution for G but still havent been able to implement it until now which ruins my rating as always :)So we lets denote $MAX(L, R)$ be the maximum value in the subarray $[L, R]$, and $F(i, j)$ as the minimum weight of splitting first $i$ elements to $k$ subsegments. By that, we have $F(i, j) = min(F(x, j - 1) + MAX(x, i) * (x - i + 1)))$ for every $x ≤ i$.Lets have an observation:We can separate $(i - x + 1) * MAX(x, i)$ to $(i - 1) * MAX(x, i) - x * MAX(x, i)$. As always, we will have some data structre like Convex Hull or Lichao Tree to query for the minimum $w* MAX(x, i) - x * MAX(x, i) + F(x, j - 1)$ for $w = i - 1$.Now, normally, one will always think of idea of iterating elements from left to right, maintaining the stack of maximum elements and trying to do something about deleting and pushing elements to that stack. As every time $MAX(x, i)$ changes, we will need to reset our Convex Hull or Lichao Tree over again. Lets fix $i$. Now our stack will represent the changes of the $MAX(x, i)$ if we iterates $x$ from $i$ to the left. And for every fixed $k$, the elements that satisfy $MAX(x, i) = k$ lies on a continuous subarray. So my main idea is for each $k$, i will first find the $x$ that minimizes $-x * k + F(x, j - 1)$ before we actually inserting it to our Lichao/Convex Hull. To do this, you can think of an segment tree which each of its node has a Convex Hull or Lichao tree to take this query. And we will use Convex Hull in this case. If we notice that every time we try to change the $MAX$ of some subarray by deleting some elements from our stack, their $MAX$ only gets bigger and bigger. So if we use Convex Hull, we can actually handle queries in $O(1)$ by using the pointer trick instead of binary searching. Now once we get the best $x$ for our $k$, we will insert a line $(k, -x * k + F(x, j - 1))$ to our Lichao Tree and take queries later. But another thing to notice is that if some elements are poped out from our stack, the Lichao tree should also be changed. But luckily, only the top elements are deleted from our stack so its prefix is still the same. Here, we can use a persistent Lichao Tree to handle this case. So my time complexity is actually $O(NKlogC)$ for building the segment tree of ConvexHull and $O(Nlog)$ memory for having a persistent Lichao Tree.Since this solution is pretty much disgusting, I hope its not author's solution. But i dont want his solution to be $O(Nkloglog)$ either cause I didn't expect it to pass and spent all my contest thinking of a better (not the one above lol) one.
•  » » » 8 months ago, # ^ |   +15 "...I hope it's not the author's solution..." - Your hope is futile.On the other hand, I was sure, that there would be much better solutions.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +29 Here's a similar solution but maybe easier to implement.Denote $D_{i, j}$ as the minimum cost to split prefix $i$ to $j$ subarrays. we fix $j$ and solve the layer in $\mathcal{O}(n \log n)$.We compute the answer for all $i$ in a D&C fashion; to compute the answer for all $l \le i \le r$, first recursively solve for $[i, m], [m + 1, r]$ where $m = \frac{l + r}{2}$, and then we consider transitions between the two halves.define $A_i = \max(a[m+1...i]), B_i = \max(a[i...m])$, the transition is$D_{i, j} = \min_{k \le m} (D_{k, j-1} + (i - k) * \max(B_k, A_i))$Notice that due to monotonicity of $A, B$, for fixed $i$ there is a suffix of the first half where $A_i$ is larger, and a prefix where $B_j$ is larger. We can solve both cases independently;$D_{i, j} = \min_{k \le m} (D_{k, j-1} + (i - k) * A_i) = \min_{k \le m} (D_{k, j-1} - k * A_i) + i * A_i$We have a linear function inside (for constant $k$), so we can maintain those in a cht. When we increase $i$, the suffix in which $A_i$ dominates increases, and we repeatedly add functions with smaller slopes, so we can do this in $\mathcal{O}(n)$.The case when $B_k$ dominates is almost identical, same analysis.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +14 Here's another boring solution.As many said, DP formula should be like $dp(i, R) = \min(dp(i - 1, L - 1) + (R - L + 1) \cdot \max(a_{L}, a_{L + 1}, \ldots, a_{R}))$ $(L \leq R)$.Now let's rewrite this formula using $a_{M}$ $(L \leq M \leq R)$ as any maximum element in that subarray, and then we can boost the transmitting process of $L \to M$ and $M \to R$ separately.Denote $[left(M), right(M)]$ as the maximal subarray that contains $a_{M}$ as its maximum element. For each $M$, we first calculate $f(M) = \min(-(L - 1) \cdot \color{red}{a_M} + dp(i - 1, L - 1))$ $(left(M) \leq L \leq M)$, and then we update $dp(i, R)$ $(M \leq R \leq right(M))$ by $(a_M \cdot \color{red}{R} + f(M))$.In both parts, we only need to answer the minimum inner product for a query 2D vector (e.g. $(a_M, 1)$ or $(R, 1)$) with one vector (e.g. $(-L + 1, dp(i - 1, L - 1))$ or $(a_M, f(M))$) selected from a certain set.To implement easily, we can maintain two segment trees of convex hulls offline. Since we don't need to support insertion and query for segments simultaneously, and we can sort the points in increasing order of the first coordinate, we can solve the problem in $\mathcal{O}(n k \log n)$.
•  » » » » » 5 months ago, # ^ |   0 I don't know how to work without supporting insertion and query for segment simultaneously. For answering $f(M)$ , we need to know the minimum inner product, it can be solved by working binary search on segment tree with $O(log^2n)$. And for updating $dp(i,R)$ , we need to maintain a set by stack and use Li Chao tree with the same complexity. I can't understand how to solve this problem by sorting the point:(
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +8 Let's maintain two SegmentTrees, in which each node stores the convex hull of a set of points. By doing insertions and queries offline, we can insert points in increasing order of the first coordinate (which means you only need to append points at the end of each hull) and then resolve query points in increasing order of the first coordinate, which means you only need to calculate the inner product between each query point and the point at the end of each hull (and drop useless points when it's necessary). Note that we avoid any binary search by doing things offline.The outline is like this: insert all points obtained from $dp(i - 1, \ldots)$; query all points needed to calculate $f(\ldots)$; insert all points obtained from $f(\ldots)$; query all points needed to calculate $dp(i, \ldots)$. Here is my submission: 55180395
•  » » » » » » » 5 months ago, # ^ |   0 Oh! I get it! Thank you so much!
•  » » 8 months ago, # ^ |   -19 It can be solved with ordinary segment tree. With time complexity O(NKlogN). Our dp will dp[k][n], where k is number of groups, and n is representing last added to some group. Now let's focus on solving only one dp layer in terms of group. Update segment tree by setting cost of each index to value of dp[prevgroup][that_index]. Now iterate from left to right, suppose that we are at index i now. Each index will have some cost in segment tree. Now our reccurence will be dp[i] = min dp[j] + cost(j,i). This can be easily found if we can calculate efficiently cost(j,i). Instead of calculating it each time, we will somehow update it efficiently. We can do so by grouping elements by maximum element from them to our i. Now one can see that when moving right, we can find where this element represents maximum. And set it as maximum for new group, while deleting previous groups that those elements belong to. Only thing that is left is that maximum is multiplied by length. We can handle this again by segment tree arithmetic progression update (it can be found easily on net, i am lazy to write about it now). I hope i helped.
•  » » » 8 months ago, # ^ |   0 It seems like there will be a problem to combine operations "add arithmetic progression to a segment" and "find minimal value on a segment".
 » 8 months ago, # |   +1 why ternary search is not correct for problem C? i am getting WA on test case 2.
•  » » 8 months ago, # ^ | ← Rev. 5 →   +1 Ternary search (to find crest) holds good for a function whose value keeps on decreasing till some point, then keeps on increasing.
 » 8 months ago, # |   0 Why my this solution for B is failing on test 8 . Solution
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 your answer bigger than 2^32 so you should puts OVERFLOW!!!
•  » » » 8 months ago, # ^ |   0 As you can see I am putting it when x > mx .
•  » » 8 months ago, # ^ |   0 seems that u need to judge if no>0 when adding to ans
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 But when no > 0 sum will be ~1e15 so I think there is no need to do it .By the way I'll see . Thanks for your time .
•  » » 8 months ago, # ^ |   +1 you missed a few cases while handling your 'no' variable, just made required changes 55178901
•  » » » 8 months ago, # ^ |   0 Thanks Bro .
 » 8 months ago, # |   +5 What is the hacking penalty and profit for Educational round?
•  » » 8 months ago, # ^ |   +1 There is no direct addition in score on hacking a problem in Educational Round but it seems quite a good debugging practice
 » 8 months ago, # | ← Rev. 2 →   +3 Can anyone help what's wrong in this submission for Problem B. 55174319 Thank you!
•  » » 8 months ago, # ^ | ← Rev. 5 →   0 I think your solve WR, in test:10 add for 1 add for 4 end for 1 add end add endThe answer is 4 but in your sol is 7you can refer my solve https://codeforces.com/contest/1175/submission/55139309
•  » » » 8 months ago, # ^ |   0 got it! Thank u very much.
 » 8 months ago, # |   +50 Not good screencast with commentary
 » 8 months ago, # |   +3 What is hacking test case for B)?
 » 8 months ago, # |   +7 Why there are so many hacks in B? Weak Test Cases?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +13 code which loop through vector/stack every time they add the number can cause TLE.the test case looks like this. 100000 for 1 x 10000 add x 80000 end x 10000 mine got hacked too :)
 » 8 months ago, # |   +5 I saw some of the solutions for F rely on the fact that the answer will not be too large. Does anyone want to give a proof/intuition on that?
•  » » 8 months ago, # ^ | ← Rev. 3 →   +54 Let a valid subarray be $a_{l}, a_{l + 1}, \ldots, a_{r}$.Observation 1: Pick up all the elements of value $1$. For every two adjacent elements $1$, denoted by $a_{x}$ and $a_{y}$, if $l \leq x$, then it must be held that $x \leq r < y$.More generally, for every three adjacent elements $1$, denoted by $a_{x}$, $a_{y}$ and $a_{z}$, $x < l \leq y$ must lead to $y \leq r < z$.Observation 2: Let's fix the position of value $1$ as $a_{k}$ ($l \leq k \leq r$). Without loss of generality, we assume the position of value $(r - l + 1)$ is on the right of $a_{k}$, and then we can conclude the only one possible $l$ by enumerating $r$, as we know $l = r + 1 - \max(a_{k}, a_{k + 1}, \ldots, a_{r})$.Consequently, there are at most $2 n$ possible subarrays that we need to check if the elements in each subarray are distinct.
•  » » » 8 months ago, # ^ |   +8 I get it. Thank you so much!
 » 8 months ago, # | ← Rev. 2 →   +30 Why this solution of D is wrong? Take the cut $[ k, n ]$ and find maximum suffix of it, $[ l, n ]$. Increase answer by the sum on $[ l, n ] * k$. Then find the maximum suffix of $[ k-1, l-1 ]$ and so on. In the end, if there some elements in the beggining of the array, which weren't counted in any suffix, also add them to answer. We can do all this with the segment tree in $O ( ( n + k ) \log n )$.
•  » » 8 months ago, # ^ | ← Rev. 5 →   +15 6 3 -1 -2 -10 4 5 6I probably did the same mistake as yours.
•  » » » 8 months ago, # ^ | ← Rev. 3 →   +14 _____I MADE A DUMB MISTAKE SORRY______
•  » » » » 8 months ago, # ^ |   +7 Correct ans is 28.[-1,-2,-10][4][5,6]
•  » » » » » 8 months ago, # ^ |   +14 Oh, yeah that makes sense. Thank you!
 » 8 months ago, # |   0 please anyone explain for problem C if t=1 n=3 k=2 a[]={ 1 , 2 ,5 } how answer is 3 thanks in advance
•  » » 8 months ago, # ^ |   0 The points are 1,2,5 Let us pick our point as 1, so the distance from 1 to all the given points in sorted order is 0,1,4 For 2 it is 0,1,3 For 3 it is 1,2,2 For 4 it is 1,2,3 For 5 it is 0,3,4So we can see that, for 3 we have the minimum (k+1)th distance.
•  » » » 8 months ago, # ^ |   0 thanks i was trying to print Kth mimimum distance instead of for what value of x Kth value will be minimum.
 » 8 months ago, # |   0 55182007 (Problem B) Why do I get a runtime error? It works just fine on my system.
•  » » 8 months ago, # ^ |   0 Hey, I guess when the first add operation is executed, the size of your vector v is 0.
 » 8 months ago, # |   0 Can you tell me why it gives WA in test 9? https://codeforces.com/contest/1175/submission/55166598
 » 8 months ago, # |   0 Was I the only person who felt B was trouble-some and spent more time on it compared to C and D?
 » 8 months ago, # |   0 Could someone tell me why I will get WA in T5? Thansk. 55187500
•  » » 8 months ago, # ^ |   0 Actually lld has max capacity of 10^18 and that would pass when 100 would be multiplied greater then 9 times, and thus surely in test case 5, the case is that only, I did the same mistake
•  » » 8 months ago, # ^ |   0 The problem is in this part:if(tmp*x>=LIMIT){ cnt++; }what if there is no add inside the loops, but you still increase cnt and print overflow.
•  » » » 8 months ago, # ^ |   0 But I solve this case like: else if(str=="end"){ if(cnt>0) cnt--;
•  » » » 8 months ago, # ^ |   0 I think I am so stupid that I will ignore the x of input,if cnt>0 :(
 » 8 months ago, # |   +4 At first, there was a legend related to the name of the problem, but now it's just a formal statement.Does someone know about that legend?
•  » » 8 months ago, # ^ |   0 Iron man
 » 8 months ago, # |   +10 editorial?
•  » » 8 months ago, # ^ |   0 I'm waiting for it, too.
 » 8 months ago, # |   0 In problem B it was specified "x is an integer variable and can be assigned values from 0 to 2^32−1" so doesn't it means the range of x is [0,2^32-1] and the number 2^32-1 should be included or my English is just bad?
•  » » 8 months ago, # ^ |   0 Yes, both 0 and 2^32-1 are included.
•  » » 8 months ago, # ^ |   0 Yes, 0 and 2^32-1 should be included.
 » 8 months ago, # |   0 My Submission got accepted during the contest 55132811 but after the contest ended the status changed to Compilation error. I checked the same code on custom invocation and it compiled without any errors. What the heck is going on!! Can somebody explain?
•  » » 8 months ago, # ^ |   0 Even submitted the same code 55191358 and it got accepted. :/
•  » » 8 months ago, # ^ |   0 It will be fixed today.
•  » » » 8 months ago, # ^ |   +8 It hasn't yet. :(
•  » » » 8 months ago, # ^ |   0 Not till today. :^)
 » 8 months ago, # |   +3 Ok, feels lucky for being expert again :^)
 » 8 months ago, # |   0 Hello everyone! Answer me please. Why is my solution for C getting TL? What's wrong? https://codeforces.com/contest/1175/submission/55161342 Please, help)
•  » » 8 months ago, # ^ |   0 Looks like slow output, check for fast java input output methods.
 » 8 months ago, # |   0 Help!! Could someone please explain how to solve C what does ar[i+k]-ar[i] even mean;
•  » » 8 months ago, # ^ |   0 In my opinion, it's because the first k value will be generated in a[i] ~ a[i + k] intervals.
•  » » 8 months ago, # ^ |   0 To answer on task's question you should find the smallest interval which include exactly k points. My submission: 55152560
 » 8 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 8 months ago, # |   0 Any hint for F?
•  » » 8 months ago, # ^ |   +13 (l,r) is a subpermutation iff r = max(l,r) + (l-1) and all values in(l,r) are unique. so we try to find out how many valid l are there for a fixed r, and this can be done by a segment tree with lazy propagation
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 Can it be solved via BFS? Start bfs at each 1 with state (i,i+1), from (l,r) next state is (l-1,r) if a[l-1] == r-l+1 and (l,r+1) if a[r+1] == r-l+1. Increase answer by 1 for each state reached. Bound is number of permutations, which should be much less than N^2.
•  » » » » 8 months ago, # ^ |   0 I don't think, it can be solved by BFS .
•  » » » » » 8 months ago, # ^ |   0 You're right, I missed the statement by a mile.
•  » » » 8 months ago, # ^ |   0 Can you explain how to find number of valid l for a fixed r using segment tree with lazy propagation
•  » » » » 8 months ago, # ^ |   +3 If all values are unique in range (l,r) then r <= (l-1) + max(l,r). Its equal only when (l,r) is a subpermutation. So for a fixed index r, in each l such that l<=r we need to have (l-1)+ max(l,r), and in each node of segment tree we need to store the minimum in that and a count denoting in how many indices that minimum occurs. As you go right and your r changes, the max (l,r) for some l is changing. You can maintain the maximum with the stack technique. And in segment tree you need to handle that with lazy propagation. You can have a look at my code for a better understanding. 55194670
 » 8 months ago, # |   0 Can someone help me find the problem with my code for problem B ?
•  » » 8 months ago, # ^ |   0 The value val should be (1<<32) — 1 instead of just (1<<32) . Read problem statement to sure
•  » » » 8 months ago, # ^ |   0 Thanks for reply. But, I used '>=' to check for overflow considering that.
 » 8 months ago, # | ← Rev. 4 →   0 Can anyone explain why it is giving wrong answer on test case 8 in problem B? My submission-55198130
•  » » 8 months ago, # ^ |   0 Read a bit above . Mb it will help you
•  » » » 8 months ago, # ^ |   0 I have applied the overflow condition whenever I am adding but still I cannot understand why I am getting wrong answer on test case 8
•  » » » » 8 months ago, # ^ |   0 if(checker>(int)pow(2,32)-1) . Here is your problem.
•  » » » » 8 months ago, # ^ |   0 sarthakoherwal, your code will fail for this test : 4 for 2^32-1 add end addYou have to apply additional overflow check in the else if loop after the line 'x+=checker'
•  » » 8 months ago, # ^ | ← Rev. 3 →   0 are you checking for if( x > (int) pow(2,32) - 1 )` then cout<<"OVERFLOW" ?
 » 8 months ago, # |   +7 where is editorial ??
 » 8 months ago, # |   +3 Why isn't the editorial out yet?
 » 8 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 8 months ago, # |   0 When will tutorials come ?
•  » » 8 months ago, # ^ |   0 Actually, I have the same quation(
•  » » » 8 months ago, # ^ |   0 it has came finally :)
 » 8 months ago, # |   0 Why the problems of these latest contests are not tagged their difficulty pointers?( e.g. *1500, *1200 etc) Does anybody know the reason?
 » 5 months ago, # |   0