By PikMike, history, 5 weeks 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 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:

Hello Codeforces!

We hope your summer is going well!

Last Friday we finished the second edition of the Tech Scouts Summer Camp, with 70 participants, 20 different nationalities and many solved problems. We had 6 participants with a full scholarship thanks to the collaboration between Harbour.Space and Codeforces and we are working on increasing this number next year.

We would also like to remind you that we offer scholarships for our technical programmes, such as Computer Science, Data Science and Cyber Security.

They 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 HERE→

UPD2: There will be 6 problems in the contest.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Um_nik 6 111
2 Golovanov399 6 174
3 PinkRabbit 6 190
4 dreamoon_love_AA 6 198
5 _twilight 6 232
6 HIR180 6 252

Congratulations to the best hackers:

Rank Competitor Hack Count
1 greencis 122:-29
2 Ali_Zaiback 26
3 racsosabe 22:-7
4 plusplus6408 14
5 Flamire 14:-3
6 crvineeth97 13:-2
397 successful hacks and 420 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A dorijanlendvaj 0:01
B Um_nik 0:04
C beefman 0:06
D Um_nik 0:12
E Benq 0:11
F Um_nik 0:31

UPD3: Editorial is out

• +172

 » 5 weeks ago, # | ← Rev. 2 →   +19 Hope that Pretest can be strong this edu round. (I'm so afraid of fst). :D
•  » » 5 weeks ago, # ^ |   +10 But usually,Educational Contests have weaker pretests on purpose.Maybe to let some coders who are new to Codeforces be familiar with "hacking"
•  » » » 5 weeks ago, # ^ |   +17 Pikmike said that he intended to have as few hacks as possible
•  » » » » 5 weeks ago, # ^ |   +4
•  » » 5 weeks ago, # ^ |   +2 I am also afraid of fst.
 » 5 weeks ago, # |   +30
 » 5 weeks ago, # |   -89 Typically for educational rounds (and for this one in particular), is the intention to have strong pretests to try to prevent failing systests, or to have weak pretests to encourage hacking?Just trying to get a sense for how much I should trust the pretests tomorrow. :)
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +98
•  » » » 5 weeks ago, # ^ |   -19 You copy this photo too
•  » » » » 5 weeks ago, # ^ |   0 Yes you and he copy
•  » » » 5 weeks ago, # ^ |   -6 your rate will be Legendary grand Meme Master(I am just Joking :D)
•  » » 5 weeks ago, # ^ |   +4 Is this an attempt to get upvotes?
•  » » 5 weeks ago, # ^ |   +26 LOL, thanks for looking out for my content creation, team. :)
•  » » » 5 weeks ago, # ^ |   +21 woah your shirt changing color with rating xD
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +32 Glad you like it. :)The original shirt was actually blue, but the purple and orange are edited.
•  » » » » » 5 weeks ago, # ^ |   +23 I hope you will put on the red shirt soon :)
 » 5 weeks ago, # | ← Rev. 3 →   -33 Nice
 » 5 weeks ago, # |   +5 Is it truth, that educational contests are a bit easily than usual div2?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +17 It depends whether a participant knows theory well
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +8 Genarally I find them easier because they don't put a troll case like what they do in some normal div2 rounds
 » 5 weeks ago, # |   +39 A user enters the club of young explorers and says: "I am here for the first time". Music stops, and the main young explorer comes to him and answers: "You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post."
 » 5 weeks ago, # |   -32 Round 69. The name itself a MEME
•  » » 5 weeks ago, # ^ |   0 I feel like this MEME gonna get me turn into pale blue again :>>
•  » » 5 weeks ago, # ^ |   +32 Such comments should get 69 downvotes for ruining the decorum of this platform
•  » » 5 weeks ago, # ^ |   +2 you are really naughty!!
•  » » 5 weeks ago, # ^ |   +54
 » 5 weeks ago, # | ← Rev. 2 →   +44 Roses are red, violets are blue,Wish you a high rating, and hacking points too! xD
 » 5 weeks ago, # |   0 Nice
 » 5 weeks ago, # |   +16 Hope I can become a candidate master after the contest.I only need +21
