Hello Codeforces!

On Aug/25/2020 17:35 (Moscow time) Educational Codeforces Round 94 (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 or 7 problems** and **2 hours** to solve them.

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

Good luck to all the participants!

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | neal | 7 | 179 |

2 | tmwilliamlin168 | 7 | 210 |

3 | jiangly | 7 | 235 |

4 | kmjp | 7 | 236 |

5 | LayCurse | 7 | 245 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | orz | 54:-1 |

2 | anuragsingh804 | 31 |

3 | Loveforever | 20:-3 |

4 | dapingguo8 | 16 |

5 | celestialcoder | 15 |

401 successful hacks and 778 unsuccessful hacks were made in total!

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

Problem | Competitor | Penalty |
---|---|---|

A | neal | 0:01 |

B | jiangly | 0:05 |

C | gleb.astashkin | 0:07 |

D | balakrishnan | 0:06 |

E | aibark | 0:04 |

F | rainboy | 0:43 |

G | rainboy | 0:19 |

**UPD:** Editorial is out

0

he hasn't participated to rated contests for 6 months.

Oh, I thought the last person would say he just doesn't participate in the rounds and it would be MiFaFaOvO :)

That is already done! ...in parallel universe.

Exploring life other than CP.

He hasn't participated in the last 6 months, so he has moved to the inactive section of codeforces.

You can see his profile.

Gladly waiting for div4 && div3 Contest..........

Div 4 is not happening any time soon...

"You sleep while we work: due to technical reasons Codeforces may be unavailable on August 24 on time interval 21:00-23:30 (UTC)."

Ha ha, I am in UTC-7 timezone, so for me at this hour I am wide awake!

West coast be like: Aww I have to wake up early for CF contests

East coast:

sleeps in until 10:25 and doesn't miss the contest`You sleep while we work`

It's not a statement, it's an order.mike mirzayanov is from russia) so russians sleep at this time)

best of luck

Codeforces is the best way to spend time in this pandemic

https://bfy.tw/Ormx

In normal Div 2 ,weightage is different for all question, but in Educational contest weightage is same for all questions,and Ranking is based on penalty and no. of questions.

Anushk-24 can you explain/elaborate this please?

In the classic div 2 rounds you get a different amount of points for solving different questions. For example you get for A 500 points, for B-750,C-1000, and so on, but in the educational rounds this doesn't exist and you get one

pointfor each question you solve. Also, in the classical Div 2 rounds you get less and less points for problems as time goes but in Educational round you get penalties.smh people changing comment content to avoid getting more downvotes

Finally...

In the recent Educational Round, I unable to have some positive rating. Expecting positive this time. Give me your wishes. Cross fingers.

No No No!!! another bad nightmare.

I'm looking forward to this competition. I wish I could increase rating.

Hoping to remain expert this time :)

Do you mean specialist?

yeah !~~!

Hope that queue does not occurs.

Can anyone please tell me what is the speciality of Educational rounds?

what it the meaning of "equal weight-age" ?

If you solve A and if you solve F, you get the same result.

oki, ty man

Some more -

Actually there's a systest phase after the hacking phase(contains all successful hacks), and your solution might fail during that phase.

That's true but people usually don't wait till that long and directly see the rating changes. That feel of "Running on Test Case X" is unmatchable.

Greetings to the Harbour Space university :D I think problem solver students in there are lucky to have this great community:D Always forward :)

Hoping for a positive delta :)

became pupil first time in last contest. Hope will maintain this status :)

Persistence my man! Full year of persistence paid off! Congrats. :)

Kudos to Team vovuh BledDest awoo for organising awesome contests.

for destroying participants by bad ordering of problems

wish me good luck

good luck

thank you nimom.

This kind of ordering?? You just destroyed me.

