Hello everyone!

This Sunday July 2, 19:05 MSK rated Codeforces Round #422 (Div. 2) will be held.

This time I'm the only one author in contradistinction to the Round 415. Many thanks to coordinator Alex netman Vistyazh for help in preparations of the round, Vladislav winger Isenbaev, Alex AlexFetisov Fetisov, Nikolay KAN Kalinin and Ildar 300iq Gainullin for testing the problems and also to Mike MikeMirzayanov Mirzayanov for Codeforces and Polygon platforms.

As in the Round 415, the main characters of the tasks will be the stunning girl Noora and hacker Leha.

Participants will be given six problems and two hours to solve them. As always, participants from the first division can take part out of competition. Scoring will be announced before the round.

I hope you'll enjoy my round. I wish everyone good luck and high rating!

**UPD1: Note that the number of tasks which would be proposed for the solution has been changed.**

**UPD2:** The scoring for this round is: **500 — 750 — 1250 — 1750 — 2250 — 2500**.

**UPD3:** Congratulations to the winners! Editorial will be posted soon.

Div. 2:

Div. 1:

Special congratulations to natsugiri, who is the only one among all the participants who coped with all six tasks!

**UPD4:** Editorial.

Really looking forward to this round! //Why always stunning girl Noora and hacker Leha... (codeforces round 415)

N** coincidence, why not? You'll feel like making "Tommy" do all sorts of interesting/ridiculous things if you do more problemsetting.

Is it rated?

Not for you bro

why? why? why? T-T

Why do you talk to yourself? Are you so lonely?

till now yes.

В связи с последними событиями очень актуальный вопрос

I want to ask it too.The past two contests are both unrated!

I'm so tired.

don't worry this time it will be rated and try to learn some new things from each and every contest instead of thinking about ratings and all.

I'd like to go to sleep if this is unrated.Then I will have a virtual contest.

The virtual contest can let me learn some new things too.

Me too.

But,in virtual contest,there is no hacks,no points.

It's a little boring.

UPD:I miscalculated it. I'm so sorry for inconvenience.I think the time and date link is incorrect as it differ from the remaining time.] written in contests page.

Hopefully this time it will be rated ;D

tourist is registered and everyone is excited!

He unregistered!

tourist you're such a troll!

He unregistered now, or he isn't registered basically his last visit was 6 hours ago before which is before the registration opened. Looks like you just want contributing points :D

snowden.exposed

Nice try detective, but that "Last visit" thing doesn't work well.

why would a fake account wants contributing points though?

Then why I can't see tourist in the registration list?

...

He is fond of contribution, I think he comments from this account then upvote his comment form other accounts, as I realized immediately when he write a comment he got +3 or something like this, which gives more chance to upvote him after seeing that tourist is registered and the comment took +22 before checking if he if really registered.

Yes, I upvote my own comments and I also did 9/11.

He ranked 5 in SnackDown 2017 Finals today the 3 top are 1-Um_nik's team 2-anta's team 3-jcvb's team

check Ranklist here

we hope it be rated and no issues during the round after two consecutive unrated round

It's three

Is it unrated?

the answer is after the contest :D :D

Schrödinger's round: it's both rated and unrated until it ends

Two consecutive rounds unrated, i think codeforces should be more cautious！

The last round was just the author's luck though, nothing could have been done to help.

what? having a false solution to a problem is luck? I am not saying the that it is the author's fault, but being cautious does help in such situation, so why do you think that it is luck?

Yes.I think it is a luck because you can learn from it.

I can only imagine the pressure on author.

Round #422=Registration x422

Soon it will be

Round #422=Downvote x422Soon

the blog post ratingwill be422! Great!UPD: It's now +416. Soon it will be 422 or more!Hope this time nothing to be happened to make this round unrated !

I participated in the last two rounds, in spite of Eid occasion. One of them was at the night before Eid day in our country and another was one day after the Eid day. Though my friends and relatives were enjoying and gathering by themselves with other stuffs, I participated in the contest in stead of joining with them, because I love to do contest. But unfortunately both of them became unrated !

I speak through memes.

.

No mistakes in jury's solutions, please

For the First time, i am

NotExcited for Hat-trick .after the round :D

Mike Cameron

Hope that this contest will be bugfree and rated even after contest unlike last twos.

My plan for evening: Mexico — Portugal Contest Germany — Chile

Hope there will be no problem with any of the problems. :-)

GL & HF ?

Hopefully history won't repeat itself...throwback to unrated #420 and #421 :(

Hmmm.. This doesn't look legit :D

From today's contest registration:

Attack on

acloserseason 1++Ban everyone!Is it possible to make User-Id using loop?

If not then that guy had all the time in the world to create these lmao

Codeforces has CSRF and XSS protection which supposedly should prevent anyone from running a script to send data to the server from the outside, so that lad must've had gone through lots of trouble to make those accounts XD