•  » » 5 weeks ago, # ^ |   +6 I hope your nickname to change to purple.
•  » » 5 weeks ago, # ^ |   +5 i believe in you, come and get it.
 » 5 weeks ago, # |   +4 Hope that the statement of the problems is very short and easy to understand. :D
•  » » 5 weeks ago, # ^ |   -16 Me too. My English is poor, and the LaTeX in the problems makes them difficult to be translated in Baidu Translator.
•  » » » 5 weeks ago, # ^ |   +8 Are you sure you are from Nanjing Foreign Languages Institute?
 » 5 weeks ago, # | ← Rev. 2 →   -49 AgainPretest needs to be strong.Accepted needs to appear more.TLE should not appear.And no Queueforces or Typeforces or Hackforces or Speedforces please.
•  » » 5 weeks ago, # ^ |   +8 You should not tell people what to do!! I smell downvotes coming your way
 » 5 weeks ago, # |   +5 Every time I take part in educational rounds I couldn't solve problem D out.But in normal round I can solve it (but somtimes fst XP).Ah, wish all would solve D this time!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -8 congratulations !! how did you solve d?
•  » » » 5 weeks ago, # ^ |   0 YES!!! Hope no fst!
•  » » » » 5 weeks ago, # ^ |   -8 what was your approach to solve it?
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +17 My English is poor sry.An O(nm) solution:Let dp[i][j] be the maximum cost when choosing a[i] as the end of a subarray and the length of the subarray is n (n mod m == j).So when j = 0 ,dp[i][j] = dp[i — 1][m — 1] + a[i];when j = 1 ,dp[i][j] = max(a[i] ,dp[i — 1][j — 1] + a[i]) — k;else dp[i][j] = dp[i — 1][j — 1] + a[i]The answer is the maximum of the dp array.
•  » » » » » » 5 weeks ago, # ^ |   0 why？Could you post a blog? I'm going to study in your blog， thanks.You can just publish it in Chinese.I am also a Chinese competitor.
•  » » » » » 5 weeks ago, # ^ |   0 And it's nearly 1 am in China, I have to go to bed so I can't leave more details. Bye.
•  » » » » » » 5 weeks ago, # ^ |   0 Thanks! amazing solution. Good night.
•  » » » » 5 weeks ago, # ^ |   0 Hi,what is fst?
•  » » » » » 5 weeks ago, # ^ |   +10 FST is short for 'fail system tests'. In Codeforces-format contests, tests are split into pretests and system tests. Before the contest ends, submissions are judged with pretests. Then the latest submissions with 'Passed Pretests' verdict will be judged with system tests, which are stronger. FST means that your submission passed the pretests, yet failed during system testing.
•  » » » » » » 5 weeks ago, # ^ |   0 Thank you I understand it now :)
 » 5 weeks ago, # |   -120 Is it rated? Is pretest strong? Is system test quick? Is TLE rare? Is statement short? Is Editorial ready right after the contest? Is it Hackforces or Queryforces or neither?Is it rated? Is pretest strong? Is system test quick? Is TLE rare? Is statement short? Is Editorial ready right after the contest? Is it Hackforces or Queryforces or neither?Is it rated? Is pretest strong? Is system test quick? Is TLE rare? Is statement short? Is Editorial ready right after the contest? Is it Hackforces or Queryforces or neither?Is it rated? Is pretest strong? Is system test quick? Is TLE rare? Is statement short? Is Editorial ready right after the contest? Is it Hackforces or Queryforces or neither?
•  » » » 5 weeks ago, # ^ |   +8 "I don't know." * 7 * 20.
•  » » » » 5 weeks ago, # ^ |   +17 It's so long that I don't want to count how many questions there is.
•  » » » » » 5 weeks ago, # ^ |   +16 Maybe INF.
•  » » » » » 5 weeks ago, # ^ |   0 200 copies of each. The guy really did an excellent job.
•  » » » » » » 4 weeks ago, # ^ |   0 I don't want to see it again... I'm curious and click... Then my computer...
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Are you a repeater or something?
•  » » » » » 5 weeks ago, # ^ |   -83 Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am.
•  » » » » 5 weeks ago, # ^ |   +5 you can compress it as for(i=0;i<200;i++) { cout<<"Is it rated? Is pretest strong? Is system test quick? Is TLE rare? Is statement short? Is Editorial ready right after the contest? Is it Hackforces or Queryforces or neither?"<
•  » » » » » 4 weeks ago, # ^ |   0 But maybe that comment is easier to send and harder to read than this one.
 » 5 weeks ago, # |   -19 Early editorial for my bois:https://en.wikipedia.org/wiki/Kama_Sutra%27s_algorithm
 » 5 weeks ago, # |   0 Waiting for another queryforces
