Привет.
В 19.08.2018 16:35 (Московское время), состоится общий рейтинговый раунд Codeforces Round #505. Этот раунд идет в паре с раундом #504.
Часть задач взята с Финала VK Cup 2018 (ashmelev, Errichto, Lewin), часть придумана мной. Спасибо моим товарищам — Диме (cdkrot), который, кстати, является координатором этого раунда, Коле (KAN), который позвал меня его проводить, а также Грише (vintage_Vlad_Makeev) и Ильдару (300iq) за то, что они просто клевые.
Также спасибо Майку MikeMirzayanov за множественные баг-фиксы и замечательный Codeforces!
Задач будет семь со следующей разбалловкой:
500 — 1000 — 1500 — 1750 — 2250 — 2750 — 3500
UPD. Систесты окончены. Разбор
Поздравляем победителей!
Так же, как и в прошлом раунде, по инициативе компании ВКонтакте будут разыграны очки GP30.
Участники сортируются по очкам за оба тура (если участник не участвовал в одном из туров, очки, набранные за него, полагаются равными нулю); при равенстве очков как тай-брейк используется максимальное за оба тура время, прошедшее от начала тура до последней посылки, прошедшей претесты.
Напоминаю, что лучшие 10 по сумме очков GP30 получат фирменного плюшевого персика.
Надеюсь, что вам понравится. Удачи!
palindromic round :D
имя раунд
Ok so greengrape, another shitty maths contest.
Lol what? His last round was great (especially D) and had only one math-related problem. He writes hard rounds but it doesn't mean they're bad contests.
How many problems, duration, scoring?
some strong pretests please GreenGrape :D
lol
Happy Hacking&&High Rating
I feel like it will eventually become like this..
*Fine, I found that CF#505 really seems to be the most sad for me as the pic....
How many problems and what will the scoring be like?
I think I know who is the author of problem B from the official final round...
You missed just a bit. Mine was A :)
Please contest don't have problems that solve with a lot of IF and ELSE! (Iranian people say this problems "Kharkari's problems")
I think the last few games are very difficult.
I think the problems will be very interesting.
.
for you nothing
.
Points for top30
Thank you for your insightful, useful and informative comment.
three contest in a row......interesting
What do you mean? At least 554 contests in a row!
God
Can codeforces hold more contest in a row??? I need more!!! I don't need sleep!!!
after this there will be most probably a div.3 round
can someone please provide a test case where this solution will fail http://codeforces.me/contest/1023/submission/41825727
Your segment tree works wrong. In your code: int q2=query(node*2+1,mid+1,end,l,r); Correct: int q2=query(node*2+2,mid+1,end,l,r);
i have corrected it but it is still failing http://codeforces.me/contest/1023/submission/41826504
You print
YESbut the answer isNO."Some problems are taken from VK Cup 2018 Finals" is that mean that some problems are already known to some contestants??
No.
At least, in the VK Cup series, no contestants today know about those problems (as those who do know has participated before in the official round).
For other series (like parallel Olympiad or something), disciplines are kept through words. Not a really effective way in theory, but it's worked times before.
For example in the announcements of Codeforces Round #500 (based on EJOI — European Junior Olympiad in Informatics):
We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of EJOI (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.
Will it be harder than 504 or not?
Are the editorials going to appear?.. (for this and the previous rounds)
Mike Mirzayanov slaps codeforces roof
@Mahmoud..Adel
I wish to turn blue!
Hope I will become expert after this round
Я так понял, что примеры из условий — это и есть все претесты.
Совет — если хочешь зашутить в комментах, чтобы твою шутку оценили и при этом в посте есть англ перевод, пиши на англ
U want strong pretests? Hehe. Hehehehehe. AHAHAHHAHAHAHAHHAHAHAH!
The Joke
HAHA, you have a good sense of humor. I can not solve B too. Maybe I should say goodbye to programming ...
Pretty nervous having sense of getting WA on systest D. :o
How to solve D? I couldn't get my DP to be faster than n^3
I could not get it faster than n**5. Can you share your insight for n**3, because i think that should pass the time limit.
My dp was like dp[l][r][t] — is it possible to construct binary tree from l to r and root of this tree is left child of r + 1 if t = 0 and right child of l — 1 if t = 1, but it gives tle.
same
Dp[Left/Right][L][R] is true if you can express the range [L,R] of the array as a left or right child of the binary tree. Then you brute force the root of this subtree (it's somewhere in this [L, R] range and if it's gcd with the root (the root will either be R+1, or L-1 depending on what kind of child it is) is > 1, then you try to solve the ranges [L, i-1] and [i+1, R].
I thought it might be the solution but I found a case that makes me run in a little more than a second.
Ahh, I missed a key observation. If i am finding for a sequence i to j, then the only possibility of root is i-1 or j + 1. This would have made my solution run in O(n^3).
I think n^3 with some early break optimization might be fast enough.
That's what I did but I generated some random case that made me run in a little more than a second (might be because I'm in Java though).
My solution (c++) runs in 46 ms with some break conditions: 41869813
Yeah turns out I missed some break conditions (like not running the recursion for the right subtree if the left one fails) :(
Early break made it AC in Java for me, after contest :)
maybe need some optimization, my O(n ^ 3) solution got TLE
n^3 / 64 fits in the time limit. Can you imagine a solution with bitsets?
My N^3 passed the pretests: 41846474. I think I tested it with the worst possible input (no interval is possible), and it used 0.085 seconds of time.
My solution was the same as explained by Len.
EDIT: AC. Another factor that maybe impacts this is that I precalculated the GCD's.
Using STL bitset, the O(n3) DP can be optimized to
.
http://codeforces.me/contest/1025/submission/41844612
i began to feel like stupid. How did so many ppl solved D ?
Brute... With some optimizations. Consider the array to be inorder traversal of BST. Construct tree using recursion. If there is atleast one valid tree, then "Yes". Also... Use Top Down DP.
you are saying an optimized version of back tracking. how does it pass ?
The worst case complexity can be reduced to 2*n^2 with DP. dp[l][r][rootPos] where pos is 1<=l,r<=n and rootPos can be left or right since parent of any subarray must be the left one or the right one in inorder traversal.
can you explain a bit more abt rootpos
Given inorder traversal (a1 a2 a3 a4 a5 a6), if we taske a3 to be the root, then the inorder of left subtree is (a1 a2 a3) whose parent is to the right of it (a3) similarily (a4 a5 a6) constitute right subtree whose parent is to the left. For any subarray (l,r), it's parent can be the left one or the right one.
cool. and optimization means for a given range l, r you will check for the nodes for which the gcd with the l-1th node is > 1 and stop as soon as you find one and similarly for r+1. if yes, wont this get tle ?
I might have to agree with you... Got a TLE :/
what was pretest 6 for problem B?
Как решать D?
How to solve problem B?
How to solve B and C?
Just find all prime factors of a[1] and b[1], and check if some of them can divide everything.
The other way is to combine pairs of numbers into a single number
c[i] = a[i] * b[i]and usegcd()on it.Afterwards though, you will have to take care of a test like:
You can't output their product, and so have to find one of these primes somehow.
My bad, this will time out.
All right, but if
loop will time out (which it did).
ans = 999999893 * 999999937in the first place, theAfter calculating the gcd, you need to find the smallest prime factor of gcd. You don't need to iterate over prime factors of ans for finding the prime.Just iterate over prime factors of the numbers in one of the pair.
(I had similar solution, and I tied it up like so:)
Let's say you have answer g from process egor.okhterov described.
Then you can run over the array again, and replace g with
. We can show by induction that at each iteration g > 1.
You can do greedy for it. Iterate over pairs and if gcd(ans,a[i])>1, you can assign that value to ans, otherwise assign gcd(ans,b[i]).
Great :). It was so simple. Nice solution !!
Me while coding div2C:
Can somebody explain how to solve problem D? Is it requires DP or something else?
I solved it using dp with state of 3 variables l, r, i (l and r are the interval limts I am working on from the sorted array, and i is the chosen root of the sub-tree represented by this interval).
Not sure if it will pass system tests though.
If you have that 3 state dp, doesn't each state need linear recursive calls to be calculated? I believe that leads to n^4.
One observation you can make is that for a subtree on [l, r], it's root will only be a child of r+1 or l-1. With this, you can optimize the solution by keeping 3 state dp l, r, k where k is 0 or 1 and dp[l][r][k] tells you whether the subtree on [l, r] can be made as a child of l-1 (if k=0) or r+1 (if k=1). Then, you have n^2 state and linear recursive calls, so you'll have n^3. You can break out of your recursive calls early if you find that dp[l][r][0] and dp[l][r][1] are both possible.
Yes, it is O(n^4) so it didn't pass :D
I tried to use flows, but I think it won't pass too. There are cases where my program will fail.
How did you solve D using flow?
Incorrectly.
What is the hack for Problem B? Got hacked continuously XD
1 1000000007 1000000007
Well f**k...
Isn't the correct answer 1000000007 itself?
Yes but many solutions are printing 1000000007*1000000007
Ohh Okay... That isn't the case for me then. Pretests seem too weak.
Try 2 1000000007 1000000007 1000000007 1000000007 Maybe you have n = 1 precalculated.
Not Yet XD... Code Just too curious on what it might be.
I hacked succesfully with
and
How to solve B?
2 1000000007 1234567891 1234567891 1000000007
150000 pairs of 1999999973 and 1999999973. It gives TLE because people take gcd of all
a*binstead oflcm(a,b)Yeah... I did take GCD of all LCMs.
How to solve B?
And? a*b couldn't be more than 4*10^18. So the algorithm would work in O(n*log4*10^18) And if n = 150000 n*log4*10^18 = 62*150000 = 9300000. That's pretty fast.
Some people did an o(sqrt(4*10^18)) check in the end. Note that 1999999973 is a prime number.
I had an array with all prime numbers in range (1;sqrt (1e9)) and then checked a1 and b1 for prime divisors in range (sqrt (1e9); 1e9) , considering the fact if any prime number doesn't divide a1 or b1, it wouldn't be in global gcd as a divider. I did it in O(sqrt (a) + sqrt (b)) and added in an array. And still my solution crashed on test 68.
you may try this: 2 2000006 3000099 5000015 7000231
answer should be either 1000003 or 1000033
Me vs. problem C
how to solve C?
My assumption was that it doesn't make sense to do more than one time the operation. Hence, check the length of the pattern from beginning as l1 and length of pattern from end as l2 such that s[0] and s[n-1] are not equal then answer will be max(answer without any operation, l1+l2)
It can be proved actually. Just try rotating it in your head. Find the longest zebra prefix and the longest zebra suffix. Rotate the string the way these two zebras will be together but make the left rotating part as small as you can (that means, the left part is zebra prefix itself). Beginning of the new max zebra prefix will be the end of the old zebra prefix rotated and the new sufix will be a substring that went AFTER the old max zebra prefix (also rotated). So there is no way first and last symbols would be different in a new string because in that case (substring that went AFTER the old max zebra prefix) substring will be the part of the old prefix. Hope you understood something.
I don't know how, but this solution didn't pass.
split it in max len correct zebras. mark from 1 to n. whenever you split it between any two zebras, the neighbours stay the same, except for the first and last zebras — the could become neighbours so the answer is either the longest correct zebra or the sum of 1st and last zebra if it's possible
I need a video from 3Blue1Brown in order for me to understand that :)
Or at least an article from BetterExplained ;)
You don't know how many times I wished 3Blue1Blown did competitive programming videos xD
Pretests of D are very weak.
Even checking that any tree can be made from the input (not essentially BST) with every 2 adjacent nodes having GCD > 1 passes pretests.
1114 passed pretest on D. I would bet a lot even at 1/10 odds that no more than 650 will pass full tests — or at least close to that ammount.
Is ans for C just max for all cyclic shifts?
Yes.
I did that but i dont have any aidea why that works haha
Consider all the zebras in a circle. Now verify that any operation on them simply rotates this circle and reverses it.
Note that after each operation, the order of the characters in the string taken cyclically is reversed. But for the zebras the order being reversed doesn't matter, so it suffices to consider the cyclic string.
My idea for problem E:
Find m cells such that they aren't an end point, and move the cubes to them.
Next, move the cubes from this cells to their end points.
Am I missing something???
Link to my submission, I had two bugs in it, But am just saying about the idea :\ [submission:http://codeforces.me/contest/1025/submission/41865118]
I tried the same but I tried that the free cells were on the border... I think I have a bug in my implementation though
This was the worst contest I've ever participated in.
The problems A-D were pretty nice, the issues in my opinion were really bad pretests, horrible E and silly bounds in D (straight n^3 passes with precalculated gcd's).
So in summary, bad round but not as bad as for example Codeforces Round 497 (Div. 1) where 4/5'ths of div1 participants only solved Div1A (and Div1A was really easy).
In C, is "w" or "b" or "bbb" has a length of 1? but I think that one color can not make a zebra. A real zebra should have at least two alternating color,one color can not make a zebra.so the answer should be at least 2. Can someone explain this?
That's a heavy assumption to make (that zebra cannot have length 1), and should have been something you asked during the contest. It doesn't say anywhere that minimum length should be 2, so you should assume that the minimum length is 1.
the question has mentioned that "pieces of alternating colors to create a zebra",so we should think that the answer should have "alternating colors" but not just one color
I suppose that makes sense, but regardless, precision of language is not one of the strengths of CF problems, so it's best to just ask a question during the contest.
should I ask the author directly or ask here? I haven't do that before. Anyway,thanks for your advice:)
There is a way to do it during the contest. I believe under the "Problems" tab you should see an option that says "Ask a question"
anyone used articulation bridge to solve D like me?
Can you explain?
How to solve F?
Also, to anyone who solved D by dp[l][r] means whether it is possible to build a BST using number from position l to position r
F is similar to the JOI problem: solution
can someone briefly explain it, most of us don't know know japanese?
Think of every pair of non-intersecting triangles (they have points
a[0], a[1], a[2]andb[0], b[1], b[2]).Now note that there are only two lines passing through points
a[x]andb[y]for each0 <= x, y < 3, such that all the points of one triangle will lie to the left of the line (one point will line on the line), and all the points of the other triangle lie to the right of the line (one point will lie on the line).How can we solve the problem? We can draw a line from point
p[i]to pointp[j]for each pair of points. Pointsp[i]andp[j]become vertices of different triangles. Now we should find the rest of the points of our triangles. For the first triangle, we choose any two points to left of the line, for the second triangle, we choose any two points to the right of the line.The statement above helps us to understand that, using this algorithm, we add each valid pair of triangles exactly two times.
Now we should find a way to find the number of points to the left of each line. First, sort all the lines by their angle. Suppose we now consider the line
l[i] = A[i]*x + B[i]*y + C[i]. Denotepp(i, j) = A[i]*p[j].x + B[i]*p[j].y + C. For each linel[i], we should keep the points sorted by itspp(i, j)(p[a]must be earlier thanp[b]ifpp(i, a) < pp(i, b). If we can maintain this, we can say number of points which are to the left ofl[i]: it's all the pointsp[j]which havepp(i, j) < 0. Don't forget that the points are sorted bypp(i, j), so, to answer this, we can find the position of first pointpp(i, j) >= 0using binary search and so we find the answer.Now we should learn to maintain the array of points in the sorted order when we move to another line. Notice that, when line changes, only some two points swap (those two that lied on this line). It's possible beacuse the lines are sorted by angle.
So, we get
O(N^2 * logN)solution.Thanks for the clear explanation.
I have to say, for a 1000-point-level, B today was quite insane.
Hmm, or B, C and even D are all insane, in terms of both ideas and corner cases?
How to solve B?
If existed, the WCD of a list can always be a prime.
Therefore, for the first pair, I'll find all prime factors of the two numbers in that pair (i.e. any prime factor of at least one of two numbers). This process has a maximum time complexity of
.
From there, we will check that if any of those prime factors can divide at least one number in each of all remaining pairs. This process has a time complexity of O(n * log(2e9)) (The number of prime divisors relates with that number itself by a logarithmic function).
Thanks.
Did C have any corner cases? (except maybe that the answer is at most n)
As I found, there are (at least) 3:
bwbw(most common)wwwwTwo latter ones seemed mostly participants' implementation failure though.
These are the worst pretests ever.
The pretests don't test logic, or time limit, or anything. What was the point of them even being there? Might as well make it TopCoder style with blind AC after submission.
These authors, they played with us man i am telling you.
Btw, Nice work on D.
Define the constraints such that the unoptimised obvious solution won't pass.
Make weak pretests such that unproven incorrect solution passes.
I mean, this is some fun game. I like it, you sleazy mofos
typical contest from GreenGrape
I think GreenGrape has become a PURPLE one.
that moment when u realize the pretests on D are the samples and ur solution is wrong
Hack for D : 5 2 3 5 7 210 Answer : NO
Is there any way to cause TLE when hacking? I saw several solutions for B that could have been hacked by using highly composite numbers. I generated a case using the following code:
Which I believe would have caught some solutions in my room for TLE, but the file was too large. The case had to have n ~ 13000 to fit the input limit, which wouldn't cause TLE. Is there any way around this?
You can send script that generates test.
You can submit the generator itself instead of input.
Whose idea was to put a problem like E into the contest? Worst problem I've seen in a while. I wish I'd just have spent my time hacking. I think my idea works but debugging this would be just crazy. 41865146.
Maybe solving F would be a better choice.
I hate geometry so no :(
That is close to what I did:
I actually think that the solution is really nice, although many people used randomized solutions, which makes me even more sad that I couldn't code it up in time. Anyway, here is my code that passes, and I would like to believe that it is pretty readable:
link
F*** your pretests again.
Well, back to pupil again...But...What can div2B pretest 6 look like?
What was the mapping of problems from VK Cup to problem from #504 and #505?
My guessing:
A — 505 problem C
B — 505 problem D
C — 504 problem E
D — 504 problem F
E — 505 problem F
F — 505 problem G
G — 504 problem G
You're almost right, except B was 505 E.
Lol, so today's E was worth 1250 on VK cup, and today's F 2250 xD?
504 EFG = VK Cup CDG
505 CEFG = VK Cup ABEF
Тупые претесты как же я вас блин ненавижу
Constaints in D were pretty weird. n<=700 and first promising solution that comes to mind is lightweight n^3. I coded it, but got TL, which is reasonable if TL=1s, n=700 (inb4, precomputed gcd of course). So I switched to bitsets and did this successfully with time of execution 109ms. But it seems many people passed it with simple n^3. What is the reason for such weird choice of constraints and TL?
Probably wanted to exclude O(n4).
I got AC with precalculated GCD, so you're correct :Dd 41846474
My n^3 passed (recursive dp). I used all boolean arrays (except for one long long vector to take the inputs).
So, is 1 second enough for a complexity of 5e8 or even 1e9 in CF? (D was a little more than 3e8 and my submission took only 62 ms)
Was this the WEAKEST pretests in Codeforces history!!!
Now looking at my solution for problem C, I can't believe it how it passed them !!!
No, there has been weaker.
I have a simple and short solution about pB
let ans = gcd(a[1]*b[1],a[2]*b[2],.....,a[n]*b[n])
if ans != 1 then you can greedy to find the answer by the code below
Are you sure this is optimal? For example, what if a[i], b[i] were both valid options and it was optimal to choose b[i] but you instead choose a[i]. Or is there never a case where at the start ans > 1 but becomes 1 during the process.
Because this was my idea when reading the problem (woke up too late to participate) but I had a slight worry that you can hit ans = 1 at some point in the process so there would be more to the problem than just checking choosing the valid one (because both might be valid).
SorryQQ I don’t understandthis the sentence “what if a[i], b[i] were both valid options and it was optimal to choose b[i] but you instead choose a[i].”
While you are choosing the answer , it’s impossible that both gcd(ans,a[1]) gcd(ans,b[1] equal 1 because ans is a[i]*b[i]’s divisor.
Sentence doesn't make sense because it was under the assumption you could reach 1.
Also I am still unsure how that proves you never hit 1. (I saw another comment mentioning proof by induction, but no one elaborated)
The initial gcd calculated gives us a value which divides either a[i] or b[i] for every i, and so does all of the factors of that gcd, therefore, we know that in the above code, atleast one of gcd(ans,a[i]) or gcd(ans,b[i]) will be greater than one.
Once you reach a prime number in the above loop, you can be sure that it divides atleast one of a[i] or b[i], which means it the final answer will stay that prime number only.
Hope that cleared up your doubt!
Holy sh**, the weakest pretests I've ever seen. Goodbye rating, I'll miss you
Weak pretests for B.
big fat L
These are the contests when you feel grateful for Hacks.
System test failed !!!
GreenGrape and weak pretests ,still better love story than twilight .
Waiting for a standard 5 problem contest
Hackforces as usual :(
if pretests were sample tests they would be stronger than this pretests
F*** your pretests!
GreenGrape, what's pretest 14 on problem E? My solution seems to pass my validator for all random tests.
Downvoting the blog right away for the pathetic pretests.
Good problems(except C) but terrible pretests !
Doesn't problem C has a nice solution? (Just double the string and find the longest alternating substring that has length shorter than n?)
Why do we double the string? I feel like it should be something obvious but cannot parse the meaning from looking at code submissions.
It's not a bad problem. The solution is really nice!! But for me, I solved it by just guessing that doing more than 1 operation might not help increasing the answer. I was unable to prove it during the contest time, but still got AC. I think few participants like me also did the same thing.
I felt like C was a "Lucky" problem. For some it was a lucky and for rest not so. When I was seeing a lot of people were getting AC, I just did the double string approach but I have no proof.
D was a good problem. But N <= 700 was not a good constraint. I think I could have solved it quicker if it N <= 500. I had to check carefully whether it will pass. And then having no other way, I just did the n^3 dp and it got accepted.
Problem B was nice. I liked the solution.
no feedback contest
He is crazy
http://codeforces.me/contest/1025/submission/41853226
Oh great GreenGrape. I need to hide my submissions away.
My eyes are literally burning. g++ -E command to make this sensible as i remember
How did this actually got hacked
Since I was suffered from he's code, I really wanted to hack this. So I arrange his code and find a vulnerability XD
O_O that was really good job, congrats
That's against codeforces rules, he should be disqualified.
Hacked.
But Is It Rated?
why not? But somehow CF predictor is not working for me
If cf predictor doesn't work for 15 minutes we are legally allowed to be unrated
YYYYYYAAAAASSSSSSSS!!!!!!!!!!!
I can stop whining about my growing record of second places :>>>>>>>>> Waited for this so long, so happy :D
Congrats to Swistakk for finally winning something!
Downvoted. Thanks for the weak pretests which made my solutions for both B and C failed system test.
May I call this FSTforces?
system testing is a massacre for us noobs
Contrary to the opinion which seems to prevail in the comments so far, I quite like it when the pretests and the system tests are not of the same effect. It gives more value to local testing, which is definitely a useful skill on contests outside Codeforces.
So, just wanted to chime in with it, otherwise the discussion looked pretty one-sided.
I think that it should've been announced before the contest, not after it during the full tests. I believe that programming contest site is not a place for such surprises.
I can understand disliking the system or being disappointed that your solution fails.
But one thing that really bothers me is the attitude that it is somehow the authors' fault if your solution fails system tests. It's still your faulty code. Please accept that.
Well said.
Related, from personal experience: once I transferred from the mindset like "my programs are awesome and so CAN'T fail" to the more realistic "my programs are still awesome but WILL have bugs", soon enough, my programs had less bugs. Still nowhere near zero though.
If the purpose of pretests is to act like the real tests, but to reduce the load on the servers during the contest, then technically every time a submission fails to system tests it is the author's fault.
Of course if your solution fails, it's your fault for writing buggy / incorrect code, but why does that discredit saying that the pretests being weak are a problem?
Alright, it's the first time I see it formulated like this. So, unlikely that this is what the platform authors envisioned.
Or maybe I just didn't follow.
The purpose of pretests is to make the most unreasonable solutions fail.
Quoting this blog from MikeMirzayanov
Most importantly:
I think nowadays on Codeforces pretests are supposed to contain at least tests with maximum size of input, maximal value of n, etc. However the coverage of corner cases does vary a lot.
8 years ago
I think the idea of pretests was distorted (sorry for my english), so these tests have changed into a reduced variant of systests. The fact that your solution can be tested precisely during the contest seems casual but common and, in my view, more practically-oriented. Anyway, contesters got used to it, so all these protests and downvotes things can be understood. 3 of my 4 solutions failed on systests, so I as a submit-see-green-proceed person was upset and could understand them.
Then what's the point of pretests? It's pretty unfair if some special cases are covered in pretests and some are not. Should the pretests just cover the samples?
Also, if pretests are weak, the hacking system is incredibly broken: How much you score becomes very dependent on the room you are in (how many people had easy bugs to find), The score you get highly depends on whether you get hacked or not, since getting hacked saves you from failing to systests, and, say two people in the same room find some corner case, now they are competing in speed at noticing that someone submitted to a problem, and hacking that person.
Of course you write a brute-tester when programming in the real world, but even if the pretests are very weak, it is not necessarily correct to write one. You just have to make the decision to risk failing to system tests, or wasting time writing a brutetester. I find it much better that you don't have to guess whether your solution has a bug or not before writing a brutetester. With strong pretests, you still have to find what the problem in your code is, which I think is the main part of debugging anyways (not finding out that a bug exists in your code).
Conversely, if passing the pretests should always mean passing the systests, then what is the point of systests?
Reducing the load on the servers during the contest, and preventing reverse-engineering the test data.
Additionally, all successful hacks are added to the system tests, but there is no way to add hacks into pretests.
The first point is moot assuming you want no solution that passes the pretests to fail the systests, excluding hacks.
OK, not arguing your points for now, but asking a question instead.
What, in your opinion, would be the best difference between pretests and system tests? Your comment sounds much like you'd want them to act the same. Well, we have plenty of other contest platforms which have exactly that: no pretests.
For a platform where pretests and system tests are two distinct entities, it makes perfect sense that they have observably distinct effects.
Topcoder has very nice hacking system. All pretests are open, so you can see for yourself, how strong they are. Almost every contest a lot of solutions get hacked or fail systests, but noone complains that pretests are weak.
On Codeforces, you have no idea how strong pretests are, which often feels frustrating.
On TopCoder, people also complain when pretests are weak :) .
And yeah, the pretests system on Codeforces is far from perfect because of its quirks with uncertainty. Hey, if there was no uncertainty, there won't be vastly different expectations for pretests, and there won't be this thread!
Still, it is possible to utilize the imperfect system, and it is possible to effectively shut down the pretests-and-hacking part of the contest. Both happen, in different rounds. I just like the former option better, is all: we have plenty other platforms for the latter.
If I hypothetically (but not really) found a test case that breaks my solution (and possibly other people's solutions) to a problem, even though it passed system testing, am I obligated to release that test case? (Or maybe a better question is do I want to.)
People have done it before. I remember one time in particular recently the case mentioned broke like 4 out of the top 5 contestants' solutions or something like that. I imagine it only helps, because it lets the authors know that their tests could have been stronger.
This test won't influence the standings for this round, but we can add it to the tests for upsolving.
My test case for problem D:
It is specifically designed to break my code, so I don't imagine it would affect rating changes that much anyway besides for me.
Expected output?
Yes
Another Testcase:
3
2 3 6
A couple of accepted solutions fail this, one such example: http://codeforces.me/contest/1025/submission/41858091
Wrote a script to determine the prize winners (sorry for the ugly code): link
I am 11th in this list :(
UPD: System testing is over, nothing changed.
why cf predictor is not showing anything ?
Looks like CfPredictor failed the System tests..
Good One!!!
Could someone tell me the reason why changing '&' with '&&' between two booleans give TLE. Solution with '&'
Solution with '&&'
The
&is a bitwise operation.The
&&is a logical operation, and has the benefit of short-circuit boolean evaluation: if the first argument is false, the second one is not calculated.Perhaps this meant a lot in your particular case, when both arguments are recursive calls.
Thanks. I think the time limit was too strict in D, that's why it failed sys test. They should give n = 500 for O(n3) solution
Or they could have increased TL to 2 sec. O(n^4) wouldn't have passed in 2 sec anyway. I was using ll unnecessarily instead of int which gave me TLE.
Because
&is bitwise AND and&&is logical AND. Logical AND is short-circuiting, which means if the first operand determines the result, it will not evaluate the other.EDIT: Oops, someone beat me to it :P
The announcement has failed system test too.
codeforces need to organize more combined contests(div1+div2). bcoz i think solving more not easy problems with stronger participants let us to rise faster
How to solve D ?
It seems that a number of submissions with time complexity O(d(a1, b1)·n) passed problem B, where d(a1, b1) denotes the number of divisors of at least one of a1 and b1.
However, there are only tests with large d(a1) (number of divisors of a1) and d(b1), but not large d(a1, b1): there may be many duplicate divisors of a1 and b1. For example, 1396755360 and 1102701600 are integers having the most divisors (1536 and 1440) below 2·109, but there are only 2208 different divisors of at least one of them.
I generated a pair of integers for a1 and b1 below 2·109 with the most d(a1, b1): 1889727840 and 1715313600. They have totally 2760 different divisors. I think it would be better to add something like the following case to the practice version of the problem:
Out of curiosity, how did you generate these numbers? I couldn't figure out a way to do it that would run in a reasonable time and I also couldn't find the numbers online.
I searched the prime factors p = 2, 3, 5, 7, 11, ..., and multiplied them to a1 and b1, that is, multiply a1 by p0, p1, p2, ... and multiply b1 by p0, p1, p2, ... each time. Of course we do not want to waste a small prime and use a big prime, so we should avoid multiplying p0 to both a1 and b1.
It seems kind of brute force searching with some pruning, but it runs only 72 seconds on my computer. I couldn't analyze its accurate complexity. (x, y denote a1, b1, and xrem, yrem denote 2·109 / a1, 2·109 / b1 in the following code)
I think it can even be a nice (and hard) problem in some round (given n, find a1 and b1 below n with max d(a1, b1)) if someone figures out some optimizations to make it run in several seconds :)
Added, thank you.
Thanks God this test was not in original system tests! My solution 41848942 got accepted in 1185 ms but now it gets TLE on the test #99.
My code still passed this test in practice in
1465ms.Link
We love you so much, GreenGrape... Wish you are already preparing next contest.
With no pretests at all. Only 2-3 examples.
When I click on Editorial, it says "You are not allowed to view the requested page". Please fix it. Edit: Fixed.
Is it rated ? Cause i don't see anywhere about rated or unrated announcement.
Rated.
can someone please help me in debugging my code. I've no idea why it failed on test 45.
code link. My dp state is dp[i][j] -> if the root is ith index vertex and we have to assign tree upto jth index (actually I skip a dimension. instead of having l, r I have single j as we know if j is less than current root then (l, r) == (j, i-1) else (l, r) == (i+1, j)).
Your solution is correct but you were forgetting to set your
ansvariable in a couple cases, so the second time you visited those states you returned an invalid memoized result.Fixing that gets you AC: http://codeforces.me/contest/1025/submission/41869888
thanks for the reply. But can you tell me one thing that why it matters? because at first I've already reset my dp table to zero and hence if 'ans' is not set then will it not safe to assume that it will be unset?
The lines with
return ans = 0;are unnecessary like you said (I only added them for completeness), butreturn ans = poss[i][root];might betrueso that's when your previous code failed.Sorry I actually missed that line. After trying for 1 and half hour I'm thinking that the entire solution is wrong. Thanks a lot again :)
I see that this contest was received kinda badly as this blog post has -27 votes. It seems that only thing people complain about are weak pretests. There were no other issues (ok, maybe I can add dubious constraints for D), problems were fine, statements were clear, no CF hardware issues lowering overall experience etc. I think that these downvotes are way too harsh
With all due respect, I doubt if you'd feel so if you lost your rank 1 because of some systest-failed B or C or D.
the thing that was too clear, was the fact that authors didn't spend time on making strong pretests, bc that was not a thing that they can not do it. also i have a bad feeling about all rating changes, some wrong solutions that get accepted (on the first contest's D), but i believe that for first contest's A, even though the pretest were weak, every participant could take the tricky test cases from the problem statement itself (it means it was written good) i couldn't take part in second contest (even though i liked to), so i can't say anything about it. at the end, i believe contest weren't very bad, but our expectations were so high (Why, our expectations so high — eminem )
"the fact that authors didn't spend time on making strong pretests"
disagree. It's just author want participant get FST XD.
pretest is always a trap, that's why we calls it pretest : )
its ok to catch some solutions in that trap, but half of them??? i don't know
in fact I think the only bad thing with weak pretest is that lucky participant may get more hacks. but for weak pretest it self, I think it's ok.
We should judge our sulution by it's logic but not it passed tests or not.
especially it's pretest.
when you get weak pretest, everyone else get weak pretest too.
As the result ,it's you choosed to believe in the pretest
My B also got FST because I checked all factors but not prime factor.
max number of factor(in 2e9) is about 2000 numbers(as I culculated at local)
And prime factor is about log(x),but I expected this 20min later
I think codeforces is fast and choosed not to resubmit to avoid lose 200 points
And as the result I losed 840 points XD
there is nothing wrong, nobody forced me not to resubmit : /
Because pretest is an issue that causes tons of lower level contestants to fail things that they would otherwise have passed. And it is more significant than bad statements.
Hardware issues are not the domain of authors.
Maybe these downvotes are due to some bots? As happened on Announcement page of Round 502.
Any one else thinks random pretests are stronger??
when you considering : " come on, codeforces super fast and I get PP with 120ms "
If you guys knew that the pretests were going to be weak because of the author or whatever, why didn't you just take the extra 5-10 minutes to do local testing/try to prove your solution is correct?
In such contests, I indeed feel very fortunate that I got my C hacked during contest, and then I got a chance to get it accepted :)
End of the coding weekend! Thank you Mike and CF.
In prob D, I approached it with DP with the parameters left, right and root
So, I guessed the Time complexity will be about O(N^3) but when i made a random test case of 700 it took so long
Then I changed the DP table, and I got MLE...
http://codeforces.me/contest/1025/submission/41864181
Can anyone tell me where I am wrong?? And, what is the right sol?
700^3 is 343000000 ~ 3e8, no surprise you get MLE.
std::vector packs the booleans, but I don't think raw arrays do, so if you want to just decrease memory usage, you can use vectors over raw arrays.
Pretests too weak, Hackforces?
These submissions are identical, but my solution got tle in system testing :(.
http://codeforces.me/contest/1025/submission/41880498
http://codeforces.me/contest/1025/submission/41858978
Different machine stability. If u ac,it is lucky. Else it will be TLE.
too strictly time limit
In 1025B - Ослабленный Общий Делитель
I have a solution and got Accepted but I find a test case can hack the solution:
Solution:41885803
Test case:
Expected -1 but this solution got 3. Hacked myself :-)
Oh my god — they created change.org pull
Your text to link here... Why is this B right?
GreenGrape My solution 41866649 was accepted .But i hacked it .
It should be output "YES". But my solution output "NO".
Lol, ACM was my life for 5 years, but thanks to you I realized just now what its logo is meant to show.
I still don't get it, can you explain?
thinking thinking continiously then suddenly an idea strikes you or the aaahhh moment and AC(ballons as you get after solving a problem).
ohhhh, balloons for AC is clever
why this solution can ac http://codeforces.me/contest/1025/submission/41902787 but this will tle http://codeforces.me/contest/1025/submission/41905132 only change "dfs(l,i-1,i)&&dfs(i+1,r,i) " to " dfs(i+1,r,i)&&dfs(l,i-1,i) "
If you write “a&&b” and a is false,it won’t be true.So we can return false instead of calculating if b is true.
left first will ac right first will tle I think this mean if I reverse the test data thr data can hack most solutions
Yeah.Sometimes the hackers or examiners makes the most extreme data.Like random algorithm,SPFA(Shortest Path Faster Algorithm),BST(binary search tree) without adjustment(for example,Splay),will TLE.
So if “dfs(l,i-1,i)” are almost false,but “dfs(i+1,r,i)” are almost true,It will be TLE. And sorry for my low English level.
And the same rule as “||”
Hi Everyone. Tried to write down A and B's solution. Here's the link. Editorial for A & B
I was looking at the fastest solutions to the problem D and found this one — 41869905. What the heck is this?
It seems like the author of this solution just explored the tests where his solution is failing and added a simple heuristic. Indeed, it seems like there're no tests with n = 4 and the answer "Yes" which is sad.
When do we get the editorials?