Or he's really smart and he could turn around the system and find some sort of a vulnerability that let him do that.

Either way it took him some serious effort :3

What about selenium?

What about captcha?

don't think codeforces has captcha to make account.

there is a captcha you have to solve immediately after confirming your email.

What's the gain on creating multiple dummy accounts ? Altering the quantity of people that have submitted something wrong, and in that way boosting your rating income?

76 likes, it seems all the acloser liked this.

They are more than 76, you never know.

Hopefully no more server slow problems.

Many thanks to coordinator Alex netman

Has KAN resigned?

No :)

Exciting score distribution :D

My first contest in a long time.. good luck to everyone!

I have faith in pedrodelyra... he is a monster

wow great,after a long time six problems. Hopefully all problem statement will be shortly. Thanks.

Problem A: I shed a tear :'

(no emoji)

Me too.

At most one of the numbers a,b is greater than 12.

I am not able to see the source code for hacking.

You should use glasses Maybe You can see !! :D

WA #3 preliminary test set C. C seems so easy!

So there is a blue rating contestant with four wrong answer verdict submissions in my room and three green rating with five WA's. Seems that the problem is very dangerous. I will wait for the explanation very hard.

It's not the whole test

Test case3 2

1 1 10

2 2 100

3 3 1000

Answer — 110

On my local machine output is 110.

http://ideone.com/OHMWiN

Is there something wrong with hacks of A?

Just lost 50 points due to this.

Pretest 2 D is killing everybody

dp f(i)%=MOD before calculating f(i)*t^(i-l)

How to solve C? I had a O(n*log(n)*log(n)) approach using segment tree and binary search, but I thought it wouldn't pass. Is there a better approach?

I used adjacency list + BS.

Can adjacency list be used to answer rmq?

actually in my approach suffix minimum was sufficient.

me too!

EDIT: failed systests. two pointers

You can sort by difference between l and r (sort by cost in case of equality) and then use two pointers to iterate your array .(runs in

`O(nlog(n))`

)could you elaborate on your approach . I tried this way only . the sorting logic also exactly same but i got WA on pretests.

EDIT: This failed systests. this might help http://ideone.com/BU1KjQ