•  » » 5 weeks ago, # ^ |   +41
•  » » » 5 weeks ago, # ^ |   +1 Is it a problem to solve query problems or what? I just don't get it)
•  » » » » 5 weeks ago, # ^ |   0
•  » » » » » 5 weeks ago, # ^ |   0 I meant why people don't like query problems. Is it hard/uninteresting or smth else to solve them?
•  » » » » » » 5 weeks ago, # ^ |   0 A query problem is harder than other problems. It makes the time close.
•  » » » » » » 5 weeks ago, # ^ |   0 As for me query problems are actually much less interesting(exept the query problems that can be solved off-line)
•  » » 5 weeks ago, # ^ |   +8 What does queryforces mean?
•  » » » 5 weeks ago, # ^ |   +7 It means rounds with a query problem.A query problem means a problem that we have to answer all the queries.
 » 5 weeks ago, # |   +16 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 5 weeks ago, # |   +45 I think the setter got lost making testcase 1 of problem C :p
 » 5 weeks ago, # |   +11 used a linked list for the first time in my life
•  » » 5 weeks ago, # ^ |   0 for which one?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 For B, I think (delete max element and check for max-1, etc)
•  » » » » 5 weeks ago, # ^ |   0 Yep
 » 5 weeks ago, # |   0 How to solve C & D??
