Hello Codeforces!

On Jul/22/2019 17:35 (Moscow time) Educational Codeforces Round 69 (Rated for Div. 2) will start.

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

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

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

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

Good luck to all 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!*

**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 | PinkRabbitAFO | 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_ZaiBug | 26 |

3 | racsosabe | 22:-7 |

4 | plusplus6408 | 14 |

5 | Flamire | 14:-3 |

6 | crvineeth97 | 13:-2 |

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

Hope that Pretest can be strong this edu round. (I'm so afraid of fst). :D

But usually,Educational Contests have weaker pretests on purpose.

Maybe to let some coders who are new to Codeforces be familiar with "hacking"

Pikmike said that he intended to have as few hacks as possible

Right https://codeforces.com/blog/entry/68338?#comment-526600

I am also afraid of fst.

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. :)

Is this an attempt to get upvotes?

LOL, thanks for looking out for my content creation, team. :)

woah your shirt changing color with rating xD

Glad you like it. :)

The original shirt was actually blue, but the purple and orange are edited.

I hope you will put on the red shirt soon :)

Is it truth, that educational contests are a bit easily than usual div2?

It depends whether a participant knows theory well

Genarally I find them easier because they don't put a troll case like what they do in some normal div2 rounds

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

Round 69. The name itself a MEME

I feel like this MEME gonna get me turn into pale blue again :>>

Such comments should get 69 downvotes for ruining the decorum of this platform

you are really naughty!!

Roses are red, violets are blue,Wish you a high rating, and hacking points too!xDNice

Hope I can become a candidate master after the contest.I only need +21

I hope your nickname to change to purple.

i believe in you, come and get it.

Hope that the statement of the problems is very short and easy to understand. :D

Me too. My English is poor, and the LaTeX in the problems makes them difficult to be translated in Baidu Translator.

Are you sure you are from Nanjing Foreign Languages Institute?

Again

Pretest needs to be strong.

accepted needs to appear more.

TLE should not appear.

And no Queueforces or Typeforces or Hackforces or Speedforces please.

You should not tell people what to do!! I smell downvotes coming your way

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!

congratulations !! how did you solve d?

YES!!! Hope no fst!

what was your approach to solve it?

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.

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.

And it's nearly 1 am in China, I have to go to bed so I can't leave more details. Bye.

Thanks! amazing solution. Good night.

Hi,what is fst?

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

"I don't know." * 7 * 20.

It's so long that I don't want to count how many questions there is.

Maybe INF.

200 copies of each. The guy really did an excellent job.

I don't want to see it again... I'm curious and click... Then my computer...

Are you a repeater or something?

Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am. Yes, I am.

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?"<<endl; cout<<'\n'; }

looks like someone need to learn about loops .....

But maybe that comment is easier to send and harder to read than this one.

Early editorial for my bois:

https://en.wikipedia.org/wiki/Kama_Sutra%27s_algorithm

Waiting for another queryforces

Is it a problem to solve query problems or what? I just don't get it)

https://codeforces.com/blog/entry/68553?#comment-529209

I meant why people don't like query problems. Is it hard/uninteresting or smth else to solve them?

A query problem is harder than other problems. It makes the time close.

As for me query problems are actually much less interesting(exept the query problems that can be solved off-line)

What does queryforces mean?

It means rounds with a query problem.

A query problem means a problem that we have to answer all the queries.

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).I think the setter got lost making testcase 1 of problem C :p

used a linked list for the first time in my life

for which one?

For B, I think (delete max element and check for max-1, etc)

Yep

How to solve C & D??

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.

Why does this work?

taking difference?

Array is sorted

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.

Thanks. It helped in understanding :)

Oh got it..

Awesome..

How did you develop this approach?

by doing algebra

Diao!

thank you !

thank you sir for this crystal clear explanation.

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?

Logically, because array is sorted, it is like we are merging n — k pairs to make k subarrays

Problem #D was very difficult for me... R.I.P my blue dream..

How to solve problem D?

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}$$$, ...].

Thank you, I didn't know about this approach with prefix sum. It is really cool, I will study it!

Could you please explain it in detail i am not able to understand it

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.

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

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.

Can someone share code with this solution?

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.

using dp i think

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?

It can be solved with a very simple DP, where

DP[i]= maximum subarray ending at indexi. Then for the transition we have two choices — the length of the max subarray ending at i is at mostm, or it ismore than m. First case can be computed in constant time, and for the second case we haveDP[i — m] + A[i — m + 1] + ... + A[i] — k.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

Really awesome idea.

Here's one way to solve it (57526007).

Any hack?

I don't think it would work if the problem was proposed on Educational Round 1.

Hacked it.

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

Good contest, thanks)

How to solve E?

if ini<outi<10^5 it is easy to solve with dp(int max_out,int is_something_used) which return pair, first value is minimum extra space, second is our answer. We can go to dp(max_out-1,is_something_used) or use some matryoshka to skip from max_out to new_ma_out. Know you can convert all values <10^9 in values <2*(n)<2*(2*10^5). This is a solution which i send and get AC 57544668

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.

Any hint for E?

What is the 3rd testcase for problem D?

