Hi Codeforces!

I am glad to announce and invite you to Codeforces Round #678 (Div. 2), which will be held on Oct/24/2020 17:05 (Moscow time). A couple of weeks ago, we held Codeforces Round #675 (Div. 2) based on the tasks of the [contest:297213], and this time we want to offer you to solve the best 5-6 problems of the finals.

**Please note the unusual start time of the round. This round will be rated for the participants with rating lower than 2100.**

This is the second year that Andersen has been holding the competition, which is primarily intended to support students of regional Universities in Belarus and Ukraine (starting this year). This year, 60 students from regional universities in Belarus and Ukraine will take part in the finals of the competition.

- The authors of the round are: Aleksey aropan Ropan, Yuri hloya_ygrt Shilyaev, Andrei andrew Mishchanka, Alexander AleXman111 Krivosheev and me.
- The round was coordinated by Nikolay KAN Kalinin and Ildar 300iq Gainullin.
- The round was tested by: Boris PuRpLe_FoReVeR Serenkov, Yahor kefaa2 Dubovik, cckk4467 and rafaelgo2.
- And, of course, thank you very much Mike MikeMirzayanov Mirzayanov for creating the polygon and codeforces platforms.

Thanks a lot for your contribution to the preparation of the round!

Good luck to everyone in the upcoming competition! :)

**UPD:** The editorial was posted.

Congratulations to the winners of **div 2**:

as well as **div 1** winners:

Thank you all for participating!

Unusual time + Comments on Scoring Distribution

added, thank you

Stay hydrated!

Why do I get the strange idea that some people just copy what I say?

Last time I saw you was orange and setting great contests. Congrats on getting grandmaster :)

*testing

Yeah congrats circle

Everyone beware!, Comment section hijacker is in the house! (why not hit 200 with this one ?)

I wanted to see if a green warrants less upvotes than a red :P (which it does, as expected)

Well it doesn't help that people remember that Monogon wrote it first already

Hey, he was a tester when he left the comment. I think, big part of it was tester appreciation.

You forgot that people are less likely to upvote something if you're the 2nd person to say it and that it's more important that the comment poster was monogon than that the comment poster was red.

They are copying your strategy to get contribution points.

Last time the contest was nice. Hoping the same this time as well.

Clashes with El Clasico

Yeah that's a terrible news too ):

I have a question to ask the author. Compared with other div2 competitions, the questions in the last preliminary round are already considered difficult. Are the questions in the finals more difficult than the preliminary rounds?

Codeforces Cotest at 8:05pm El Clasico at 8:00pm What will you choose!Obviously

`Codeforces Contest`

.7:35 pm*

He is from Bangladesh. Bangladesh's time runs 30 min faster than India's.

Oh, my bad!

El Clasico at 20:00.Is it possible to reschedule the contest!!Do you really think any of the players were going to participate?

You sure?

AnsuFati ViniciusR -messi- griez7 Isco FrenkiedeJong21 EdenHazard ToniKroos LucaModricMamani

Also ronaldo could play this game, but he came to Juventus

But Ronaldo attackted by corona .Hope to , champ will get well soon !GOAT -messi- is going to miss El clasico due to cf

CF round at 20:05(UTC+6). Is it possible to reschedule the El Clasico?I think we need to ask the officials of ERIC12138 and RealMadrid

Deleted

So I can't watch the El Clasico.

So I can't participate in contest

clashes with ieeextreme

I actually have a college assignment due today, can this round get rescheduled to tomorrow?

scoring distribution?

Is it rated?

No

It is clearly mentioned in the bold letters in the post that "**It is rated for the participant with rating lower than 2100**

You forgot to bold..

I selected that B (Bold)option from the cf editor but it didn't work.Can you please help with this?

It is clearly mentioned in the bold letters in the post that

It is rated for the participant with rating lower than 2100How did you help him?

Please explain how did you do that?

remove the

"okayEl classico or codeforces round 678??

.

.

Me, but I am not proud of it

Well I'm not proud, I'm just trying to make my contribution to 0 but got downvotes xD

I can totally understand you bro....I had -76 contribution on my other account once and had no hope of becoming it positive but now it is 70+ (+146) -> I got it in only two weeks..You have to be smart...not just comment anything..

But again I am not proud of it..You are talking as if upvote count is some kind of a measure of your skills.

sorry to disturb you..