•  » » 5 weeks ago, # ^ |   +1 Problem C.Sort the array find all differences of $a_i - a_{i-1}$ and sort them because we need to take away $k$ biggest ones. And choose first $n - k$ differences.
•  » » » 5 weeks ago, # ^ |   0 Why does this work?taking difference?
•  » » » » 5 weeks ago, # ^ |   0 Array is sorted
•  » » » » 5 weeks ago, # ^ |   +3 basically u have to choose k-1 indexes from the array so that k subarray can be formed. now choose those k-1 indexes efficiently as ex. if k=3, so choose 2 indexes ,let it be i & j so cost is a[i]-a[0]+a[j]-a[i+1]+a[n]-a[j+1]. now write these terms efficiently so (a[i]-a[i+1])+(a[j]-a[j+1])+(a[n]-a[0]) now for to minimise this expression ,first two brackets should be min. as last bracket is always constant so sort the array(array of differences of a[i]-a[i+1]) and take 2 values (means if k=3) and then add (a[n]-a[0]).. this is yur minimum answer.
•  » » » » » 5 weeks ago, # ^ |   0 Thanks. It helped in understanding :)
•  » » » » » 5 weeks ago, # ^ |   0 Oh got it..Awesome..How did you develop this approach?
•  » » » » » » 5 weeks ago, # ^ |   +1 by doing algebra
•  » » » » » 5 weeks ago, # ^ |   0 Awesome explaination
•  » » » » » 3 weeks ago, # ^ |   0 Diao!thank you !
•  » » » 4 weeks ago, # ^ |   0 why first n-k???if we need to make k subarrays then the cost of k elements form ai−ai−1 will be needed. No?
•  » » » » 4 weeks ago, # ^ |   0 Logically, because array is sorted, it is like we are merging n — k pairs to make k subarrays
 » 5 weeks ago, # |   +3 Problem #D was very difficult for me... R.I.P my blue dream..
 » 5 weeks ago, # |   +13 How to solve problem D?
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   +70 There is a common approach to find a subarray with maximum sum: construct an array of prefix sums $p$, and find a pair $l, r$ such that $r >= l$ and $p[r] - p[l]$ is maximum possible. To do so, we iterate on $r$ and maintain best possible $l$.Let's modify it for our problem. Suppose $l$ has remainer $x$ modulo $m$. Let's remove $x$ first elements from our array, and search for best $l$ only among those that have remainder $0$ modulo $m$. To maintain that we should subtract $k$ a few times from the result, we may insert some elements equal to $-k$ so we get an array: [ $-k$, $a_1$, $a_2$, ..., $a_m$, $-k$, ..., $a_{m + 1}$, ..., $a_{2m}$, $-k$, $a_{2m+1}$, ...].
•  » » » 5 weeks ago, # ^ |   0 Thank you, I didn't know about this approach with prefix sum. It is really cool, I will study it!
•  » » » » 5 weeks ago, # ^ |   +16 Could you please explain it in detail i am not able to understand it
•  » » » 5 weeks ago, # ^ |   0 During contest i thought of solution using binary search. we want to maximize:p[r]-p[l-1]-ceil(k*(r-l+1),m) so we fix l and binary search on fun(r)=p[r]-ceil(k*(r-l+1),m) for maximum value, but the problem here is p[r] is not suitable for binary search,but we could instead replace it with p2[r]=max(p[r],p[r-1]), index having negative values are not useful,as we could already have our have our maximum on lower size(r-l+1). now we can binary search on fun2(r)=p2[r]-ceil(k*(r-l+1),m). so for each l=0 to n-1,we get our maximum value. is the above solution feasible,could it work.I tried implementing it but was getting TLE.
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 Fixing l and finding correct r value by binary searching is not possible as the values won't be monotonous always... What I mean is f(l, x) > f(l, x+1) < f(l, x+2).
•  » » » » » 5 weeks ago, # ^ |   0 k*(r-l+1)/m is monotonous , and we are making prefix monotonous using pfx2[r]=max(pfx[r],pfx[r-1]), as you may notice considering negative values is not useful,as it will never be considered in max contribution.
•  » » » 5 weeks ago, # ^ |   0 Can someone share code with this solution?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I'm sorry but i don't really understand, how would we iterate over $r$ while maintaining the best possible $l$ ? Is this sort of like kadane's algorithm? I would really appreciate it if you could provide some link regarding this.
•  » » 5 weeks ago, # ^ |   0 using dp i think
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 Why downvotes? It can be solved with DP[i][j] = maximum sum if r = i && (r-l+1)%m = j. 57555709 or is it the same thing BledDest mentioned above?
•  » » » 5 weeks ago, # ^ |   +8 It can be solved with a very simple DP, where DP[i] = maximum subarray ending at index i. Then for the transition we have two choices — the length of the max subarray ending at i is at most m, or it is more than m. First case can be computed in constant time, and for the second case we have DP[i — m] + A[i — m + 1] + ... + A[i] — k.
•  » » » » 5 weeks ago, # ^ |   0 I used a similar approach but my solution got hacked could you help me out find the mistake. Thanks in advancw. Here is my submission 57540812
•  » » » » 4 weeks ago, # ^ |   0 Really awesome idea.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +18 Here's one way to solve it (57526007). Miss the constraint on $m$. Try random shits and fail. Decide to ignore the ceiling function and then fire up a CHT. To avoid fuck up, take the best among nearby $69$ lines suggested by CHT. Arsenal. Profit. Any hack?
•  » » » 5 weeks ago, # ^ |   +17 I don't think it would work if the problem was proposed on Educational Round 1.
•  » » » 5 weeks ago, # ^ |   +91 Hacked it.
•  » » 5 weeks ago, # ^ |   0 I couldn't solve it during the contest but later on, after fixating on the O(M*N) constraint, I solved it like this — If we pick 1 or 2 or .. m-1, in all cases, we have to subtract k while building the solution. So I built the solution by kind of picking bunches of m elements at a time. While iterating from left to right, solution at i represents the best possible subarray ending at i.When you pick m elements at a time, you get two options — 1) Add all m to previous solution at (i-m)2) Leave some (k, ranging from 1 to m-1) gaps in the beginning and start a new optimal subarray from here.At every step, take the maximum of the two available options and keep updating the final answer at each i.My solution
 » 5 weeks ago, # |   +7 Good contest, thanks)How to solve E?
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +19 if ini
•  » » » 5 weeks ago, # ^ |   +13 This is the same idea as to build graph(two adjacent unique values(plus 0) of input in sorted array have edge with weight equal to absolute difference of values, and edges with weight equal to 0 from out_i to in_i) and that you must find number of different ways from larges value to 0 it is easily with Dijkstra.
 » 5 weeks ago, # |   0 Any hint for E?
 » 5 weeks ago, # |   0 What is the 3rd testcase for problem D?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 a testCase with m=11 1 1 2correct output = 1
 » 5 weeks ago, # |   +21 Will the contest be open for virtual participation before the end of the open hacking phase, or will virtual participation only be available after the results are finalized?
 » 5 weeks ago, # |   0 D was a very cool problem to learn about maximum subarray sum