Tester think all problems are easy :(

Unbalanced problemset?

Problem B makes me rethink my whole life.

B sucks

Luckly I jumped straight to C and got it early. Still didn't solve B tho...

I thought it is a dp problem, but dp always act as a mirage. Wherever i am unable to think of logic, i always thought the problem to be of dp(XD), but after contest i got to know about greedy approach.

Felt B was even harder than D. Still, I am not sure about my solution. And I think I've seen E before on CF

Yes, E is exact copy of:

448 Problem C

Not exactly. In E you can not perform an operation if any element being affected is already 0. In that problem you provided a link to it says that it can be appliead as many times as you wish

The most disgusting codeforces round I have ever participate. B has misleading statement. C gives a useless and misleading range of x. E is an so old problem. The most bad experience.

I have idea just now. I could have done this. That irritating B costed me. Disgusting round. Don't order problems in terms of difficulty

What exactly is misleading in B and C statement?

Many are confused in C for -1 condition !

-1 is when there is no answer, and it is clearly stated in the output format. Figuring out when there is no answer is a part of the problem.

why do u give an range of x by [1,|s|-1]. It is absolutely useless. If you want to make both w[i-x] and w[i+x] unexist, plz just make x in any range or a not such a range make some participants think it have some meaning.

$$$x \in [1, |s| - 1]$$$ is exactly the range where the value of $$$x$$$ does have some meaning.

sry,I can not find any use of this.

For B

You don't care what to take, since each of them will melt into one steel ingot.But the question is to maximize the no of weapons, so it does matter what he chooses. The one with the lesser cost will give us more no of weapons.

Bruh how can u get confused by this. If it stated how you maximize weapons it is giving u the answer.

I didn't get confused as such. It's just contradictory in my opinion.

And so many participants think B as the most volume,just because you state that melt them. Why give such misleading statement?

Well, there are two places where it is clearly written that we have to maximize the number of weapons (the output format and the last sentence of the statement), and exactly zero places where it is written that we have to maximize the weight.

I think that such misleading statement dost not exists in most codeforces round I have ever participate. It is an online contest with tight time bound, we do not want to practice like an reading contest.

I think you have lost your mind and cool:).... Take a break.... Because you need it... The problem setters got nothing to do with it if you read the problems in a wrong way... So just don't lose your cool buddy..

I didn't find the statements misleading in any sense. And FYI, BledDest has written more contests than you have participated on Codeforces.

sry,I participate codeforces contest for about 10 years. I complained because many participant got confused as me. U can have different view, but such attack is too naive.

10 years? Your account history says otherwise..

First, I do not think this is the key point.But I can reply that I create new account after retired from ICPC. I think everyone have the right to comment a codeforces round. I played really bad in some past round, but I do not complain about it. I complained because this is the first round that I have ever seen that so much participants(maybe just in china around me) got confused with the statement. So I think I should let the round maker known what happened.

Yes, you're right. You do have the right to disagree with the setting of the statements, just as much as we do in telling you that you're slightly over reacting about the said problem statements.

I bet I'm better than your 10 years

