Привет, Codeforces!
Рад анонсировать и пригласить вас на Codeforces Round 678 (Div. 2), который пройдет 24.10.2020 17:05 (Московское время). Пару недель назад мы проводили Codeforces Round 675 (Div. 2) на основе задач Andersen Programming Contest 2020. Квалификация, а в этот раз мы хотим предложить вам порешать лучшие 5-6 задач финала.
Обратите, пожалуйста, внимание на необычное время начала раунда. Этот раунд будет рейтинговым для участников, чей рейтинг ниже 2100.
Компания Andersen уже второй год проводит соревнование, которое в первую очередь предназначено для поддержки студентов региональных ВУЗов Беларуси и Украины (с этого года). В этом году в финале соревнования примет участие 60 студентов региональных вузов Беларуси и Украины.
- Авторами раунда являются: Алексей aropan Ропан, Юрий hloya_ygrt Шиляев, Андрей andrew Мищенко, Александр AleXman111 Кривошеев и я.
- Координаторами раунда выступили Николай KAN Калинин и Ильдар 300iq Гайнуллин.
- Тестировали раунд: Борис PuRpLe_FoReVeR Серенков, Егор 244mhq Дубовик, cckk4467 и rafaelgo.
- И, конечно же, спасибо огромное Михаилу MikeMirzayanov Мирзаянову за cоздание платформ polygon и codeforces.
Всем выше перечисленным огромное спасибо за вклад, внесенный в подготовку раунда, а вам удачи на предстоящем соревновании! :)
UPD: Опубликовали разбор. Удачного дорешивания! :)
Поздравляю победителей официального зачета:
а также победителей неофициального:
Спасибо всем за то что приняли участие. Желаю приятного дорешивания!
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.
...and this time we want to offer you to solve the best 5-6 problems of the finals. Does this mean the problems have appeared before in some contest? What about people who have already seen the problems. Sorry if my doubt is stupid.
Final will end two hours before the start of the round. All finalists are aware that they can't participate in the codeforces round.
Clashes with El Clasico
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
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?
Is it rated?
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 2100
How did you help him?
Please explain how did you do that?
remove the "
okay
.
.
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.
Wait if its rated till 2100 then the actual level of questions will be
Div 1I 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
Score Distribution Vladik ???
Will there be dynamic scoring?
queueforces
Why such a long queue for submission?
10 minutes of queue is enough to distract someone from the contest and force him to write a comment.
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
Unexpected error? WTH?! Make the round unrated, I literally can't send in my solution.
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 :(
i think this contest is going to be unrated
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 LOL
How about make another Rated Round with 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!
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.me/contest/1436/submission/96604421
Hey can you please take a look at my solution? I used the same logic. https://codeforces.me/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)
how to solve problem C?
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.
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) \gt = 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.me/contest/1436/submission/96577050
Try it before system tests =))
Since when the problems are so difficult? last time I participated was like 6 years ago. :(
what is wrong in my code on problem D . ( testcase 7 ) :(
https://codeforces.me/contest/1436/submission/96592768
In D, my O(n*log(U)) solution kept TLEing until I changed
long longstoint.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.
Отправил задачу A на 4ой минуте, но из-за крутой системы решение не отправилось (unexpected error), в результате потерял очки. Очень грустно
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 2we 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.
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.
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.me/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.
In 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
https://codeforces.me/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)
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.
Hello!
Can someone please help me, I don't understand what is wrong with my solution:
https://codeforces.me/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.me/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?
B probably was
Disagree regarding A, quite a typical A
Disappointed as this contest had less number of pretests and the pretests were weak!!
make this round unrated? I would have saved 20 mins if I knew there was a small mistake in my first submission but there was a 10 min queue.
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.
n=1 i think
This pretests...
Weak Pretest, Unexpected Error, Long queues and rated contest!! Make it Unrated :P
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 Pretest, Long Queues, Unexpected Errors and Rated!!:(. Make it unrated :P
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.
Worst pretest and worst contest. problem setter doing prank on us.
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
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 frustration
Yeah, totally unbiased.
Well, I am
unbiased in terms of this round being unrated for meregardless. 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.
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.
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 setl = 0andr = 3. Then, it will setmid = 1, check it, and updatelto2sincea[mid]is equal to3. For the next iteration,mid=2, check, andlwill be updated to3sincea[mid]equal to1, which is less than3. Then, the loop is over, checka[l-1]you will get1instead of3.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 = 0andr = a.size(). This way of viewing array is useful for the case of splitting array, so instead of being confused of usingmid - 1,mid, ormid + 1, you can directly uselefttomidandmidtoright.Someone explain for C testcase 10, why for 3 3 1 the solution is 0 ? 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?
problem C: why the answer of the test case 3 3 1 is 0 not 2? can anyone help?
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 ???
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.
Did anyone fail in Test Case 52 in problem C? Can someone explain me why am i failing this testcase
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
Понравилась D только из-за условия)
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.
Floating point precision problem.
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 ?
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.