•  » » 5 weeks ago, # ^ |   +1 how to solve D?
•  » » » 5 weeks ago, # ^ |   0 check BledDest's answer above https://codeforces.com/blog/entry/68553?#comment-529245did pretty much the same thing
 » 5 weeks ago, # |   +20 Got confused in A for a long time. Thought we can make new planks by joining other planks :(
 » 5 weeks ago, # | ← Rev. 2 →   0 Can anyone explain the proof of C?
•  » » 5 weeks ago, # ^ |   +5 if you divide the array into k parts, then cost turns out to be : cost = An — A1 — d1-d2-d3....dk-1 where di correspond to difference between consecutive elements in elements at the partition ends: Ex. — 1 2 3 / 5 6 7/ 10 11 12, here d1 = 5-3, d2 = 10-7.So to minimize answer, we need to subtract maximum difference for K-1 differences from An — A1, which can be achieved just by sorting differences.
•  » » » 5 weeks ago, # ^ |   0 Thanks!
 » 5 weeks ago, # |   +1 C was similar to global round 1 (B) quen.
 » 5 weeks ago, # | ← Rev. 4 →   -38 ..
 » 5 weeks ago, # | ← Rev. 2 →   +1 Solve task D, but long type is not enough for result... Send solution (5 min after) with BigInteger and get AC (may be somebody crack my solution, but im really sad).
 » 5 weeks ago, # |   +8 How to solve D?
•  » » 5 weeks ago, # ^ |   0 iterate the remainder $i$ fo $m$, and calculate the every prefix sum $pre[j](i\le j \le n) = \sum_{k=i}^j a[i] - \lceil {j - i + 1 \over m} \rceil$, so the cost of subarray[l...r]=pre[r]-pre[l-1]($l \bmod m = i$), you can find answer by maintaining maxmium pre or minimum pre.
 » 5 weeks ago, # |   +14 Oh. In A, I always thought that two planks can put together to be a longer plank and the second maximum plank can be changed...
•  » » 5 weeks ago, # ^ |   +6 Same here. Was lost in that almost till the end. It might have been a good problem to deal with.
 » 5 weeks ago, # |   0 Is there any point in problem B that input has unique numbers?We cannot hack with repetitive numbers in test case because codeforces says it's invalid.
•  » » 5 weeks ago, # ^ |   0 where ai is the radius of the disk initially placed on the i-th pillar. All numbers ai are distinct.
 » 5 weeks ago, # | ← Rev. 3 →   0 Nice Contest :)
 » 5 weeks ago, # | ← Rev. 2 →   +5 After thinking about subarray sum for a long time and not getting anywhere, I decided to use the ol' divide-and-conquer method to solve D. I've used this "trick" previously to solve a G from another educational round, where the solution was segment tree. Here is the code — https://codeforces.com/contest/1197/submission/57533758
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I think DNC doesn't work because my solution using DNC just got hacked. Did you prove that it satisfies the quadrangle inequality ?
•  » » » 5 weeks ago, # ^ |   0 Well, I mean the divide-and-conquer paradigm, not the dp technique — my technique is similar to merge-sort.
•  » » 5 weeks ago, # ^ |   0 can u explain briefly what have u done!!. - your method seems interesting.. 
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 Alright.This technique in general should work well for places where we want the optimal subarray or so. The function solve(int l, int r) divides the whole array into two parts and checks for an optimal subarray which is a part of either, and in O(n) it checks the subarrays which contains the middle element.Time complexity proof is easy — there are logn divisions and you do each of them in O(n), since the length of each interval is 2^x and the number of intervals are n/2^x. Thus, time complexity = O(nlogn).
•  » » » » 5 weeks ago, # ^ |   0 Isn't the time complexity O(nlogn)?
•  » » » » » 5 weeks ago, # ^ |   0 Corrected.
•  » » 5 weeks ago, # ^ |   0 Those who were asking about the other problem: see my solution here — https://codeforces.com/contest/1107/submission/49050220
 » 5 weeks ago, # |   0 I submited my code and wrong answer. After that, I didn't submit any problem. So will my acount unrate in this contest?