Plz do something to prove that yourself instead of bragging here. Maybe after ten years you won`t even be able to participant WF :)

I thought Russians are the dumbest but it seems like Chinese like you are worse. Ur more dumb than your handle bro

WrongProblemOrderForces !!

How to solve E?

448C - Painting Fence

This is an exact replica of that problem. How lucky (and hardworking) I am to have solved it!

that's why UpSolving is important... xD

Is it? In tbat problem it says that you can paint a fence that has already been painted. And in E you cannot perform an operation if its range contains an element which is already zero.

Yeah, but solving E is equivalent to solving Painting Fence because in the optimal sequence of Painting Fence, we never perform an operation on an already painted part of the fence. (Proof by contradiction)

But the two problems are slightly different in the ranges of $$$a_i$$$. This makes Painting Fence a subtask of Problem E, but they are almost the same. (I used the same code for both problems because when I solved Painting Fence two months ago, my solution was a bit different from the editorial which incorporated $$$a_i==0$$$ part).

dp[pos][k] where pos is the prefix we are at and k is the number of active 2nd type queries and gives minimum answer to make all elements till pos equal to 0

goodbye ratings.

How to solve Problem D?

Iterate for $$$j$$$ and $$$k$$$, Now you need a index i such that $$$a_i = a_k$$$ and $$$i < j$$$, similarly, you need index $$$l$$$ such that $$$a_j = a_l$$$ and $$$k < l$$$, this suggests us to store two things.

$$$1$$$. $$$pref[i][j]$$$ be the number of times $$$j$$$ appeared from $$$1$$$ to $$$i$$$

$$$2$$$. $$$suff[i][j]$$$ be the number of times $$$j$$$ appeared from $$$i$$$ to $$$n$$$

Now, rest is quite easy.

. edited .

pref[i][j] be the number of times j appeared from 1 to nshouldn't it be

pref[i][j] be the number of times j appeared from 1 to i?Yeah. $$$1$$$ to $$$i$$$.

Could you elaborate more? Wouldn't overcounting be a problem ?

I think there wouldn't be any overcounting since every time j and k's combination will be unique.

Submission link

thank you, it works) helped for me

There are only at max $$$n$$$ distinct numbers, so lets consider the case where each of them are used as $$$j$$$ and $$$l$$$, lets call this number the $$$divider$$$. So for each $$$divider$$$, we iterate left to right across the array, lets say the current number is $$$cur$$$. There are two cases:

$$$cur$$$ $$$\ne$$$ $$$divider$$$ — Then we want to add the number of pairs for which this position is $$$k$$$ and some previous position of $$$cur$$$ is $$$i$$$, lets say it is $$$cnt_{cur}$$$. We'll add this to the answer and also store $$$cur$$$ in a vector with contains all non-$$$divider$$$ numbers visited (if its visited multiple times its stored multiple times). I'll explain how to calculate $$$cnt_{cur}$$$ in the other case.

$$$cur$$$ $$$=$$$ $$$divider$$$ — Then we want to add all possible values which act as $$$i$$$ to their respective counts. Clearly each number in the vector we stored can act as $$$i$$$ if this position acts as $$$j$$$, so we just add 1 to $$$cnt_{x}$$$ for each $$$x$$$ in the vector.

Also, we have to consider the case where all 4 numbers are the $$$divider$$$, but this is simply $$$cnt_{divider} \choose 4 $$$.

Now since we're iterating over $$$n$$$ distinct numbers and iterating over the whole array in $$$O(n)$$$ each time, and operation 2 is clearly $$$O(n)$$$, it may appear as if the total complexity is $$$O(n^ 3)$$$. However we can observe that $$$cur$$$ $$$=$$$ $$$divider$$$ can only occur $$$n$$$ times over all iterations as each position has only 1 value. So operation 1 which takes $$$O(1)$$$ time is run $$$O(n ^ 2)$$$ times and operation 2 which has complexity $$$O(n)$$$ is run $$$O(n)$$$ times, so overall $$$O(n ^ 2)$$$ which easily passes.

My submission — 90967360

https://codeforces.com/contest/1400/submission/90950605

I iterated for i and k and maintain some arrays which mean:

lft[x]: how many x appears in the range [i+1,k-1]

rht[x]: how many x appears in the range [k+1,n]

cnt[x]: how many pairs of (x,x) with the first x in [i+1,k-1] and the second x in [k+1,n]

Apparently, (cnt[x] = lft[x] * rht[x] ) always hold but we can't iterate for x (which cause TLE). But note that with the same i, we move k from k to k+1 will cause only the change of cnt[a[k]] and cnt [a[k+1]], so cnt[] can be maintained with O(1) and the solution is O(n^2)

How to solve B?

Hintnumber of swords and number of axes is less than 10 ^ 5.

Tried with that but WA

Go from 0 to number of swords.

In each iteration. You try to take

`i`

swords and if you can't all swords then give remaining to your follower.Now, take as much as axes you and your follower can with remaining weight capacities.

Find maximum answer from all of them,

Not so nice Implementation

Ohh no. Another silly mistake

If u started ur loop with 1 instead of 0 .. we are in the same boat buddy .... this mistake cost me the whole problem

I tried first taking as many swords as possible and then removing each sword and getting axes in place(only if I can) for both f and p and combine results of both. What's wrong in this approach?

What kind of hint is it ? :)... It is also given in the statement(number of swords < 2*10^5)...

Some people like me ignored it. After reading the problem second time I noticed that it is less than 2*10^5

Okay Fine... But to be honest I laughed so hard on your hint.. and I am still while writing this comment... Great Hint:).. Don't take it personal man...

😏

The solution is greedy. First, if s>w swap them and the number of sords with the number of axes. Make a for from 0 to x axes that you take where x is the maximum available given, check if it's possible to take that many, then add as much sords as possible, then add as much axes as possible to your friend bag then add as much sords as possible to your friends bag. That's it!

Link to my code: 90946553

B should be placed after C :(((

After D

Why? It is just a basic brute force.

Though it is a basic brute force but many might have been stuck if they took the path to solve it via Linear Programming

That doesn't increase a problem's difficulty.

Copy pasted E from here

:(

The problem may seem standard but I am curious about how you found that EXACT problem that E was copied from

Practice...

I remembered solving this problem somewhere. And I remembered that it involved painting the walls. Then I googled and got the problem.

Impressive memory! :)

I had also found this, but wasn't sure if they are same. Checkout the last condition in the link you shared. "Note that you are allowed to paint the same area of the fence multiple times."

Is it the same, as I think we can't the operation in today's problem if not sufficient Ai for which we intend to do operation?

Maybe I'm missing some observation. Please clarify toxic_hack

Even if you are allowed to paint the same area of the fence multiple times, that would not reduce the number of operations needed.

You will not need to paint it horizontally twice, because you would have combined the horizontal operation.

Neither do you need to paint vertically twice for the same reason.

After painting horizontally in the optimal fashion, there are no unpainted block under a painted block. There is no need for a vertical paint to go over a block painted horizontally.

I Accepted 448C

but I don't know E is the same as 448C,I'm fool ,lol.

Fucked-up-order-forces

Still waiting for the day I'll turn expert. (The grind is still on)

congratulation

How to solve G?

Inclusion-exclusion, answer is C(cnt[i], i) if m = 0 where cnt[i] is number of people j with l[j] <= i <= r[j]. If m > 0 then for each mask you need to calculate intersection of segments, and subtract\add C(cnt[i] — badCnt, i — badCnt) for L <= i <= R (badCnt is number of unique people in mask, [L, R] is intersection of segments). Since badCnt <= 40, you can precalculate it with prefix sums.

Inclusion-exclusion on the subset of taken pairs of mercenaries that hate each other.

Suppose that we fix a subset of pairs we take, this subset denotes the subset of mercenaries we have to take (up to $$$40$$$ of them). For these mercenaries, intersect the segments $$$[l_i, r_i]$$$ to get the range where the size of the subset will be (let it be $$$[L, R]$$$).

Suppose there are $$$k$$$ mercenaries we have to take. Then we have to compute $$$\sum_{i=L}^{R} C(c_i - k, i - k)$$$, where $$$C(x, y)$$$ is the binomial coefficient, and $$$c_i$$$ is the number of mercenaries that are allowed in a subset of size $$$i$$$ ($$$i \in [l_x, r_x]$$$ for those mercenaries). The key observation is that $$$0 \le k \le 40$$$, so we can build $$$41$$$ arrays of those binomial coefficients and use prefix sums to quickly get the sum on range.

I believe the crux was that max complete combos never exceeded 2^20

Can someone just give a hint for B?

Iterate over number of swords bought by one of them, and then select greedily. https://codeforces.com/contest/1400/submission/90977190

Is Linear Diophantine Equation used for Question 2?

No,It can be done without this theorem.

You can draw a coordinate system in the form of linear programming. According to the slope, the answer must be one of the two endpoints.

Wrong Answer on test 2Story of this contest

what is wrong with my code for C, plz help, i'm desperate and i can't find the mistake. 90982135

plz help

I couldn't understand that long code but here is how i upsolved it: First we only know that we will get a 0 only if there is no '1' on i+x and i-x indices. (Update both indices to '0') then, for each '1' in s, we check if

at leastone char either i+x or i-x is 1. if both are '0', print -1. else print 1's in all un-updated indices and updated will be '0' from the first step.tks, but i think i understand my mistake, i should have initialize the answer with all ones.

Seems like that wasn't the only mistake. I'm no expert but i think that shorter code like this is easier to debug.

isn't E divide & conquer dp?

Yes and it's actually pretty easy.... Almost solved in during contest and feeling regretful now...

Thanks for the best B ever. Must say it was a bit humiliating when i started solving it first but it turned out to be the best decision of my life when i decided to move on to C rather :) .

Great decision. I wasted an hour on B. Couldn't even read D which I was able to solve in 10 min after the contest.

Can you help as how to see rank after the contest? I'm unable to find myself.

Just see Friends Standings.

Okay, thank you.

I failed just because of starting the loop from 1 instead of 0 ... feel me lol

I found B very interesting..

shouldn't have wasted that much time on B, C was waaayyy easiear and doable than B.

Yup,I also wasted a lot of time in B ,since I thought that problems are in SORTED order...

Can someone give any hints for F?

The total length of $$$x$$$-prime strings is not too big (somewhere around $$$5000$$$), so we have to generate them, build an Aho-Corasick automaton and implement the following dynamic programming: $$$dp[x][y]$$$ is the minimum number of characters from the first $$$x$$$ we have to remove, so the resulting state in the automaton is $$$y$$$ (make sure to mark the bad states of the automaton, that is, the states where some prime string ends).

Haven't really heard some of the terms you used. Guess this problem wasn't intended for me to solve. Appreciate the reply BTW :)

We will try to explain this technique in editorial

Hi all, can u help me? Sorry, I bad at English.... https://codeforces.com/contest/1400/submission/90954904

cases of for having '1' is ambigous, but have a '0' is obvious. why are you considering '1's first?

check this test case: 11110 1

Oh...thanks for all <3

Solution for C: Initialize a string str of 1's of same size. In C just put 0 on both side of string str at x distance, if you get 0 at a position in input string. For -1 condition : Check if you can form input string from the string str according to given rules. If you can't form input string print -1.

Did exactly the same but got WA :/ https://codeforces.com/contest/1400/submission/90976353

Maybe you have checked only a specific case in your second for loop. It will be better if you try to make the original string from the answer and then compare.

See this answer

4 Times "WRONG ANSWERE ON TEST 2"...

same pinch

This contest has been weird-order-forces, greedyforces, and WA on Pretest 2-forces.

Can anyone tell me what's wrong in my approach for C. I created the original required array(say arr) by using the conditions in a reverse way, then I created another array using those conditions in a given way array(say s2) By using arr. Then I checked if the input string (say s1) is not equal to s2, the answer is -1 . Else print the array (arr). my WA

no there could be multiple answers. so finding one possible and then checking if it matches input is obviously wrong.

I think you misunderstood. His logic is right but maybe some implementation mistake.

I did the same thing and got accepted 90966489

You are correct. My mistake was, suppose if i=1 then both i+x and i-x (if existed) is not necessarily 1.Thanks.

Problem D looked like a standard interview problem.

It was LOVEDAY contest for me

SpoilerLawda__I overcomplicated B .Didnt look for cntB<=200000

What is the point of naming questions A, B, C when they don't represent the difficulty level? Just do it the CodeChef way if you can't order properly, it wastes a lot of time.

That being said, definitely a great education contest.

How to solve Problem B ?

import random random.shuffle(problemset)

So, now my believe that they sort problems in terms of difficulty is broken. Thanks!

Educational round is very unpredictive. Specially be extra cautious when they say round is for standard 5-6 students.

In fact, question E is the same as the question 448C You can use the code from question 448C to pass E.

Can confirm, just submitted.

I had solved 448C while practicing about a year ago. Couldn't solve it today. Now this is sure that I won't forget this problem/solution ever :)

me too……

but I Accepted 448C in 8/23

lol

I'm fool

i accepted 448C 10 months ago,

but i spent too much time on B that I didnt even look at E!!!

Why is this code wrong for C?

Please help (if possible provide correct logic of C)

i guess that you access string w out of bound?

I think you should check conditions

`i+x<s.size()`

and`i-x>=0`

separately.In your code, when

`i=0`

,`i-x<0`

but`i+x<s.size()`

-> you access character at a negative (`i-x`

) position in string s.i submitted my solution when very few seconds were remaining (usually when contest is over then a small rectangle appears saying contest is over but this did not happened in my case when i clicked on submit) . But my solution did not got submitted. What could be possible reasons ? can awoo or MikeMirzayanov look into it.

swap(B,C);

SpoilerWhen can we expect the editorials? Eagerly waiting for the explanation for B.

Iterate on $$$i$$$ — the number of swords you take, then you can compute the number of axes you take using a simple formula in $$$O(1)$$$: $$$\min(cnt_w, \frac{p - is}{w})$$$. Then compute the number of weapons your buddy should take: if the swords are lighter than the axes, then the buddy should take the maximum possible amount of swords he can, and then — the maximum number of axes. Otherwise, it's vice versa.

Got it. Thanks, man. I don't know what I was thinking when I first saw the problem. Feeling so stupid now.

I tried first taking as many swords as possible for F and then removing each sword and getting axes in place(only if I can) and then decreased the count of respective weapons and then performed same thing for P and then combined the results.

I saw many of test cases for this solution correct but many were close but not exact? What's wrong in this approach?

PS:- I understood your approach. Thank you.

Hey man! If you find an answer to your question. Please let me know. I did the same. Don't know why it's wrong to do that.

The question E was an exact copy of /problem/448/C. why?

Why is it giving MLE on E?

I created a 3-d vector ( n * n * 2 ) of ints

Technically, 10^8 vector of ints gives ~ 4*10^8 ~ 400 MB,

So here it is 4*(5000)*(5000)*(2) = 2*10^8, which is roughly 200 MB, and constraint is 256 MB!

Are you using long integers?

no I changed it to integers, after 1st attempt, still MLE

Still 200 is pretty close 256. And I see you are using vectors. Vectors sometimes take a bit extra space than you assign them.

Maybe array won't give MLE

thanks, it worked with the array. still curious to know the factors affecting the MLE part. bcoz I had approximated 1MB to 10^6 bytes, but it is 1024*1024, which provides even more space than 2*10^8 bytes.

Read up on how vectors work. A vector is alloted extra space than the size you declare it to. This is to support the pushback operations in constant time. When the actual capacity is reached, the size alloted is doubled I think.

vector makes more cells than it actually has, because it can expand

Poor me couldn't solve C. Could anyone explain it a bit?

First initialize s (length n) with all 1's.

Traverse on string w. For all 0's in w set s[i-x] = 0 if i-x>=0 and s[i+x] = 0 if i+x<n, where i is the index of a zero.

Check if the final string s is correct. If it is print it else print -1. You have to check if it is correct because you changed some cells' values from 1 to 0 in s. So you have to make sure that all the 1's in w are valid.

Can someone tell me where do I go out of range I got so tilted during the contest.On problem C:90979571

you should initialise your string s = ""; and in for loop s +='a'; even though your code is giving wrong ans but you will not get RE

Wow thx a lot. Do you know why my code gives runtime error?

I think it happens because the string is empty so you cannot use its indexes , as the space at that index is not created.

A bit weird it passed on test case 1 without RE but thanks a lot for the help.

Contest is very interesting.... Thanks...

Damn, I didn't read problem E correctly (or I forgot the details). I thought we had individual numbers given and not the numbers of each specific number....

Why don't you guys announce officially that problems won't be sorted according to increasing difficulty. And I think gone are the days when the problemset used to consist of problems with varied difficulties. It's really frustrating taking part in such contests.

why will binary search not work in problem B.

I was trying like this if you can take 'mid' number of total swords then you can take any number of swords less than 'mid'

to check mid we will take that kind of sword which is cheaper first and then rest of the other type of sword.

Submission : https://codeforces.com/contest/1400/submission/90957831

please help

upd: i got my silly mistake

Dear coders,I have a question.Suppose I submit wrong solution in this contest two times.Before two minutes ending the contest,if I submit correct solution,Is it counted accepted?And is it show in my contest list that I have solved this problem during contest time?

Yep , if you solved the problem during contest.

Swap B and C :)

I spend too much time on B.

so I didn't read E. :)

can somebody please help what is wrong in my code in div2C ,i just changed some if's and it got accepted thanks in advance WA CODE Accepted Code

Alternate Solution to B:

Suppose item of type 1 costs lower than type 2 ( if both are equal choose arbitrarily). We first determine if there is an optimal solution which does not use all the type-1 objects. Consider any optimal solution S*. If S* has some type-2 objects, replace them by type-1 objects until there are (a) either no type-1 objects left, in which case we conclude that there is an optimal solution which uses all type-1 objects, or (b) We obtain an optimal solution consisting only of type-1 objects, which, further, does not use all type-1 objects. But (b) happens iff floor(p/weight_{type 1}) + floor(w/{weight _type 1}) < cnt_type 1.

If (b) happens, then the optimal value is simply floor(p/weight_{type 1}) + floor(w/{weight _type 1}).

Otherwise, all the type-1 objects are part of an optimal solution. Now we iterate over the number of type-1 objects that one of the persons takes as part of the optimal solution, we can then figure out the remaining capacities of both persons and update the answer accordingly.

Someone please explain how to solve problem D.

this is brute：

`for(int i=1;i<=n;++i) for(int k=i+1;k<=n;++k) if(a[i]==a[k]) for(int j=i+1;j<k;++j) for(int l=k+1;l<=n;++l) s+=(a[j]==a[l]);`

I'm going to use a two-dimensional prefix and optimize this toUnable to parse markup [type=CF_MATHJAX]

$.

`for(int j=i+1;j<k;++j) for(int l=k+1;l<=n;++l) s+=(a[j]==a[l]);`

So the total complexity is going to beUnable to parse markup [type=CF_MATHJAX]

$,Can be achieved by.

`code != explanation`

Your optimation is not clearly parsed. Can you mention it again?

Let's take all possible values of j and l, so we need to find possible i and k. How do we do that ?

Spoilerif we count the occurrence of each number from 1 to 3000, before j and between j and k, we are done.

But it's a tle. So how to do it effectively.

SpoilerWe increase j and l in steps of 1, can we just keep a variable and modify its value based on the current element?

I think the code should be readable now. 90963741

Nice explanation :)

Was D a standard approach? If it was, what is this thing called?

Ps: I know it is an optimization to the brute force and hence can be called DP, but I wanted to know a more specific term than DP related to this problem (if any)?

No its not dp. The optimization is done via Prefix sum arrays

Yes, you're right! My bad :(

Well I am not sure for the standard term, I can relate it to "contribution techniques". A recent problem which uses same kind of technique can be found in Codechef August Long Challenge,( Subsequence frequency counting ).

Thanks a lot!

anyone please help what's wrong in my code in problem C( giving wa on test#2)

https://codeforces.com/contest/1400/submission/90994456

One of the bugs is,you did not consider that when i-x and i + x are both out of bounds, s[i] must be zero. But I corrected this point and still got the wrong answer, and you have to find the remaining bugs yourself. It is recommended that you can print out the test data to see what is wrong.

but cases in which it's wrong are not shown ..

I helped you get the data that caused the error, it is 1011 1 You can take a look at how my submission gets the data. https://codeforces.com/contest/1400/submission/90994907

For problem C, will checking if the character is 1 instead of checking for 0 and transforming be wrong ? Hard to explain but here's the code WA Solution

u should check the 0 first since its obvious, if you check the 1 first, its hard to handle as there can be 2 positions for 1

Bro it can be checked.I couldn't solve it during the contest,but after the contest I upsolved it.

yes it can be but he said "it's hard to check".

In question c, I did not consider that when i-x and i + x are both out of bounds, s[i] must be zero. It is a sad story. I think there should be many people like me.

No, both simultaneously can't be out of bounds read constraints.

Edit : sry my mistake.

i did the same mistake.

I have an nlogn Solution to problem E(nlogn preprocessing and O(n) recursion) ..

https://codeforces.com/contest/1400/submission/90992471

segment treee?

No .. a simple sparse table.

can some one provide small counter case in my problem c submission

Accepted

I don't know what exactly the mistake was but it was something with reinitializing values.

I am not initializing anything if you notice . Just see these two codes , the only difference is that i am declaring string outside the loop and in the other inside. wrong answer

accepted

problem is with the way you use resize() function. temp.resize(n+1,'1') will not change the value of whole string to string of '1's. Ex. if temp="001" then it will become "00111" after temp.resize(5,'1').

For problem F, it says in the notes for the first example that

The resulting string "1162317" contains no 8-prime substrings.But here "62" and "17" are also 8-prime substrings, right?

In the 2nd condition with the $$$[l_2, r_2]$$$, $$$x$$$ can't be divisible by $$$f(l_2, r_2)$$$. For those substrings, 8 is divisible by 2 and by 1.

Can we solve D if the array were circular? For example, take n points around a cirlce. Each point i has a value $$$a_i$$$. Join points which have the same value by a straight string and then ask for the number of times two strings intersect.

Wow. Another perspective to look at the problem.

This perspective would be helpful in creating another problem with the same solution.

my solution for E just got hacked, https://codeforces.com/contest/1400/submission/90994198 can someone help me to find the mistake?

This is not quite correct. If array has length 1, but its only element is 0, then the answer is 0. After reading your code I think it's impossible for your code to pass an array with 0 to this function recursively, but you can be given such array on the input.

Thanks a lot man.

Is n^2logn allowed in D , many submissions are passing Extreme cases with 1990 ms.

URGENT If i submit a solution from 2 different accounts will both of them will get skipped?awoo

problem E felt much easier than problem D... Could it be because problem D is a well known problem? Because I looked at some solutions and they seemed very tricky. I mean, I reduced it to the number of "pure" intersecting sub-segments so maybe that's well known? I don't know...

If it is a well known problem, I can say that even though they consistently screw my ratings, these EDU rounds are so important to get familiar with non-ad-hoc problems and their solutions.

Even though C has a very simple understandable solution. Did anyone thought of using Two Sat to solve the problem during contest ? It is a very direct application of Two Sat.

SpoilerIf s [i] == 1 then either i-x is true or i+x is true. If s [i] == 0 then i-x is false and i+x is false.

You can check my submission here 91000892

Can someone hack my solution for D, the time complexity of my solution is $$$O(n^3)$$$.

Link: https://codeforces.com/contest/1400/submission/90999462

Edit: It's $$$O(n^3)$$$

Your solution actually can take up to $$$O(n^3)$$$ on a test like

Due to how unordered_map works, occurrences of 2001 will be stored in g[0],

so

this piece of code will be executed for all $$$y$$$ in $$$[1,1000]$$$, for all $$$0\leq i<j<2000$$$, which is total of 1999000000 times.

Fortunately for you your solution has a very low constant factor and runs on this test in 1699ms so I don't think it is possible to hack it.

At first I thought compiler somehow realised this loop is somewhat redundant and optimised it into just adding the same thing x times, but no, when I run it on similar test with $$$n = 6000$$$ it did take approximately $$$8$$$ times longer

I most-probably hacked 30 submissions using maps , unordered maps and custom hashes. and I hope if my test case is added then his solution may time out. PS:- My test can't stop compiler optimisations thus I don't think the submission will timeout.

No it won't. The part using hashmap does $$$O(n)$$$ operations on it, so even if you defeat it, which is impossible given that those operations operate on keys from [1, n], they'll take $$$O(n^2)$$$ which is still very fast with $$$n=3000$$$.

Ya I came to know it after seeing that pragma , in his submission. And I think that pragma should not be allowed in real to use. As it is just allowing some brute approaches to pass. Anyways its my opinion.

I worked out E by greedily picking min_element and recursively solving the subproblems on either side of it. Can someone provide the proof of optimality for the approach?

The recurrence comes down to $$$T(n) = T(n-i) + T(i) + O(n)$$$ where $$$i$$$ is the index of the min element. Worst case is $$$T(n) = T(n-1) + O(n) = O(n^2)$$$.

You want to take the longest "horizontal" interval because if you take two overlapping intervals, you can always replace them with their union and intersection (for example if a = {1,2,2,1}, you can take the intervals [0,2] and [1,3], but you can replace those with [0,3] and [1,2]).

So, you keep taking the longest one as many times as you can, which happens to be min_element times.

What you guys said is right in itself, but it doesn't justify optimality, I think.

The

first observationis that the order of the operations doesn't matter. Consider some element $$$i$$$ frequency $$$a_i$$$. All the operations acting on $$$i$$$ need to sum up to $$$a_i$$$ (op 1 has the effect of $$$+1$$$, op 2 has the effect of $$$+x$$$). Since addition is commutative, the order doesn't matter.The

second observationis that it's always better to do a single op 2 on any $$$i$$$. Two op 2s $$$(i, x_1)$$$ and $$$(i, x_2)$$$ can be replaced with a single $$$(i, x_1+x_2)$$$.The

third observationis that the intervals for any two op 1s can be replaced by their union and intersection (as described by Svlad_Cjelli above). This means that if you have some set of intervals that overlap to span a range $$$[l, r]$$$, then you can replace the intervals such that you have an op 1 that spans the whole range.Now for the greedy strategy. By the first two observations, we can end the algorithm by perform $$$r-l+1$$$ op 2s on the remaining elements. Otherwise, we need to perform some sort of op 1. Using the third observation, we can greedily pick the largest range possible.

Where does the min element come in? If you use the greedy strategy above, then doing $$$< a_{min}$$$ op 1s followed by the $$$r-l+1$$$ op 2s is never better than doing $$$r-l+1$$$ op 2s from the start. However, once we reach $$$a_{min}$$$ op 1s, we cannot do anymore op 1s over the full $$$[l, r]$$$. Hence, it breaks down into the left and right subproblems.

Therefore, the final greedy algorithm $$$solve(l, r)$$$ is the minimum of:

Thanks a lot!

C is confusing.

For a given $$$i$$$, such that $$$i-x > 0$$$ and $$$i+x <=N$$$, should $$$s[i-x]$$$ be equal to $$$s[i+x]$$$? From the problem statement it seems so. Otherwise $$$w[i]$$$ is not defined, since it should be equal to both $$$s[i-x]$$$ and $$$s[i+x]$$$.

But from looking at the solutions, it doesn't seem to be the right interpretation. What is the right interpretation of the problem statement?

If w[i]==1 then s[i-x] and s[i+x] must be equal (to 1). But if w[i]==0, then one of them could be 0 and the other one could be 1.

Recently seeing this trend of placing a more complex problem (grammatically or otherwise) at B than the problem at C, and its not helping. Now on, will keep a watch if problem C is getting solved by more people than B, and then decide which to attempt first. ;O

I think this round is "hap"py and not "happy".:(

I can't solve E(T_T),I'm so weak!

E is not a original question Same as https://codeforces.com/problemset/problem/448/C

It seems that D is not a original question either.Will this contest unrated?

I hope it's Unrated. It's a bad experience?

Please explain why problem E is exactly the same question as 448C - Painting Fence. And will this round be unrated because of this mistake?

Yes plz, no bias

E was used in Tencent(腾讯) coding test of campus recruiting a few days ago.

In E.Clear the Multiset can anyone explain me how we get the output as 3 instead of 2.Thank You! input 5 1 0 1 0 1 output 3

We need to clear $$$a_1,a_3,a_5$$$ (They are all equals to $$$1$$$) separately, so we need $$$3$$$ operations. How did you get the answer $$$2$$$?

thanks,got it.Got a bit confused earlier!!

deleted :(

i am your friend, and i want to thank you（

Why does a iterative solution not work for E? I try to find the minimum value in every contiguous segment with value >0, and reduce every element in the segment by the min. value, I keep doing this till all elements are not 0

91013729

Reducing by the min takes min operations.

Your code prints 1, but the answer is 3.

oh, I completely forgot that. Thanks a lot

Hi, please somebody help me debug this code for problem B. I have been trying to find the bug but no success. I am first iterating over all number of swords we can take ourselves, and then giving the remaining swords to follower. Axes fill the remaining space for both.

MY CODE

Thanks in advance!

loop on l from 0 to p/wgts should be upto min(p/wgts, cnts) because otherwise cnts-l can be negative.

Testcase:

expected answer : 5 your output : 6

Ohh yes!! Thanks for your help :)

Why doesn't the system test start?

Waiting for it :((Is it rated?

.

I think he asked coz the problem E was not original and few people passed it by just submitting code for the problem which was copied.

Why the rating for this round is not given till now?

Because of the system test

why system tests are not completed yet?

i think, now it is testing for similar solutions

how to solve problem B using binary search?

Same question. I was trying with binary search but got wa on tc 2. Can anyone tell me whats wrong in my code. I think my logic is 100% correct.

Code Link: https://ideone.com/nbM3Uu

Thanks in advance.

C was easier than B.