a testCase with m=1

1 1 1 2

correct output = 1

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?

D was a very cool problem to learn about maximum subarray sum

how to solve D?

check BledDest's answer above https://codeforces.com/blog/entry/68553?#comment-529245

did pretty much the same thing

Got confused in A for a long time. Thought we can make new planks by joining other planks :(

Can anyone explain the proof of C?

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.

Thanks!

C was similar to global round 1 (B) quen.

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

How to solve D?

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.

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

Same here. Was lost in that almost till the end. It might have been a good problem to deal with.

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.

where ai is the radius of the disk initially placed on the i-th pillar. All numbers ai are distinct.

Nice Contest :)

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

I think DNC doesn't work because my solution using DNC just got hacked. Did you prove that it satisfies the quadrangle inequality ?

Submission : https://codeforces.com/contest/1197/submission/57528146

Well, I mean the divide-and-conquer paradigm, not the dp technique — my technique is similar to merge-sort.

can u explain briefly what have u done!!. - your method seems interesting.. `

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

Isn't the time complexity O(nlogn)?

Corrected.

Those who were asking about the other problem: see my solution here — https://codeforces.com/contest/1107/submission/49050220

I submited my code and wrong answer. After that, I didn't submit any problem. So will my acount unrate in this contest?

nope, the round will be still rated for you.

I thought my account would not be rated so i didn'n submit again :((((((((

I think that if you submit at all, the contest becomes rated for you.

I think if you submit and it passes pretest 1,then it is rated.

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

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

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.

Any hints in problem F for one line? I know that should by some matrix multiplication.

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)$$$.

Thanks. I mean how to find answer for n = 1 (one line). It is quite detailed explanation.

What's wrong in this logic for problem C? Code

I used binary search.

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() {

}

maybe you should put endl instead of '\n'

still invalid input

i think you should give the text not the code

You put an extra ' ' after the 100000-th number "100000". It's not allowed.

you should remove last space and last endline

you print a unexpected ' '(space) in the last line

Problem C was very similar to this problem asked in Global round 1.

Why is there one person with so many hacks in problem A?

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

nice, my solution also hacked

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

I think that it will run in o(n^2) for arrays that are almost sorted, but i am not certain.

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.

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

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 .

Can someone please explain how to approach for Problem E..?

Thank you.

Without loss of generality the dolls are ordered such that out_1 <= out_2 ... <=out_n

Key observation. Fix j<i and consider all arangements such that the smallest matrushka is i and the largest is j, then the arrangement amongst these that minimizes empty space is already maximal with respect to number of matrushkas.

Now we describe a quadratic solution. Let m[i] be the minimum possible extra space in a maximal arrangement such that matrushka i is the biggest matrushka (maximal among arrangements containing only matrushka i and smaller matrushkas). Now let q[i] be the number of such arrangements. We provide a method to calculate all m[i] and q[i] increasingly:

Step 0: initialize m[i] = INF and q[i] = 0;

Step 1: iterate through 1 to i-1 and for each doll j that fits inside doll i do m[i]=min(m[i],m[j] + in[i] — out[j]).

Step 2: iterate through 1 to i-1 and for each doll j that fits inside doll i such that m[j] + in[i] — out[j]=m[i] add q[j] to q[i].

Now, in order to make this nlog(n) instead of quadratic we use a persistent segment tree and an implicit persistent segment tree.

in order to do step 1 we just need a segment tree that saves in position out_j the value m[j] — out[j], and to find the best one that fitst we just query for range (1,in[i])

in order to do step 2 we need persistance, let version T_k of the segment tree only contain the updates of j if out[j]<= k. Then the sum of all the q[j] we need is simply the value stored in position m[i] — in[i] of the tree T_(in[i]).

My A got TLE: link

Why? Is this all because I used Java?

`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 :)

Wow! I didn't know that. I guess it is the best lesson I could have learned from a div2 A problem.

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. :)

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

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.

i know that feel, bro) in my case I also have D task AC 10 min after contest

I saw many people using segment tree to solve D. Can anyone explain this in more detail? (the whole algorithm) ^^

When will the rating change due to this competition. Mine is same.

When did usually change? I wonder, too.

It usually changes 2 hours after the contest has ended.

System Testing is running now. So wait a minute.

is it over now.

Yes — It went very slowly.

Are you able to see your changed ranking. I dont think they have updated the rankings yet.

It's changed, and I didn't participated in this contest.

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

Binary search will not work for this problem. Try this testcase:

5 2

1 4 5 7 8

Correct ans is 4 by partitioning in the following: [1][4 5 7 8]

Good contest ,but...

System test and rating change are SOOOOOOOO SLOW!

Are rankings change complete, cause I am not able to see my ratings change.

How my solution for A was hacked. I did the same as others did.Is there anything to care about in java?

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

Will Editorial be posted?

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.

..

Not sure if anyone else did this, but my solution for B actually uses Binary Indexed Trees. https://codeforces.com/contest/1197/submission/57523003

I use DP 57545123 You can see this code (WA because of types), same solution with BigIntger got AC.

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Can anyone explain to me what "hacking solutions" means and how to do it please?

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.