•  » » 5 weeks ago, # ^ |   0 nope, the round will be still rated for you.
•  » » » 5 weeks ago, # ^ |   0 I thought my account would not be rated so i didn'n submit again :((((((((
•  » » 5 weeks ago, # ^ |   +5 I think that if you submit at all, the contest becomes rated for you.
•  » » » 5 weeks ago, # ^ |   0 I think if you submit and it passes pretest 1,then it is rated.
•  » » 4 weeks ago, # ^ |   0 when u submit code with any verdict at anytime in official time of a contest, this means that you will be a participant and u will be rated after the contest also
 » 5 weeks ago, # |   0 I recently started on codeforces and I can only solve 2 problems atmost and after the contest 3rd seems pretty doable but I cant get it right during the contest. My rating is just getting dropped after each contest and that has got me irritated and sad. Any suggestions on how to improve??
•  » » 5 weeks ago, # ^ |   0 You should practice more questions Specially topic wise the topics in which you think/know you are weak at..
•  » » 5 weeks ago, # ^ |   0 I'd say don't worry about your ratings until it stablizes. The initial ratings don't represent much about your skills anyways. On how to improve, you can try learning algorithms and make your own library to use in the future.
 » 5 weeks ago, # |   +5 Any hints in problem F for one line? I know that should by some matrix multiplication.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +60 It's impossible to do it in one line, but I'll try to make it short.When analyzing a combination of acyclic games, we can almost always apply Sprague-Grundy theory. Let's solve the problem with the following dynamic programming: $z[i][j]$ is the number of ways to color $i$ first strips so that the Grundy value of their combination is $j$.To do this, we have to somehow count the number of ways to paint one strip so that its Grundy value is fixed. We can do it with auxiliary dynamic programming: $dp[i][last]$ is the number of ways to color $i$ first cells of a strip so that the tuple $last$ represents the values of Grundy of the last several cells. Since our moves are limited to shifting the chip at most $3$ cells backwards, we have to store only $3$ last Grundy values in this tuple. And since we have at most $3$ different moves, each Grundy value does not exceed $3$, so there are only $64$ different values of $last$ we are interested in.To speed this up, we can skip long uncolored segments by converting the transitions of this dynamic programming into a $64 \times 64$ matrix (let's call it $T$) and using binary exponentiation of this matrix. The common version of matrix exponentiation may be too slow (this solution will work in $O((n + m) K^3 \log A)$, where $K$ is the number of rows in $T$), so we should speed it up. One common way to do it is to notice that every time we need to skip a long uncolored segment, we have to multiply the transition matrix (which is the same every time we need to do so), raised to some power, by the vector of current dp values. So, instead of naively exponentiating $T$, we may precalculate $T$, $T^2$, $T^4$, $T^8$, ..., $T^{2^{30}}$ and multiply the matrices we need by this vector, and it reduces the time we spend on every uncolored segment to $O(K^2 log A)$.
•  » » » 5 weeks ago, # ^ |   +25 Thanks. I mean how to find answer for n = 1 (one line). It is quite detailed explanation.
 » 5 weeks ago, # |   0 What's wrong in this logic for problem C? CodeI used binary search.
»
5 weeks ago, # |
+11

I try to hack one solution of problem 'A' using this code.. But it shows "invalid input". Any Reason??

include <bits/stdc++.h>

using namespace std;