this time is good for me.

No Ronaldo No Like

when someone asks about score distribution:

downvoters be like****:Today we will make your contribution hit a century in negative axis.Wait if its rated till 2100 then the actual level of questions will be

`Div 1`

I am not sureEven Edu Rounds are rated for those users.

Codeforces : There is a contest at 17:xx MSK.

Random user : The round clashes with 17:xx MSK. Is it possible to reschedule the contest?

score distribution ?

Vladik

Busy watching El Clasico?

after the contest

May be we have to wait till the contest started!

Score DistributionVladik ???Will there be dynamic scoring?

queueforces

Why such a long queue for submission?

what is the problem with prob A. you guys are changing prob statement while contest is going on. time to say goodbye to this contest....:)

Getting unexpected error on submission for B.

me too

getting unexpected error. can't submit b. what is happening????

Getting unexpected error while submitting B. Please fix!

not worth the frustration. going to eat dinner instead

unable to submit solution :(

This round should be unrated. Unexpected errors, long queue etc...

I don't mind long queues, atleast everyone is on the same disadvantage. But this unexpected error puts people who solved the problem first on a disadvantage. Please make this unrated.

Wow! I wonder how the good idea of making this round

"RATED"even the submit was delayed for about 10 minutes LOLHow about make another

Rated Roundwith 10 munutes delay together? It seems very good idea to make great round!I am not sure but I think it is taken care of bcoz for problem B some people who have submitted after me have gotten more points thus compensating for the 10 min delay.

I've read the logs — the issue with the unexpected error during code submit was fixed in less than 5 minutes.

Queues also were fixed quickly. Plus the longest time to judge was only 459 seconds (most submissions which faced a queue were judged much faster).

Are you sure that less than 5 minutes of such a breakdown plus some queues at the start are worth sacrificing a month of work of problem writers?

What's wrong with semi-rated?

TL;DR 5 minutes makes a huge different for greens/greys.

Personally, I made 5 attempts on problem B which probably took around 10 minutes longer becuase of queues. Since I only solved A and B (like a lot of greys and greens), this change made a huge difference.

What does semi-rated mean? How would that be implemented? Does the leaderboard change? Do the ratings get calculated against the ratings of people who drop out as well?

All rating changes get cut in half.

Testing round 17 before global round 11 seems a better idea for most of the contests.

MikeMirzayanov Do you think people just kept hitting submit button for 5 mins straight or magically knew when the error was fixed and submitted in the very next moment? Even if the error was only for 5 mins, it has cost more time than that for most people. I'm sure there were some people who got frustrated seeing the large queue and left the contest as well.

And about your question, 5 mins of breakdown + queues affect people a lot, especially during the beginning, so yes, it is indeed worth it.

MikeMirzayanov, I started with problem B today, because A looked too tough for me. After getting the implementation intact, I submitted my solution, and naturally it didn't submit. I left the contest out of frustration, because I saw people had already submitted A by that time. Now, I definitely agree that the setters did a lot of hard work, but at the same time, the starting five minutes of the round are much more valuable for a newbie/pupil. So, you should make this round semi-rated. I think it's a good compensation for both the setters and the participants. And, note that-regardless, this round will be unrated for me. So, I am actually unbiased over here.

[deleted]

Instead of conducting many contests under Div2 and setting easy problems. Better Codeforces should conduct more contests as they are doing now, but the contests must be distinguished between Div 2 and Div 3 perfectly.

Because it is sometimes disgusting to wait for Div 2 contest and the finding Div3 or Div4 level problems in the contest :(

Lol mate, you've solved only 2 in this contest. Big words, though.

I'm talking about all contests nowadays, not this one in specific:)

What's the difference between Div3 and Div2 problems?

Well it certainly does not contain Div3 or Div4 level problems(looking at your own submissions (you manage to solve only 2 in div3/4..certainly not)). The problems are great and balanced but the contest would have been better if there were no queueforces, delays etc.

See the thing is A is cakewalk, B is easy constructive, C is cool and enjoyable and D seems tricky...perfect for a Div2 contest.

I don't understand your point at all. You solved only 2 problems this contest, and took 30 minutes to do so. Didn't you need to think? What's bad about you solving 2 problems out of 6? Are you lacking challenging problems?

[deleted]

You didn't even solve more than a single problem in your last 3 contests(2 were div 2) and now you are bullshitting this.

[deleted]

Don't expect people to listen to you after writing from an alt xd

If you understand your comment is good, write from main account. If it's bad, don't write it. If it's good but you would get downvoted anyway, then for sure contribution system is broken so don't worry about your contribution. So no reason to use an alt.

Bro see the difficulty level this was a perfect div2 contest. A require some brain as always it involves.

B trick of just using 2 and 3 as prime numbers.

C good problem gives you deep intuitions of Binary search . The way the binary search used was brilliant.

D. DFS problem with a lot of insights and mathematics of finding averages and numbers.

E Another cool problem involving a lot of thinking.

F No idea.

Also see the balance between the number of submissions. '

A perfect Div2 contest must look like this only!

but do u think nowadays contest is going good for high rated specialists or experts....If by luck u get late in even one of top 3 then ur rating is going to fall....I can see from ur case also....

I don't know what you want ratings or practicing those hard problems If your option is first think once again!

so rating fall doesnt affect u..Rating seriously provides a motivation ..By the way I want to ask u,Isnt is better to judge candidate on the level of their skills rather than how speed he solved....some newbie could have solved first two qsns very fast and some coders let it be u take time in A isnt u get demotivated and panic on seeing ur rank to be 7000 for a moment...Isnt it better having question level something lik 800-1000-1300-1700-....

I would be happy to have a like/dislike button for contests. So I could click there instead of writing bad comments.

The blog under which you are commenting itself has a upvote/downvote button. Why don't you use that

Well, the problem with it is that it cannot be changed

Agreed, perhaps a rating for problems as well since a contest may be made of problems written by different writers. This will give feedback to the writers on what people find interesting (and what they dislike), and also help people prioritize better problems during practice.

How to solve E?

Traverse the array from 1 to r and maintain a segment tree of the last position of X. For each ar[i], find min(lpos(1),lpos(2),...,lpos(ar[i]-1)). If this is > lpos(ar[i]), then ar[i] will occur in the final array.

Corner case : For 1 to occur in the final array, there must be a non-1 element in the array.

Didn't solve it during contest, but if you could find subarray mex queries in time $$$F(n)$$$ then to find if mex $$$x$$$ is possible for any subarray, consider all pairs of consecutive positions where $$$x$$$ lies, say $$$i_1, i_2$$$ for one, then you need to check if $$$mex(a[i_1 + 1, i_1 + 2..., i_2 - 1]) == x$$$. Since there are atmost $$$O(n)$$$ such pairs you can solve the problem in $$$O(n F(N))$$$.

One way to solve subarray queries is using Mo's algorithm and keep elements not in current segment in a set, giving $$$F(N) = \sqrt{n} \log n$$$

what is the idea behind C?

I think you can just keep track of the recursion and calculate how many numbers you can pick for position middle.

Thanks but can you elaborate more? what do you mean by recursion?

Put x in position pos, and assume the array is decreasing before x and increasing after x (so it's in sorted order, with x in its spot). Now run the binary search and see how many numbers of this array it accesses. Say there are "l" numbers that it accesses that are less than x, and "r" numbers that it accesses that are greater than x.

Then it suffices to find l numbers < x and r numbers > x to place in their correct positions. Then can rearrange the other numbers however. It follows the answer is $$$\dbinom{n-x}{r}\cdot r! \cdot \dbinom{x-1}{l}\cdot l! \cdot (n-r-l-1)! $$$

I did the same but wasn't able to get the sample test output. Can you please share your submission. Thanks!

https://carbon.now.sh/zit55zLD3opEedCifi1w

My accepted code with the same idea..

https://codeforces.com/contest/1436/submission/96604421

Hey can you please take a look at my solution? I used the same logic. https://codeforces.com/contest/1436/submission/96608378

hint for n = 6

OR Just

in any value of n

For those who are interested, here's our short video with some logic that could have lead to this solution

D, anyone stuck on pretest 7?

I got runtime error on test 5?

Yeah! Have u figured it out?

int overflow

I did for a while, then got stuck on pretest 4 on later submissions >:(

Some things I fixed to get AC (no clue which caused the WA):

`long long`

, so I switched to`__int128`

.Pretest 7 was when there is only one child of 1. After correcting my mistake in this case my solution passed pretests

Would you kind enough to share the case? Hopefully, my solution produces the correct output for this type of case.

solution(WA on test7)

Does there exist an easier way to find subarray-mex-queries (i.e, given $$$l, r$$$, find mex of $$$a[l...r]$$$) other than Mo's?

Yes

How to solve D?

The answer is the maximum of ceil(sum/sz) for each node. Sum denotes the sum of all a[x] in the node's subtree, and sz denotes the number of leaves inside node's subtree.

I don't have a rigorous way to show this but this informal explanation is sort of intuitive if you think about it.

Damn I got it at the end of contest but couldn't code...This problem was a bit confusing, I had to read it again and again.

I see your logic, but can't we just simulate the process using bfs and keeping track of updated a[] values ?

I see. I will try to prove it myself before tutorial.

Proof :

This an obvious lower bound. We just need to show that this can be constructed.

Let us show this by induction on subtrees. This is obviously true for a leaf. Now let's show that we can create a root node, and join subtrees that this condition can still be satisfied.

Let us move all the values on the subtrees to their leaves in the optimal arrangement. Now consider where the people in the root node go.

Let's say the maximum value of a leaf in the optimal arrangements of the subtree is $$$m$$$. This is also equal to $$$max(sum(v)/leaves(v))$$$ for all immediate children $$$v$$$ since we are showing by induction. We can add to the leaves with smaller values until we reach $$$m * leaves(u)$$$. If we reach this point, that means that $$$sum(u)/leaves(u) >= m$$$. Now we can put the values one by one, and reach the optimal arrangement.

Damn that's smart, thanks.

Also Tairitsu best.

How to approach problem C?

https://codeforces.com/contest/1436/submission/96577050

Try it before system tests =))

Can u please help me in finding the error?Thanks in advance here is my code https://ideone.com/gRTOIo

"Simulate" binary search, at any iteration if the middle is lower than

`pos`

the in this position there should be a number lower than`x`

, if`middle`

is greater than`pos`

then the number should be grater than`x`

, so you can multiply the options for the values at each value of`middle`

. When you reach`pos`

then the posibble rearangements of the numbers that u did not use yet is just it's permutationplease share your code, because I have used the same idea but got WA on pretest 4

https://codeforces.com/contest/1436/submission/96571014

Lesson Learnt from this Contest:

Long Queue and Submit button not workingdoesn't guarantee you anUnrated ContestSince when the problems are so difficult? last time I participated was like 6 years ago. :(

I feel contests are getting harder and since lockdown, the competition has increased substantially i.e from around March onwards.

The level of difficulty has certainly increased( I find old problems of same rating to be easier and I think thats also because of how many people are doing that during contest and it's position) since the competition and no. of participants has increased a lot.

But anyways, with some practice you will be well off.

Were the problems more Data structure/algorithm oriented earlier?

In D, my O(n*log(U)) solution kept TLEing until I changed

`long longs`

to`int`

.i think test case of C is designed to attack O(nlogn) solution

Wouldnt it give WA when sum will exceed int bounds?

I meant variables that would not overflow, ex. n, p

I just gave up and wrote the $$$O(n)$$$ solution after my $$$O(n \times log(U))$$$ solution got TLE twice.

If I submit a solution which passes the pretests and again after sometime I submit another solution to the same problem which again passes the pretests, then my last correct submission on the problem is considered or the first correct submission ?

Only the last one.

RIP queue

I forgot to print newline in my first submission of problem B and the solution was in the queue. Expecting WA on pretest 1, I submitted again but both passed and I got a resubmission penalty. Can anything be done about it?

first submission: 96543626

second submission: 96544467

i dont think so.

Yeah happened with me for C, got a resubmission penalty and last submission was considered so overall a good negative in total score.

Man… I did B in 13 minutes and I resubmitted after two hours a better solution, just to make sure it will pass the official tests. I didn't know that only the last submission counts. Now instead of +25 I get -60.

Can someone explain why i am getting Runtime error in pretest 3 of problem C

My solution 96588906

Thanks in Advance :)

Try including a value for fac(0) as well.

The problem E is a problem of 2013 ICPC Hangzhou online.

http://acm.hdu.edu.cn/showproblem.php?pid=4747

BTW,I'm in Hangzhou now so I am familiar with this problem.

how to solve C?? need hint and ovservation.thanks in advance.

Think about the order of the binary search. Every position in the array has a distinct binary search order. By tracing the direction of the B.S., you can reconstruct possible values for each "middle" position.

Just stimulate a binary search and check the path that binary search follows in there and count smaller and bigger for x during that simulation. After that its simple PnC .

in binary seach we make jumps from mid to val that we need..., so when ever we come to some point. we just need to check weather to jump forward or backward.

to jump foreward we need to put some value at that cell that is less than x. choices that we have is n-x for this cell in array. to jump backward we need to put some value at that cell that is greater than x. choices we have is x-1.

now if you make two jumps forewards, choices to put values in those cells are n-x for first cell and n-x-1 for next cell. total choices are (n-x)*(c-x-1)

after you fill and calculate all cells where you jumped. the permutation of remaining cells doesn't matter. you can permute all the rest of cells.

`eg 4 1 2`

`we jump to 2 (4+0/2).`

`val[2] == 1(x) [it is given value at 2 is 1]`

`choices that we have to fill jumping indexes is 1 (only 1 was filled no other choice).`

`ans = 1 * fac(3), [3 is number of cells whose value doesn't matter]`

`ans = 6`

[DELETED]

its strange because as i checked it doesn't ouput correct on the test below

16 927

59 72 10 90 73 72 75 47 30 59 90 16 76 82 48 28

it outputs NO while the correct answer is YES|:

O(n^2) solution didn't work for E ? I thought that for n = 10^5 , it should be fast enough

No, it won't pass because you can probably do 2*10^8 low level operations per second in cpp.

n^2 for n=10^5 would mean 10^10 operations which gives TLE.

sorry

Hmm. So 10 minutes of queue affected your chances at trying ABC, and therefore you couldn't solve them? Don't talk bs man.

Sorry again

that is your personal issue.

nope bro actually its an issue...if u are going to get good plus doesnt means that contest standard hasnt fallen down

i meant that "saying something disturbed his mental peace" is his own issue. he cannot blame it on that "something".

sorry

you need to work on your "mental peace" then.

Obviously ;)

Can we solve D using binary search??

I tried using binary search. But got various results except AC.

My idea : Binary search on the minimum no. of citizens bandit can catch

So, basically i fix the answer and check if its valid or not.

https://codeforces.com/contest/1436/submission/96583528

UPDATE : I understand that its failing because of overflow.

Each leaf can take atmost 2e14 citizens. So, we carry forward 2e14 to 1e5 nodes. So, the value goes to 2e19 which leads to overflow.

Yes, you can. 96579469

what is your valid function of binary search?

valid in the following sense:

Hello there, can anyone help me with approaching problem C? I'm a newbie so please bear with me.

Here was my idea but seems like something is wrong here:

for example, for the testcase 123 42 24,

to reach 24th position, we need to go via 61st, 30th, 15th, 22nd, 26th, 24th positions.

And we can have 41(<42) numbers on position 61, 40 on position 30, 81(>42) on position 15, 80 on position 22, 39 on position 26, and 1 on position 24(i.e. 42) and the rest of the numbers shuffle in remaining positions. Therefore, 117!*39*40*41*80*81 % (1000000007) should be the answer.

We will go like this 61 30 15 23 27 25 24

First, if you use the pseudo code provided, the positions are 61, 30, 15, 23, 27, 25, 24.

Second, if a position is to the right of pos, you should use numbers that are greater than x, since you want to go to the left. Similarly, if a position is to the left of pos, you should use numbers that are less than x, since you want to go to the right.

So the answer is actually 116! * 81 * 80 * 79 * 78 * 41 * 40 Check.

Damn! Probably miscalculated due to frenzy. I was right all along. Wasted 30 mins on this :( Anyways thanks a lot for explaining!

Well tbh I didnot read your approach but I will try to explain it to you easily....

Notice that we only need to constrain logN number of positions. This is because in binary search there are logN steps to reach target each step follows a specific sequence of path to reach the target. This sequence of path is determined by the classic BS alg as given in problem.

Now if your target pos is greater then mid that implies the element at mid must be less then x(inorder for BS to go right) and vice versa.

Count the number of such positions where the element is constrained to be less then x and vice versa.

Answer can be found using simple combinatronics.

Here is my submission :

CIn problem E, why doesn't DSU work? I kept getting WA on TC 3.

Edit: Nvm, I found my mistake.

same here

Honestly, I don't like Problems which are directly dependent on slight variations of standard algorithms. For problem C, I always update right as middle-1 and not middle itself. So during the entire contest, I tried debugging but couldn't figure out that it was a simple misreading of the Problem statement.

But you should just follow the recursion given by the code in question.

Just because you don't implement an algorithm the way it's written on the problem doesn't mean it isn't standard. Using [l, r) instead of [l, r] is not a "variation of standard," it's just another way to implement it.

I agree it was my mistake to misread. My point is different people implement standard concepts in different ways. So I personally dislike those Problems where the authors implement their version of the standard concept and we're forced to work accordingly. Anyways, lesson learned!

What is wrong with my code on problem D . wrong answer on testcase 7

96592768

When I want to submit my code, it says you did not register for the contest. Did I really forget to do that or is it just a system problem?

https://codeforces.com/contest/1436/submission/96590709 problem c ,error on pretest 3. i dont know where is the error,any suggestion?? what i did is

a! * b! * c! * d * e a=total moves to get to required position that is pos using binary search b=moves where mid < pos c=moves where mid > pos d=bC(x-1) e=aC(n-x)

check for n = 1.

The idea behind all of this is a bit math-y, but division and modulo don't play well together. Take for instance (6/2)%4, the correct answer is 3. However, if I first take the modulo of the numerator, then of the denominator, and then calculate, I get 2/2 = 1, which is not correct.

In func, when you have

a similar problem may happen. You base your code in the fact that ans * (n-i+1) is divisible by i. This may be true if you didn't have a modulo, but since you modulo every step of the way, it may be the case where this isn't true and you end up with an incorrect answer.

To calculate (nCk), use Pascal's Rule, nCk = n-1Ck + n-1Ck-1 or multiplicative inverses instead.

I wasted 30 minutes in C just to realise in the end that my code was failing at n = 1 .

(Sad reacts only)

Hello!

Can someone please help me, I don't understand what is wrong with my solution:

https://codeforces.com/contest/1436/submission/96569147

My approach is to get 2 as the sum on all rows and columns

Since the problem is multi-test, you should reset any global variables before/after each test case. For instance, n=4 leaves you with

if I'm not mistaken, but if the next test case is n=6, you're left with

Oh yes, Thanks!

weak pretests on C, stupidly missed an obvious mistake and it passed.

Damn My B will FST as I mistakenly saw n<100 .!

Passed but how?

Wasnt there n=100 as test case

by the way big case for me.

https://codeforces.com/contest/1436/submission/96589733 Can anyone tell what is wrong in this? Problem D using binary search

FSTs on C incoming!!

lets have a good night's sleep then before rating changes.

Is it just me who thinks that A & B were too easy for Div2?

Yes

B probably was

Disagree regarding A, quite a typical A

Totally Agreed

Disappointed as this contest had less number of pretests and the pretests were weak!!

FSTforces. Cool problems though.

I am not claiming that the round should be unrated, but let me tell you one thing

For A, i checked if the sum of the array is a multiple of m , it passed the pretests and later i got hacked and lost 350 points

For C, i submitted and got Runtime Error on test 79....So yeah sad contest for me!

Cheers all! Kinda sad a good contest was turned into a worst one(for me)!

hi guys. right now my solution for c is in queue, if my problem c got accepted you all can downvote this comment so hard!!. but if my solution got failed please upvote(it will make me feel better). and i think its funny to do such things. you will probably see more of these comments from me XD

Goodbye my friend.

goodbye contribution. im so stupid XD

What is test 10 in C ??!!! I dont see why my solution would fail :(..Anyways I fastforced A and B so my rank went up lol.

Their binary search algorithm is really dumb, if you look at the code in the problem their algorithm keeps going even after it finds middle...

If it's any consolation, I and many others FST'd for the same reason :(

OMG! I didnot even look at the algorithm and just assumed it was a normal BS(Binary search). But turns out their BS was actually BS(Bu*lsh*t).

I didn't understand answer of test 10 for C. :( . The test was-- 3 3 1 I printed 2, they said, it will be 0. So, aren't following permutations okay? 1 3 2 and 2 3 1 ???

Yeah run these permutation against their algorithm....

1 3 2 -> L : 0 and R : 3 and MID : 1

It should stop here XD..but it still goes on due to stupid L.

There is no such thing as "normal BS" Obviously bs can go different paths depending on the implementation.

By normal BS.. I meant the one which usually stops when an element is found and doesn't go around frolicking.

Funny thing

Because I always write BS that "goes around frolicking" instead of stopping when the element is found.

Good for you.

well, ok, it does not really frollic. But it does not stop. The point is that there are different implementations and should've written the answer for the given implementation, not for the one in your head.

Ok sensei.

n=1 i think

This pretests...

Damn, I failed systest in D because I said $$$10^9*10^5 = 10^{13}$$$, and also in E because I used a segment tree of size $$$n$$$ instead of $$$n+1$$$. If this contest was rated for me, I would be drowning with my own tears :P

One test Case , One Damn test Case and more then 1000 people got their rank dropped by 1000+....

Weak Pretests, Long Queues, Unexpected Errors and Rated :(. Make it Unrated :P

I understand that the authors worked very hard for preparing this contest, but the issues are really too big to ignore at this point.

I completely agree, Most of the FSTs could easily be resolved if only the verdict was WA instead of pretests passed.

What a blood bath in Problem C!

I've never seen a contest with pretests this bad for almost all problems

The thing is this contest is a "based contest" .. I just wonder what happened with the people who gave this in official time

what is a based contest?

Problem in this contest were from a official competition mention in the title of this blog and hence we say that this contest was based it. Moreover It was a final man.. RIP My C "pretest passed" :/

its funny how every one made same mistake of stopping iteration on stisfying mid rather than both limits.

It even funny that not only we both but many many many people did same ......

Well, "based" contests, contests with some names in titles and contests with specific sponsors often have their peculiar features. While not all of them are perfect, they add some diversification to rounds

Can't stop laughing. it's unique.

Why mathforces...

Not expected such bad pretest! Good contest turned worst , long queue, bad pretest ...

I hope they don't make the round unrated. Even if it had some problems.

Goodbye color, hope to cya soon...

weak pretest for DIV2 B

While I agree that the contest had its problems, I don't think that "weak pretests" should ever be considered a serious issue.

I'm biased because I have a positive delta, but I agree. There were 5 pretests on C and 7 on D. Pretty obvious pretests are weak.

You are saying that cause you didn't Failed any problem on ST

I always say that. Not only in this contest.

I believe people rely on pretests too much and it is their mistake

It is true that I haven't failed on ST. In fact I have only failed on ST once for all 50+ contests I took (yes, I was sad when it happened, but it never came to me to ask to make the round unrated because of that). What does it mean? Probably I think about corner cases more then others, I dunno

Agreed on that. But, we are wanting to make this contest reason due to a bigger reason other than having weak pretests. I started with problem B today, because A looked too tough for me. After getting the implementation intact, I submitted my solution, and naturally it didn't submit. I left the contest out of frustration, because I saw people had already submitted A by that time. Understand that we are talking about

this issue. Don't trivialize it by talking shit about weak pretests. I understand that you might get to CM after this round, because you didn't FST. But, don't lose your conscience and start acting like an asshole. Apologies if I sounded too rough, but I am calling like I see it. And by the way, this round(rated or unrated) is the same for me either ways. So, I am actually unbiased over here, unlike you.So, I am actually unbiased over here, unlike you.I left the contest out of frustrationYeah, totally unbiased.

Well, I am

`unbiased in terms of this round being unrated for me`

regardless. I don't have anything against the setters. I thought the problems were still nice. My problem lied in the technical issues that transpired. Anyway, if you still feel like giving a nice sarcastic comment, feel free to do so, brother! :)i know i was stupid to break when i found the match , but man the pretests for "C" just sucked.

Did you get why the answer to test10 is 0 ?

my code failed on testcase 10 but i don't know why. I this its answer should be 2 not 0

Yea I just did, change the break statements in your submission and then see the magic

check their binary search. you've put if mid==pos, return; which is not the case actually acc to problem.

I got it

in third question for testcase 3,3,1 my output is 2 why is it wrong there are two possibilities for 3 at pos 1 1. 1 3 2 2. 2 3 1

The pseudocode they have given in the problem is a bit different. It does not find 3 at position 1 in the possibilities you mentioned.

I got it

why is answer to this case 10 : "3 3 1" 0 .. Cant we have 2 3 1 and 1 3 2 ? Clarify where am I going wrong

Elements at both index 1 and 2 are processed before the search stops. So, arr[2] must be greater than arr[1] to direct the search to the middle. However, this is not possible since 3 is the largest number in the permutation. So the answer is 0.

For the case of

`2 3 1`

. First, it will set`l = 0`

and`r = 3`

. Then, it will set`mid = 1`

, check it, and update`l`

to`2`

since`a[mid]`

is equal to`3`

. For the next iteration,`mid=2`

, check, and`l`

will be updated to`3`

since`a[mid]`

equal to`1`

, which is less than`3`

. Then, the loop is over, check`a[l-1]`

you will get`1`

instead of`3`

.The same scenario happens for the case of

`1 3 2`

.Yes sir I just realized that I am so dumb that I put a break statement there. Oh man I am so dumb :(

Anyway, the pseudocode itself use the right-exclusive style of indexing (I don't know the usual term, but I always call it that way), which instead of pointing the element, the index is used to point the room divider (barrier between two element). That's why in the beginning it sets

`l = 0`

and`r = a.size()`

. This way of viewing array is useful for the case of splitting array, so instead of being confused of using`mid - 1`

,`mid`

, or`mid + 1`

, you can directly use`left`

to`mid`

and`mid`

to`right`

.Someone explain for C testcase 10, why for

3 3 1the solution is0? for this case mid will be at 1, so after putting 3 in 1, we can arrange the remaining elements in 2! ways i.e 2, since the other elements don't matter. So why 0?Pretest Sucks a lot. I lost two problems.

idk if this was on purpose, but thx for nice time limit in D. My binsearch solution got 1341 ms.

Solved B very late. Any suggestions for me?

Practice and Practice!!

I didn't understand answer of test 10 for C. :( . The test was-- 3 3 1. I printed 2, they said, it will be 0. So, aren't following permutations okay? 1 3 2 and 2 3 1 ???

0-based indexing

The binary search is given in the question is slightly different ;_; The loop will run two more times and final value of left will be 3.

Same doubt !!?

Did anyone fail in Test Case 52 in problem C? Can someone explain me why am i failing this testcase

I failed 51 because I forgot to take mod after 1 step. I think I am retarded.

Problem C: can anyone explain test case 3 3 1 my code is giving 2 but the answer is 0.

So there are two permutations

1 3 2

2 3 1

Regardless of which one you consider bs will pick at 3 and move the left pointer forward So you have left=2, right=3 Then you check arr[2] (1 or 2) and bs tells you the answer is on the right, where it does not exist

thanks man

why in c problem for test case 3 3 1 output is 0 ?

It should be 2 , Am i right?

Check this

I am just feeling dumb, as I didn't submit A even after solving it, assuming that I sumbitted it and rushed to B.

This contest should be unrated. I did not like it. In the starting, it took a lot of time to know the verdict. I submitted 2nd question thinking that it will be right and moved forward to 3rd question as getting the verdict was taking a long time. When I solved question 3 after then I came to know that I have already got WA on 1st pretest. This wasted my 10 minutes !! Even after then I successfully passed pretests of 3rd, but in the final checking, it gave WA on test 10. Pretests were weak and few, may be to reduce the load on the server. That's not a good idea. Completely disappointed after giving this contest!! RIP RATINGS !!

Did anyone else's D fail on test 78? If so what was the mistake you were making? My Submission

Edit: Got AC, was not computing the room left after raising max correctly. AC submission- 96827495

Input 3 3 1 Participant's output 2 Jury's answer 0

Can someone please explain this test case to me, because I feel 1 3 2 and 2 3 1 are good but the jury's answer is 0

This is for question D

It seems like its for question C.

If you see original pseudocode implemented on the statement, you can know that you should not get out of while if pos == mid.

Neither am I know why did author implement binary search like that... but that's the reason.

I'm sorry it's for question C

Can someone help me find out the problem with my submission to Problem A? My submission 96540614 is failing on test case 29.

Do you think this is true?

`1.0f + 1.0f == 2`

Yeah, it is.

See this.

1/3 can't be expressed exactly in decimal system it can be expressed exactly in a system with radix 3. Similarly, Binary also stores some decimals only to some level of precision.They should be avoided whenever possible, here there is an alternate way. The sum asked is simply the sum of all elements in array.

Yeah

Thanks, for the information.

Can problem A have a possible arrangement such that the sum is not m but it is still ok ?

Still wondering what was the reason for queue

For those who are interested in problem B analysis here's our short video with some logic that could have lead to a common solution.