well, after sorting , you start with i=0 and j=n-1, and while(i<j) if (difference(i)+difference(j)==x) you compare cost(i)+cost(j) to your current answer(initially=oo) and decrement j (j--) (since there can't be a better solution if you increment i). and if (diff(i)>diff(j)) you decrement j and if (diff(i)>diff(j) you increment i. here's my code: https://ideone.com/avXw3e

Use a segment tree with min query and you can do it in O(n*log(n)). You don't need the binary search.

I was using Binary search to find the elements which do not overlap, and segtree to find the minimum in them, I don't know how do I avoid Binary search here?

Use a segment tree with MAX_SIZE positions and put the item on its L. You'll get the ranges (0, current L — other size) and (current R + current size, MAX_SIZE — 1).

I used array of priority queues

What is the hack for div2B?

many people code like this

they don't limit i+n-1<=m

so hack is

I wish someone had hacked me :(

How to solve E ??

How to solve D?

O(nlogn) would be TLE :(Apparently not. I used a prime sieve and submitted at 1:59 and got pretest passed. (if only I had gotten it earlier though...)

WT!!? I thought it will get TLE and didn't submit :((

http://codeforces.com/contest/822/submission/28233115

actually, I think it's O(N), not n log n, my bad. (because the number of primes less than any N approaches 1/N for large N)

Since the prime sieve only has to go from 0 to 3000 (about root 5000000), it doesn't take a long time

Now that I think about it, I have no clue how to calculate the complexity of my code.

A prime sieve is O(nloglogn).

also, even if it was N log N instead of N, it would probably still pass because it only works out to ~120m operations

Mine passed in 1240 ms. Hope it passes system tests too.

Mine too, but it didn't pass systests :(

Mine passed in ~700 ms.. So guess it will run..

F[n] = F[n / x] + (x — 1) * n / 2; Where x is smallest prime factor of n.

Why is the smallest prime factor optimal ?

Idk, maybe because of comparisons sorts you try to split it into less parts and try to get to nlogn rather than n^2.

Let's prove that if you can get p or q such that p * q is a divisor of n you want to get the smallest one. If you get the cost of the p and q operations you'll get:

//pairs(p * q) * n / (p * q) = n * (p — 1) * (q — 1) / 2 this is making p * q

//pairs(p) * n / p + pairs(q) * n / (p * q) = n * ((p — 1) + (q — 1) / p) / 2 this is making p and later making q

After one of those you'll use the best of n / (p * q) so you can ignore it. It is easy to see that (p — 1) * (q — 1) >= (p — 1) + (q — 1) / q always so from this you see that you'll always take prime factors. Now, if p <= q, (p — 1) + (q — 1) / p <= (q — 1) + (p — 1) / q because q — p >= (q — 1) — (p — 1) >= (q — 1) / p — (p — 1) / q so you want to get the lowest.

What?

I got

f(a) = (f(a/sf) + a/sf * f(sf))

where sf is the smallest prime factor of a.

You accomplish this by breaking it into a/sf groups of size sf.

EDIT: Never mind, these both end up giving the same expression.

I got pretests passed for O(nlogn) in 545 ms, hope it passes system tests too...

EDIT: Passed system tests. Phew.

EDIT EDIT: Never mind, looks like my solution wasn't O(nlogn)

When u get problem C and then rejoice but then with 15 mins left get hacked and get sent plummeting down :'(

Hack for C:

2 4 1 2 1 2 3 2

For A, one person in my room explicitly tried to compute the factorials of both A and B. I was unable to hack him for (N, M) = (12, 10^9), because overflow probably led M! to be equal to 0 at the end, but I got him with (N, M) = (11, 30)

Answer should be -1 right?

Yes.

http://codeforces.com/contest/822/submission/28230967

What is wrong with this? Gave WA on Pretest 3.

Also, I hacked 1 brute force solution, and one solution with inf = 1e9(max answer can be 2e9).

Oh I think we should use inf like 0x3f3f3f3f......thruongh this figure,or up to the problem itself.

Start system tests quickly this time please!

May somebody please explain how to solve Problem C without getting "time limit exceeded?" Thanks in advance!

Since the round is done, would anyone mind sharing how they solved C? :(

Loop through all the sorted start and end points and if it's an end point, add the length and cost to your set, and if it's a start point then check all the end points before the current coordinate (in the set) to match the 2 lengths together.

Can u check my solution using Binary Search link: http://ideone.com/hC25Oz

For every length store costs and left border in vector. Then sort these vectors by left side and cost. And for every element do binary search. 28224027

Damn! I never thought to use binary search! That's pretty neat

EDIT: This failed systests. sort by duration of voucher and use two pointers method. works in O(nlogn) due to sorting. it passed pretests, hope it will pass systests as well. http://ideone.com/BU1KjQ

O(n) solution for C: 28224212 It passed pretest. But it didn't passed System test :(

What is your approach?

EDIT: I don't think it could be solved in O(n) you gotta atleast sort man.

EDIT2: Ok I guess it could be done in O(n)

You can sort in O(n) btw.

Yes, but with a very large Constant. I mean ok my bad.

Here is mine O(MAX) solution.

Can you explain it a bit?

Problem D: Was there anyone getting wrong answer in pretest 2 ?? I don't know what's wrong with my code :(

You should check for 32-bit integer overflow

Yes I am using long long int

Have you done the operations MOD 1e9 + 7 ?

Yep, I am also doing the modulo operation. I think I have figured out the problem. Actually , I was miscalculating he f(n) for odd numbers. I was using f(n) = (n*(n-1))/2 for odd numbers. But it seems the correct value is f(n) = f(n/x) + ((n/x) * ((x*(x -1))/2) , where x is the smallest prime factor of n.

It is the same for even numbers

For prime numbers in range, is the only possibility (n*(n-1))/2 ?? (where n is prime number)

let z = small[n], is the smallest prime factor of n, let h = n/z, then ans will be

SpoilerF(n) = ((h*(z*(z-1)/2)%mod)%mod + F(h))%mod

Mod the value of dp[i] or F(i).

I also fell down on the second test. Then I noticed that I forgot my answer by modulo after each addition.

If you are updating f[i] from f[i / p] (where p is the smallest prime divisior of i) and i >= l and i / p < l , f[i] would update incorrectly.

Can anyone explain the solutions of E and F?

Hi, I had an idea with hashings, with some greedy steps for problem E. The general idea is to keep the matched segments in some stack and remove those segments when a better one appears. Below the steps:

*Let's say "size" is equal to the sum of length of your segments in every step. *For every character "i" in string "t", and with current position pos = 0 in "s" do this:

(1)Look for the ith character of "t" in s[pos... n], take the first ocurrence, let's call this position "k" in s.

(2)Check if the largest common suffix of s[1,2,...k] and t[1, 2, ...size + 1] can replaced some stored segments on your stack.

(3)Remove segments of the stack that can be replaced by the largest suffix.

(4)Updated pos, size, Repeat until pos = n

Finnaly if you got the whole string "t" in "s", you will need one aditional check if some substring at the right position of "pos" can be a better suffix for t.

Is suffix array required in E?

suffix array is not necessary

2 minute silence for all those(including me) who initialize maximum answer to 1e9 in C

Idea behind D ?

It can be proved (I simply bruteforced), that at it stage it was optimal to take the smallest group possible.

Given this, you simply computed the answer with help of memoization and a prime sieve to prevent TLE.

Yeah. That is what I want to know. How to prove this ?

I computed 50000 values and it worked. You can easily proof that taking 2 prime numbers is better than taking their product, and then generalize. I haven't written any strict proof but someone might help.

Okay, maybe because we want to keep numerator small, we will greedily choose smallest prime

That's exacty what I said

You have to notice that one prime will never be in divisor. So which prime should this be?

Lets compare it with comparisons sort :D When you do smaller groups you achieve O(nlogn) rather than O(n^2) :D

This is intuition, not proof

Lets say what n=p1p2...p_n. We need to show what we choose p_i in order of i.

I did like this. For any n, the optimal choice is always a prime factor. To prove this, it's enough to prove that its better to choose X for N and then Y for N/X rather than choosing X*Y for N.

F(N) = X*(X-1)/2 * N/X + Y*(Y-1)/2 * (N/X)/Y + F(N/XY) in the first way.

F'(N) = XY*(XY-1)/2 * N/XY + F(N/XY) in the second way.

Its simple to prove F'(N) > F(N) for any X,Y > 1 (Just rearrange the terms, do some math).

But it's not necessary that X and Y will be chosen one after the other. Yes, all of this is very intuitive, but nothing solid.

just in case Rank predictor

Can anyone help me with my code on C...I was getting WA on pretest 5. But I used exactly same logic as people have discussed here. Thank you..

So, in D, is the optimal f(n) simple greedily doing N/2 * [ p1-1 + p2-1 / p1 + p3-1/p1*p2 + ..... + pk-1/(n/pk-1) ] ? I can't formally prove why it will be lowest, although seems like it can be.

F[n] = F[n / x] + (x — 1) * n / 2 Where x is smallest prime factor of n. Lets say n is composite: n=p*q. When F[n] = min(F[n / pq] + (pq — 1) * n / 2,F[n / p] + (p — 1) * n / 2, F[n] = F[n / q] + (q — 1) * n / 2) When F[n/p] = F[n / pq] + (q — 1) * n / 2 When F[n/q] = F[n / pq] + (p — 1) * n / 2 From this you somehow prove that you need to choose first smaller of p, q.

-_-

Actually, number of primes is small enough to take the sum. NlogN. Then you do the multiplication with t^k, 10^6logN.

What a Thrilling Contest!

Anyone with

O(n)solution for C?Mine, if we replace sort with counting sort: 28224166

I belive mine is: 28236057 Edit: although technically it's O (200000+n) I guess

200000+n is still O(n)

i commented and asked why are we not getting ratings and contests added up in our graph ?? and my contributions went to -1

I'm not sure, but if your comment rating is in [-5; 0], cf will show this rating as 0, but will count real rating when calculates contribution

I submitted an nlogn solution for D(I know it can be improved), but currently it doesn't appear on the standings and on the status page, my submission got TLE on test1(wtf). Is there someone else facing a similar problem?

Your solution's complexity doesn't depend on l, r. If your solution runs like 1400-1500 ms it can get tle when rejudged I think.

I think almost in the same way, but it is unfair if you receive tle on test 1, because it shouldn't pass pretest(it would give the possibility to modify my solution, instead of switching to other problem). As you said, my solution doesn't depend on l, r. So, if it pass pretests, it must pass systest, because the computations are almost the same.

It's only a prediction. But if you choose to write solution that runs on edge, I think you are relying on your luck.

Why do they run our code on pretests again?

what is the time needed to calculate the rate?

keeping small numbers as an input in pretests would have given a chance of successful hacking attempt on Question A

No plagiarism detection between DIV 1 participants and DIV 2 participants??.Saw a few same codes.

Although got WA in C due to initializing of maximum answer to 1e9 and D due to some silly mistake but still

best contest in last 1 month ,waiting for more rounds by authorActually, anyone mind sharing what E's test 24 or its general idea is? A lot people get WA'd but the case is too long to be read or copied.

I think this.

`Note that dp[pref1][ans][flag] doesn't work`

That's pretty unexpected. I originally thought about some edge cases, but did not ponder too much on the algorithm. Thanks a lot!

can anyone pls share solution of D?? (I was getting wrong ans on pretest 2 inspite of using the prime numbers concept to form groups)

Didn't see where you're using t. You count not t^0 * f(l) + ..., but 2^0 * f(l) + ...

thanks for pointing that out i will try and resubmit in practice section..

Check your code if there is overflow because of int. At first , I got WA on the pretest 2 too. But after changing "int" into "long long int" , I got AC.

Actually, you can see the test cases here for yourself.

http://codeforces.com/contest/822/submission/28234001 My solution for D, developed minutes after finish of contest (spent whole time trying to solve C). Idea is: to calculate, for example, f[40], maybe optimal is to have 5 groups of 8 people, so using just prime numbers does not work. Firstly, lets set f[x] = x*(x-1). Thats always a solution. Then, lets iterate from i = 2 to i = r/2 + 1. Inside that loop, iterate from j = 1 to j = i. Update f[i*j] : f[i * j ] can be solved in two ways: 1. way either you have i groups and j people in every group, then f[i*j] = i* f[j] + f[i]

( if you cant understand: i times you solve groups of j people, and then you will have i "winners", so you solve one group of i people). Since i and j are smaller than i*j, i and j will be computed by this time. 2. way similar, just opposite, j groups of i people. So f[ i * j ] = max ( i*f[j] + f[i], j*f[i] + f[j], f[i*j] ) Third way if f[i*j] is already better than going with i or j. So you just calculate all values, and then sum from l to r, and must be careful about modulo.

So.. Does D could be solved in C#? It seems I've used asimptotical optimal solution, but it still gets TL.

http://codeforces.com/contest/822/submission/28234265

O(r * min(pr)) not optimal really. O(r) or O(rloglogr) are optimal.

You are right. I should use Eratosfen Sieve, I'm stupid. But I see — on C++ approach that I've used works 1.2 — 1.4 sec, so on C++ the solution of this task is little more obvious.

I can share my divide and conquer approach for E if someone'd like me to :)

Please do :)

ok :D

Let's calculate dp[m][x]: the minimum possible position in S such that it's possible to obtain [0..m] of T using no more than x cuts. If there's no such position, it's equal to -1.

How would we calculate this in a straightforward way? Let's try to brute this optimal position. For a fixed i in S we wanna know the maximum possible length K such that S[i — K + 1..i] == T[m — K + 1..m]. If we can add it without intersections (i.e distance between dp[m — K][x — 1] and j is greater or equal than K), it means we found the answer. This gives us an O(xnmlogn) solution provided we use hashing :)

Let's try to speed it up. It can be easily seen that for a fixed x the dp values are monotonic (till they reach -1). Moreover, if for some i dp[i][x] is equal to -1, that means that for all j >= i dp[j][x] will be -1 aswell.

From these points we obtain the following idea: if there are some given segment bounds (l/r for the dp positions and L/R for the dp values), we take the median m = (l + r) / 2 and check all possible i's in range L..R. If we find the optimum, we call (l, m — 1, L, opt) and (m + 1, r, opt, R). If no, it's no use checking the right part of the segment, so we proceed with (l, m — 1, L, R). This gives us log(n) levels or recursion and no more than m operations per level. Since every check is performed in O(logn) time (binary search + hashing) and there are x calls or divide & conquer, this gives us the total complexity of O(x * m * log(n) * log(n)).

http://codeforces.com/contest/822/submission/28235167

Last part of solution is one of the DP optimizations from next link, right? http://codeforces.com/blog/entry/8219 More precisely, It is divide and conquer optimization? Also, can u explain more briefly how do we use hashing here?

It's similar, right, and uses the same idea, but applied in a bit simpler case since I know that my dp is monotonic and bounded by [0..m — 1] at the same time. This allows me to turn O(mn) into O(mlogn) as described above.

How do we use hashing? Denote lcs(i, j) as largest common suffix of prefixes [0..i] of T and [0..j] of S and use binary search :)

You can actually shave off a factor of log(n), by simply using the observation you mentioned — on the monotonicity of the dp values for a fixed x. We can simply run 2 pointers — one for S from 1..n and the other for T from 1...m. The xth row in the dp table will be computed in (n+m)*(time for computing the latest common suffix) which is log(n) using hashing.

Yes please!

Check the comment above :)

Is there anyone with TLE in C. My complexity was O(nlogn).

yes same here, but i think some corner cases were not being handled by that approach

I solved D without prime factors or anything like that. Just bottom up DP :/ Anyway, anyone thinks that D is far easier than C? I tried to solve C for ages, and I couldnt, but I solved D in pretty short amount of time.

+1 , took me quite some WAs (and a few < instead of >=) and time to get C right, D was in one go, if only I saw D first :(

You approach isn't 100% correct. You use dp[j] that sometimes won't have the best answer at the moment you use it so if the relation was diffent your solution would be WA. It's correct for this problem because of the fact that you need to use the minimal prime factor so you'll end up getting the correct answer.

No. You always calculate in right order. When you want to calculate f [i*j] you will always have f[i] and f[j] because its bottom up approach. Its nothing to do with smallest prime.

Nah... there's more than 1 way of writing i * j. You'll for example get 120 using 1 * 120, 2 * 60, 3 * 40 etc but when i = 3 and j = 40 did you consider the case when i = 10 and j = 4 (that results in 40 and is the j on 3 * 40)?

tfg No. You dont understand my solution, now please try to understand it. My first loop goes from i= 2 to i = r/2 + 1. Loop inside it goes from j = 1 to j = i ! So NEVER it can be that j > i . Because of that, when I come with first loop on some number, it is surely calculated. j is never bigger than i, so I will not have problems like you mentioned.

Im 100% that this is OK.

Can somebody explain me E solution without hashes?

Is it possible to get a particular testcase? I need case 46 of C. WA. http://codeforces.com/contest/822/submission/28232052. Otherwise, if someone helped figuring out why, it would do too!

Got my bug :) But... is it possible to see a whole particular testcase, say, as a .txt file?

Hey, what was the idea of fixing the bug? I'm also using binary search and getting WA at 46:)

Actually I messed up checking upper bound. Check line no 57 there and here. See a difference?

I see, thanks

Any help plz ? C solution

Does anyone else think that the time limit for D was too strict.My solution TLEd on pretest 1 in spite the logic was perfect. :(

Actually, I think it was opposite. I got AC without even proving that it is best to choose smallest prime. I just had DP[x] and bottom up approach, didnt even care about prime factors. It could be more strict so only if you prove optimal strategy you get AC. Still, I think that would be too hard for D tbh.

You did O(n^2)... You should do about O(n) or O(nloglogn)

How is my solution O(n*n) bro?2 nested loops don't always mean its O(n*n)

Your solution about O(nlogn): for each i = [1..N — 4] you do (N — 4) / i iterations.

As it's said above, you need O(n) solution or O(nloglogn).

Yeah my solution is O(nlogn).But even that passes.If I take minimum then everytime its TLE,else its AC. See these two solutions,u can see that just 1 line is commented and that line is making difference.

TLE solution: (http://codeforces.com/contest/822/submission/28235754)

AC solution: (http://codeforces.com/contest/822/submission/28235976)

I always think that if my solution goes for little quicker then TLE, that there is not perfect logic:D

Though if solution passes, who cares? But this solution wouldn't pass in Python or C#. Maybe there must be 1s TLE?

I think the TL is loose. Some solutions with

O(N^{3 / 2}) passed (which is precisely your solution).My solution is O(n log n) just like balalaika said.Its like let x=N-4, x/1+x/2+x/3+.... which is O(x log x).

I keep Getting WA on test 58 on problem C, and i couldn't understand what i did wrong, can anyone please check this submission for me :(

28235829

I used two pointers in C. I had created a pair in map mp[{l,r}]=cst which stores the minimum value of cost from l to r. I had created an array of sets where i inserted l,r as a pair in the r-l+1 th set. After that i used two pointers in the following way : I ran a loop from i=1 to x and i had a pointer pointing to the ith and x-i th set itr and itl respectively. I will check whether the L value of itl is less than or euqal to the R value of itr ,then i will increase itl,else i would compute the answer and increment itr by 1. This is my logic with a few corner cases handled . I trie to run the code on every possible small input in the test file but it passed all of them. Please have a look at it, and let me know my mistake. I am unable to find the mistake in my code. Here is the link to my code. Thank you !

unlucky contest ....

Oh my god , you must be so angry. You have 1899 rating. So close to div1. Man so sorry for you. I am 5 points away from specialist but you are 1 point away from div1.

I had 1898 at some point and now 1899 .... Maybe I'm cursed...

Yeah :D, but it's time for sure you become a div1, you have lots of experience, also during virtual contests you are performing really well.

In problem D, I get wrong output for case 2 in codeforces but right output in home pc and ideone, can anyone point out my mistake . code ideone

I had same problem few times on Codeforces. Trick is, on codeforces, default value for int isnt 0. Maybe on home pc your default value is 0, like on mine. So your array prime[x] is maybe problem. Just set everything to 0 on start. That will fix it, I am 99% sure! (also for other arrays that you have)

fixed wasn't the default value problem , changed type of i from int to long long in solve().

Liked the contest very much, but i don't like when a contest becomes a fast typing one. I knew how t osolve B insantly but i didn't write it fast enoguh and that's why i lost some points. Also why where the pretests for A so easy and for C. I understand that you're giving other contestants posibility to hack but that's not cool. There where people who solved 3 problems and others who solved 2 problems and they where on the same rank just because of hacking. Not cool. But contest was nice in general.

I am really not able to find bug in my code :'(. Can someone please help me! Submission link

I don't know if this is the only problem, but you shouldn't divide an expression by 2 after taking its modulo. Do the division before taking modulo in line 13.

Thanx! I m really tired of doing such mistakes! I think i am going to stay in Div 2 my whole life!

Well, thank you very much!

That moment when you did well last two rounds but fail to do well this time:

Is this gonna be unrated as well? xD

Why am i getting runtime error but i am not getting it in my compiler. Thanks in advance. http://codeforces.com/contest/822/submission/28236678

regarding this submission:

http://codeforces.com/contest/822/submission/28235877

as you see it gives me time limit, isn't this rlogr ?

the nested loops work in a manner like this: r + r/2 + r/3 + r/4 + ..... + r/r, take r common factor, this gives : r(1 + 1/2 + 1/3 + 1/4 + ..... + 1/r), for very large r this summation is just approximately 2.7, so complexity will be approximately 2.7r, do you know why it gives time limit ?

EDIT: the summation is near to log not 2.7

(1 + 1 / 2 + 1 / 3 ... + 1 / n) is harmonic series. Its sum isn't equal to e. It grows like log n. So, as we have 5*10^6, r log r solution may not pass.

yes sorry it is not equal to e i mixed it with another thing, but still at 5 million this series sums up to just 16, why 80 million would not pass ?

It is actually . You solution should pass after removing some unnecessary things, as the Time Limit is tight.

yes i accidentally mixed it with the summation of 1/factorial(i) as i tends to infinity

Just removing some unnecessary mod (it is too costly) and using long long only where it is needed gave AC :P Bad Luck :(

Changed Code — 28237999

Diff: Diffchecker

yes but with 1497 ms which is too dangerous :D

Div2 C test 59 is a stdlib qsort() killer!

Learned my lesson today: shuffle before using quicksort

My solution

withoutshuffle: 28226684 (TLE 59)My solution

withshuffle: 28235814 (Accepted)Not only me, other C (without plus-plus) user (rainboy) is also affected:

rainboy's solution

withoutsuffle: 28219544 (TLE59)rainboy's solution

withsuffle: 28233646 (Accepted)Then I search for source code for qsort() gnu implementation and found this: https://code.woboq.org/userspace/glibc/stdlib/qsort.c.html

It choose the pivot element using a median-of-three decision tree. After I read this: https://stackoverflow.com/questions/7559608/median-of-three-values-strategy the median of tree is pivot selection strategy to prevent worst case performance on easy to make case like "almost sorted data".

So I think it's not easy to make this qsort work in O(n

^{2}), but this test 59 prove that it's something common (although this is first time I encounter this problem after ~3.5 years experience in competitive programming).How to make testcase that make this stdlib qsort() run in worst case O(n

^{2})?I trusted this function for years and now... he betrayed me :p

Why use qsort instead of sort? is there any advantage?

EDIT: oops, my mistake, misread.

sort has a better worst case time complexity. sort has a worst case runtime of O(nlgn) whereas qsort has a worst case runtime of O(n^2).

Because there is no sort() function in C, only qsort().

I get "Wrong answer on test 2" (E: on problem D) when I submit and it evaluates wrong answer, but when I do custom invocation it evaluates to the correct answer. What is the difference between "custom invocation" and normal submission? E: The submission: 28237592

Don't mind me — there is a mistake in my code and I checked the wrong numbers...

My code(28230274) for DIV2 — D gave TLE when submitted in GNU C++ 14. Exact same code(28238828 ), when submitted with GNU C++ got accepted.

Why is this happening( due to compilation overhead maybe) and isn't this unfair ? Should I start submitting in GNU C++ from now on ?

Accepted code has max execution time 1497 ms with TL=1500ms. It was lucky to pass.

You shouldn't start submitting in GNU C++, just write faster solution and don't forget that compilation time isn't counted as execution time of your solution.

Thanks for pointing out :) And I just realized that the same solution passes in 1497 ms in GNU C++ 14 when I wrote the code directly main() instead of making a function solve() and calling it from main() Code : 28239178

can you please share your approach to solve E...

Is it possible to do problem D in python? My solution in python is close to the editorial one( but failed) and I implemented one of the AC solution in C++ by others and rewrite it in python but still can't get pass testcase 8. Anyone help? Thanks a lot!

I think you can try to use a better algorithm to solve the problem. If your C++ program runs more than 1000ms,your solution in Python is hard to get accepted, and I think my idea of problem D is better than the editorial

Thank you for your advice. I will take a look of your solution and see what happen if I implement it in python.

Can anyone check my solution to C using Binary Search link: http://ideone.com/hC25Oz

Can Someone explain me the solution of problem C ? Thank You.

I have used 4 vectors in my solution.

During input itself I ignored all packages which had a length of 'k' days or more since I could not use them with some other package (would have exceeded the constraint of EXACT k days). So, in vector 'deal' I pushed the {cost,{start,end}} and in the vector pack[end-start+1] I pushed the {start,cost}. Once the input part was done, I sorted the pack vectors one by one from (0,k). Now i created 2 more vectors :

I created these 2 new vectors because if not, then I had to write a binary search function separately. So I basically kept the pack[i].first portions in pack_day[i] and pack[i].second.portion in pack_cost[i] so that I could use the lower_bound function. Let me illustrate this with an example.

Suppose I had 3 packages: (k=4)

1 3 5

2 3 4

6 7 2

Then deal would store this : { {5,{1,3}} , {4,{2,3}} , {2,{6,7}} }

Then pack would store this :

pack[0] : {}

pack[1] : {}

pack[2] : { {2,4} , {6,2} }

pack[3] : { {1,5} }

Then pack_day would store this :

pack_day[0] = {}

pack_day[1] = {}

pack_day[2] = { 2 , 6 }

pack_day[3] = { 1 }

Then pack_cost would store this :

pack_cost[0] = {}

pack_cost[1] = {}

pack_cost[2] = { 4 , 2 }

pack_cost[3] = { 5 }

So now, if I am provided a package starting from L, ending at R and costing W, then I will have to search for another package of length LEFT = K — (R-L+1) days. So will have to search the pack_day[LEFT] vector and find the position from where the packages start further from (R+1). So if for example,

L=3

R=6

W=5

K=10

DAYS IN CURRENT PACKAGE = 6-3+1 = 4

DAYS REQUIRED IN OTHER PACKAGE = 10-4 = 6

So search in pack_day[6] for the position from where packages start from (R+1=7) 7 so that disjointness is satisfied. Once you have got this position, all you require is the minimum cost from THAT POSITION to the end of the pack_cost[LEFT] vector.

Finding the position aspect is taken care of by lower_bound :

Now you require minimum cost in pack_cost[LEFT] vector in range (IDX,end of that vector). So for the minimum cost finding part, we shall take minimum from the end of the vector to beginning.

So the minimum in pack_cost[i] vector from position IDX to end is = pack_cost[i][IDX]

So, iterate through the DEAL vector and for each package find its optimum partner package and keep taking a global minimum of the costs :

My AC Code Complexity : O(Nlog(N))

Thank You So Much! I understood very well..

can anyone tell y my soln to C is giving RTE 28228552 . Thanks in advance.

Can anyone find my bug please :/ problem: D

http://codeforces.com/contest/822/submission/28252419

Div 2 C giving WA on Test Case 25. Can anyone help me in finding the error?

http://codeforces.com/contest/822/submission/28250623

Man this is the third time I'm commenting. After commenting, I'm not able to find the previous comments. Why does this happen ?

Bro..Your code is extremely lengthy to look at. Let me explain you my logic. I hope it will help you.

I have a map<pair<int,int>,int> mp-stores the minimum value of range {l,r},

an array of set<pair<int,int> > st[N]-store the value {l,r} in the r-l+1 th set.

So you have a map in which you can get the minimum cost from range l to r and an array of set in which st[i] has all the ranges stored in increasing order whose distance is i. So now lets run a loop from i=1 to i<x and continue if st[i].empty() or st[x-i].empty(). We will only consider ranges from st[x-i] which occur after the end of a particular range in st[i]. So this is kind of a merge function in merge sort. Let me explain it. Initially we will have the pointers itl and itr pointing to the beginning of the i th set and the x-i th set respectively.

We have two cases :

1)R of itl is greater than or equal to L of itr-in this case we know that these are of intersecting type (or the itr pointer's range is completely before the itl's range-we do not need to consider this because this will be considered when i=x-i). In this case we can safely say that since the range at itl is not satisfying itr,all the ranges that come after it wont satisfy it as well. Hence we increment the pointer at st[x-i].

2)R of itl is less than L of itr- in this case we know that it is a valid range which can be a candidate for the answer. Hence we compute its cost. But wait you will not simply add their costs. Instead you need to keep a variable which stores the minimum of all the costs of ranges in the st[i] set. This is because if a range in st[x-i] satisfies with the j th range in st[i] it will satisfy with all the ranges which occur before it. Hence you will keep a variable global and whenever you encounter this case you need to update it to minimum value possible.

How to calculate minimum-Whenever Case 1 occurs just compute cost=global+mp[{itr.first,itr.second}] and update ans=min(ans,cost); Just keep in mind you need to consider all the elements in st[x-i] even if st[i] elements have finished because they also satisfy all the elements in st[i] if at all they satisfy even one of them.

Just be a bit cautious while writing the code, and surely you will get an AC. I did not get an AC during the contest as i was very careless — well it has become a norm nowadays :( :( .

Thank you very much for the explanation. That helped !

I would really appreciate it if someone could help me figure out why the following submission ended up with WA on testcase #7. I'll try to explain each of my steps in this post if anyone is confused with what I was trying to do :^)

http://codeforces.com/contest/822/submission/28232461

So I have an array arr that has dimensions n x 4. The first column was meant to store r — l + 1 and I was planning on doing a sort based off first column with my own comparator. Up till this point my code was successful (I'm 100% sure). However, I feel the mistake lies somewhere in the way I applied the binary search to find the other value in the array such that both sum to x. Any advice is appreciated greatly!

Thanks for the great contest Melnik :)

IS IT RATED IS IT RATEDDDDDDDDDDDDDDD

Can someone tell me how to solve a variation of Problem C, i.e., if more than two disjoint trips are allowed? All I can think of is a recursive approach. For N trips and Duration K, choose

. Any approach to implement this would be nice. Thanks

I only can think about DP... O(NK^2) DP[i][k] stores min cost ending at i with length k. Initially DP[i][k]=inf, DP[i][0]=0 for every vacation (sorted by r) (l, r, c) DP[r][k]=min (DP[l-a][k-r+l-1]+c). Also you can do O(N^3) by compressing intervals in O(NlogN).

You can do it in O(n^2logn) using RMQ.

You don't need rmq, just prefix minimum. Its O(n*x)