int main() {

cout << 1 << "\n";
cout << 100000 << "\n";
for(int i = 0; i < 100000; i++) {
cout << 100000 << " ";
}
cout << "\n";

return 0;


}

•  » » 5 weeks ago, # ^ |   -33 maybe you should put endl instead of '\n'
•  » » » 5 weeks ago, # ^ |   0 still invalid input
•  » » 5 weeks ago, # ^ |   +3 i think you should give the text not the code
•  » » 5 weeks ago, # ^ |   +23 You put an extra ' ' after the 100000-th number "100000". It's not allowed.
•  » » 5 weeks ago, # ^ |   0 you should remove last space and last endline
•  » » 5 weeks ago, # ^ |   -8 you print a unexpected ' '(space) in the last line
 » 5 weeks ago, # |   0 Problem C was very similar to this problem asked in Global round 1.
 » 5 weeks ago, # |   +3 Why is there one person with so many hacks in problem A?
•  » » 5 weeks ago, # ^ |   +4 I noticed that all hacked submissions in problem A are written in Java, so i think the problem is with sort (in some specific cases it can run in o(n^2) instead o(nlogn)).
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 nice, my solution also hackedMy thinks during 1st task: "Do not use sort, just store 3 maximum elements", but lazy won.Is there some info about worst cases for java Arrays sort?
•  » » » » 5 weeks ago, # ^ |   0 I think that it will run in o(n^2) for arrays that are almost sorted, but i am not certain.
•  » » » » 5 weeks ago, # ^ |   0 As far as I remember, int array in java uses QuickSort, a workaround for this is to use an Integer array which uses MergeSort instead.
•  » » » » » 5 weeks ago, # ^ |   0 Yeah, I found on codeforces forum discussions. Top contest for me (life education), one hacked, other has correct solution but too late because of wrong work with types
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 Well I just got hacked by him, and now my rating is projected to drop 30 points. How lovely :)Btw I used C.
•  » » » 5 weeks ago, # ^ |   0 You got TLE ? If yes it's coz you used inbilt qsort in c whose worst case time is O(n^2) . Either shift to c++ or use your own custom merge sort implementation
•  » » » » 5 weeks ago, # ^ |   0 I don't know how to see if it's TLE or not, but yeah I used qsort
 » 5 weeks ago, # |   +11 From past few contest i keep getting stuck at Problem A , in most cases i was not not able to understand the problem properly , which leads me to huge time loss . Same thing happened to me today . I feel B was pretty easy . Solve it in 10 min using 2 pointer . I tried so hard to become pupil , but i am unable to achieve this simple thing too .
•  » » 5 weeks ago, # ^ |   0 Goddammit, The exact same thing is happening with me too..... last 3-4 contests either i was being complacent or i don't what I am unable to solve A.... B/C are good go's for me from some time now..... Even I want to get out of this newbie rut, but it looks like i have to work hard and solve more, duh!
 » 5 weeks ago, # |   0 Can someone please explain how to approach for Problem E..?Thank you.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +11 Without loss of generality the dolls are ordered such that out_1 <= out_2 ... <=out_nKey observation. Fix j
 » 5 weeks ago, # | ← Rev. 2 →   +1 My A got TLE: link Why? Is this all because I used Java?
•  » » 5 weeks ago, # ^ |   +1 Arrays.sort` uses quicksort for primitives and mergesort for objects. It's possible to hack you with an adversarial case such that quicksort takes quadratic time. You can avoid this by sorting an array of Integer rather than int.greencis got me with this before too — 55176174 :)
•  » » » 5 weeks ago, # ^ |   +20 Wow! I didn't know that. I guess it is the best lesson I could have learned from a div2 A problem.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   -6 I was lucky to learn this lesson by submitting an unofficial solution after Educational Codeforces Round 66 (Rated for Div. 2) ended (I didn't compete in that round) and somehow still getting hacked, so I got the lesson for the low cost of 0 points. :)
•  » » » » 5 weeks ago, # ^ |   0 It seems this lesson is getting more expensive. I did the same thing in C. Go ahead and hack it.I literally screwed up. lol
•  » » » » » 5 weeks ago, # ^ |   +5 Good news, because the adversarial array would have all distinct positive integers and is the differences of the input array, the maximum input size where the input values don't exceed $10^9$ is approximately $N \approx \sqrt{2 \cdot 10^9} \approx 44000$. And it turns out $O(N^2)$ is still reasonably fast for this case. As a result, I think you will not get hacked.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 i know that feel, bro) in my case I also have D task AC 10 min after contest
 » 5 weeks ago, # |   0 I saw many people using segment tree to solve D. Can anyone explain this in more detail? (the whole algorithm) ^^
 » 5 weeks ago, # |   0 When will the rating change due to this competition. Mine is same.
•  » » 5 weeks ago, # ^ |   0 When did usually change? I wonder, too.
•  » » » 5 weeks ago, # ^ |   +9 It usually changes 2 hours after the contest has ended.
•  » » » 5 weeks ago, # ^ |   +11 System Testing is running now. So wait a minute.
•  » » » » 5 weeks ago, # ^ |   0 is it over now.
•  » » » » » 5 weeks ago, # ^ |   0 Yes — It went very slowly.
•  » » » » » » 5 weeks ago, # ^ |   0 Are you able to see your changed ranking. I dont think they have updated the rankings yet.
•  » » » » » » » 5 weeks ago, # ^ |   0 It's changed, and I didn't participated in this contest.
 » 5 weeks ago, # | ← Rev. 2 →   0 why does this binary search approach fail in problem C , I am searching for minimum possible difference almong all the different that will result in k partition. https://codeforces.com/contest/1197/submission/57575150
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Binary search will not work for this problem. Try this testcase:5 21 4 5 7 8Correct ans is 4 by partitioning in the following: [1][4 5 7 8]
 » 5 weeks ago, # |   +13 Good contest ,but...System test and rating change are SOOOOOOOO SLOW!
•  » » 5 weeks ago, # ^ |   0 Are rankings change complete, cause I am not able to see my ratings change.
 » 5 weeks ago, # |   0 How my solution for A was hacked. I did the same as others did.Is there anything to care about in java?
•  » » 5 weeks ago, # ^ |   0 primitive arrays ure quicksort, object arrays use mergesort, so, for sorting, Integer array is better
 » 5 weeks ago, # |   +6 I have a complicated feeling after the contest.Happily,I became an expert again as soon as I wrote this.However,because of my rating,I will be unrated if I participate in the next div3 contest.o(╥﹏╥)o
 » 5 weeks ago, # |   +6 Will Editorial be posted?
 » 5 weeks ago, # |   0 I use my friends written sublime snippet to generate code and as a result some specific codes of us are same and his submission got skipped. I am also learning programming from him.
 » 5 weeks ago, # |   0 I come with something for problem D but I can't develop it to a solution if anyone solves it by the help of the following please tell me:we deal with the array as the blocks, we try each possible one let's call it j from 1 to m, and for every j we try to start from 0 to j — 1 and move by j step to partition the array.it does nothing but I think it could be developed in some way.
 » 5 weeks ago, # |   +3 ..
 » 5 weeks ago, # |   0 Can anyone help me in question D. I am getting TLE on test 3. please describe your approach towards problem.
 » 5 weeks ago, # |   0 Not sure if anyone else did this, but my solution for B actually uses Binary Indexed Trees. https://codeforces.com/contest/1197/submission/57523003
•  » » 5 weeks ago, # ^ |   0 I use DP 57545123 You can see this code (WA because of types), same solution with BigIntger got AC.
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 I have contributed one solution for B Div2 1197B - Pillars 57582495
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 can you explained your approach for solution ... i solved it using concept that , I iterated loop from i=1 to i=n-1 on given array set . and checked that if there exists any a[i] which is smaller than both a[i+1] and a[i-1] , if exists then ans is NO else YES .i saw many people solutions, they approached it in a different way like you . can you elaborate ,what you did???
 » 3 weeks ago, # |   0 Can anyone explain to me what "hacking solutions" means and how to do it please?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Hacking a solution means passing a custom test for someone's submission. If submission and author's code return different answers or any other failure happens then solution is hacked and the authon loses his points.