<almost-copy-pasted-part>
Hello! Codeforces Round 624 (Div. 3) will start at Feb/24/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.
The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.
You will be given 6 or 7 (or 8) problems and 2 hours to solve them.
Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:
- take part in at least two rated rounds (and solve at least one problem in each of them),
- do not have a point of 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.
Good luck!
</almost-copy-pasted-part>
Thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for help with testing the round!
UPD: It turned out that in the problem C, such a test exists that the answer overflows 32-bit integer type (int). Since such a test was not in the test set, many participants made such a mistake. We decided to forbid such tests, additionally guaranteeing that the answer fits in int.
UPD2: Editorial is published!
[DELETED]
hahahah!!!!!!!
Finally a good freaking round
Can anyone help me how to hack a solution ? With detail's . Thanks in advance.
On the dashboard, click the padlock icon for locking a problem (Note, that you can not send your solution for a problem after locking it). Then go to room results, where you can see roommates codes for the problems you've already locked (you can see a certain solution by double clicking on it in the room results table). After you've opened someone's solution, you can consider it and then hack it. When hacking a code, you're entering some testcase on which that code is most likely going to fail (it may be wrong answer, or running out of time/memory limit). When you want to enter a large testcase, you can send test generator instead of typing it. Test generator must be your program which produces a file with a testcase in it. After hacking a code, you can see hacking results. There are two possible outcomes: "Successful hack" — it means the code failed, and you're rewarded with 100 points for that. Otherwise, it's "Unsuccessful hack" (the code did not fail) and you get minus 50 points for that.
In div.3/educational contests, you can not hack any solutions during the coding phase. In the hacking phase which follows the coding phase and lasts for 12 hours, you can hack any solution. Just double-click somebody to view his/her submissions and then click "hack it!" button.
there will be no points for successful hacking attempts and no penalties for unsuccessful ones in div3/educational rounds.
So in div3/edu contest. If I failed to hack someone's code, I wont get minus 50 points right ?
No penalties,just hack for fun :)
3 rounds in 2 days is very cool!
.
.
[DELETED]
Div3 gives confidence
Yeah have the confidence that i will never be a specialist ever :'(
you have just read algorithms and solve lots of high rate problems from it and you will become specialist at least :)
thanks for your suggestion.i'll try my best.
if you need help i will help you :)
Keep practising & forget about the rating changes.
a really good advice for a noon like me. appreciate.
Is it rated?
It's rated for Newbies, Pupils and Specialists. It is also rated for Experts who have taken part in at least two rated rounds (and solve at least one problem in each of them).
That's good.
I'll take off in this contest.
I don't like only Div.3 contest. Actually most people is more than 1600.
But in last div-3 contest there was 9000+ participants!
But they can take part out of the competition. It won't decrease the happiness of doing a contest. So Div.3 is very nice since it's easier and more people can have fun!
If you want more contests so please donate the codeforces 1000$ or more
But I don't have enough money to donate.Actually I am hungry, for I don't have money to eat rice.
If i register the contest but will not submit in the contest, will my rating change?
No.
Since you are above 1600 your rating will not change by Div3 rounds like this one.
Exiting to join the contest <3 Hope that I can solve A-B-C and dont get any stupid mistakes <3
Let's Hope Everyone gets a positive change in their ratings :)
Sorry I am a newbie,I wanted to ask what does it mean "The penalty is 10 minutes".Is it literal that 10 minutes will be deducted from our time,if we have a wrong submission or is it something else?
Short answer:
No it doesn't, it just is basically something that makes your score for that problem worse.
Long answer:
Basically in Div3 (and Educational Rounds or any other rounds that follow ACM-ICPC format), your score is calculated a bit differently from normal CF rounds. Participants are first ranked by the number of problems they solved. After that ties are broken by a so called "penalty".
This penalty has two parts to it:
A person with a lower penalty is ranked higher.
Consider for example the following contest with 3 participants — A, B and C and a wrong submission penalty of 10 minutes:
A solves 2 problems, the first at 5 minutes and the second at 30 minutes, with no wrong submissions on either.
B solves 2 problems, the first at 5 minutes and the second at 25 minutes, but makes a wrong submission on the second problem before submitting the correct solution.
C solves 3 problems, the first at 10 minutes, the second at 40 minutes and the third at 1 hour 20 minutes.
So A has solved 2 and has a time penalty of 5 + 30 = 35 minutes,
B has solved 2 and has a time penalty of 5 + 25 + 10 = 40 minutes, and
C has solved 3 and has a time penalty of 10 + 40 + 80 = 130 minutes.
As we sort them first by number of problems solved then by penalty, so the final standings will be:
Schrodinger's Problem Number
OMG first time I solve D <3
Screencast
How to Solve D? I tried thinking of it in multiple ways, but all my approaches seem to fail.
Fix B.Find A and C greedily.
Does there exist a proof that this approach will always work?
You can simply try all possible solutions in time. code
That's So Cool! I never thought that brute force would pass.
Well, it was hacked. So don't be too sure yet.
How does the hack work?
I'm guessing that it's because you're only going upto $$$10^4$$$ instead of $$$2*10^4$$$
Ah, I see, the input is limited to 1e4, but not the solution space. Sic shit.
So, 10000 100000000 1000000000000 could be a valid answer for some input.
Edit: It turns out that a,b,c should be all below 2*1e4, because if not there is a better solution. So, this code uses same algo but works better.
What should be the output for : 1 481 777 10000?
How did you decide the size of solution space ? Why 2e4 ?
One possible sol is allways 10000 10000 10000 for any input where max(a,b,c)==10000.
The max diff is 9999*2. So the max value for b and c cannot be more than 20000, whatever a is.
Not sure if this counts as a prof ;)
Why only 2e4 ? How did you come up with that upper bound?
We only have to show that a goes to A, b goes to B and c goes to C (you can prove this by considering all cases in the number line). Then you can show that B must be less than c+a. This can be proven by contradiction. So actually you only need to test it for 1<=B<=c+a
You need to check values up to 10k + epsilon for test such as
73 73 10000
How to decide that epsilon value?
20k should be more then enough (since if go up to 20k we can achieve all values in [0, 10k] with a smaller cost)
10.5k is enough. not 20k.
10^4 + 32 is enough. And no less because of:
tribute_to_Ukraine_2022 can you please explain, how did you concluded +32 would be enough?
We can slightly modify the model solution to pick out of answers with minimum distance the one with minimal value C.
Now for a fixed triple $$$A_0, B_0, C_0$$$ such that $$$B_0$$$ is divisible by $$$A_0$$$, $$$C_0$$$ is divisible by $$$B_0$$$ and $$$C_0 > 10^4$$$ if there is a testcase for which this triple will be the only valid answer, then one of them will be testcase $$$min(A_0, 10^4), min(B_0, 10^4), min(C_0, 10^4)$$$. We can just run the modified solution on this test, if it says the minimum value of $$$C$$$ is $$$C_0$$$ it means that there is a test, which requires checking values of $$$C$$$ up to $$$C_0$$$.
Now just run it for larger and larger values of $$$C$$$.
I ran it for $$$C <= 20000$$$ and found nothing larger than $$$10^4 + 32$$$.
Your solution for D has been hacked but it's still showing in standings
I fixed A and then find B as A*j and then find C as A*j*f.
you find all pair of a and b from 0 to 10^4(maybe more for safety) for every pair of a and b you find suitable third number nearest to original c. it probably cost you about n*log(n) for every test case.
So it will be O(10^8)*100 = O(10^10) operations right ? How did it pass the time limit?
No of course. let's call first number is a,second is b. we want a is a divisor of b. so we just start from a then go to 2a,3a,4a.to find every pair of a and b.it's only cost you about nlog(n)
it's just like erastothenes sieve without prime number
No, I am not sure about this. This is n^2.
errrrr it's running in n+n/2+n/3+n/4+...+1 which is prove less than nlog(n)
I'm not sure if i'll get hack xD but i believe in my solution
I got your solution, you are right. I just upsolved it now. Sad :(
i think this is (n^2)/2
it's n+n/2+n/3+n/4+...+1.not 1+2+3+4+...+n. dont be mistaken
Take (1+ 1/2 + 1/3 ......+1/n) as integrating (1/x)dx with limits from 1 to n......you will get log(n) as an answer for the summation for that series.
from : https://math.stackexchange.com/questions/206032/what-is-the-integral-of-1-x
You have ∫1xdx=ln|x|+C (Note that the "constant" C might take different values for positive or negative x. It is really a locally constant function.)
Thank you so much. I understood.
How can this algorithm cost n*log(n)?
Make all the possible combinations (A, B, C) with for-loops and compare them with the given (a, b, c)s.
The key is that neither of these three should exceed 10^4. (If they did, they would in itself be not the efficient solution) I have found just a bit fewer than 5X10^5 cases which satisfies (A, B, C). Thus, given that the test cases are 100, 5X10^7 seems like a good deal.
Brute force, if applied properly, can be a very powerful tool.
speedforces
I want an editorial ASAP :(
why is my code not correct in test2 about problem b?
https://codeforces.me/contest/1311/submission/71794691
You are running the outer loop 4 times,your solution will fail,If more than 4 swaps will exist for a test case. https://codeforces.me/contest/1311/submission/71814830 Here I just changed your solution a little bit and it got accepted.
How does one solve F with a complexity lesser that O(n^2) ? We at least need to consider all the pair of points for the minimum distance between them.
I'm also want to know it :(
The non-integer part is really helpful here — distance between points i and j will be either 0 (if they overlap), or starting distance (if they diverge). You can easily see, that for i < j if vj < vi then distance is 0. So, for each i we can find sum of xj such that vj >= vi (I scaled speeds to fit in a segment tree) in logarithmic time, then we can calculate everything in O(n log n).
Hint:
Here's how you would find the sum of the differences between all pairs.
Sort the array. Set sum = 0. Note that for every number, it will be subtracted from the sum a (number of numbers greater that it) of times, and added to the sum a (number of numbers lower than it) of times, so you can solve the problem in O(NlogN).
Can you please elaborate? I don't understand your solution fully.
His code: (https://codeforces.me/contest/1311/submission/71790025)
He didn't describe his actual solution yet, just an $$$O(N)$$$ way to calculate (xj-xi) for ALL pairs i<j. But then he goes through again in one pass, and removes those (xj-xi) which didn't satisfy (vj>vi).
I think I get the solution now after 2 hours of thinking. Maybe this example can help someone else. Say $$$x=[100,50,75,25]$$$, and the corresponding sorted $$$v=[1,2,3,4]$$$. First we sort $$$x=[25,50,75,100]$$$. Then look at the ways 75 gets added initially according to @golions comment:
(from 75-50, 75-25, and 100-75)
Now let's iterate through $x$ in sorted $$$v$$$ order: when we get to the third element 75, we see that we should only have a single
term due to the
. Coincidentally this equals the net sum of the three terms above. The reason is that if $75$ has the same rank in both the sorted $$$x$$$ and the sorted $$$v$$$ versions, then there is a symmetry in how $$$[25,50,75,100]$$$ mutates into $$$[100,50,75,25]$$$: we can let other elements "jump over" 75 to anywhere on the other side, and the symmetry is that the number of jumps going right over 75 equals the number of jumps going left: 100 jumped left, but then 25 jumped right. So the rank of 75 is equal in both cases, and we don't need to correct the $$$+75,+75,-75$$$ in our final answer.
Another case is $$$25$$$, which is rank 1 with respect to $$$x$$$, but rank 4 with respect to $$$v$$$: Initially we had
due to 50-25, 75-25, and 100-25. But because the rank changed from 1 (w.r.t $$$x$$$) to 4 (w.r.t $$$v$$$), we must have had 3 jumping overs to the left: and every such jumping over means we shouldn't have included a $$$-25$$$, so we correct with $$$+25$$$ 3 times, and end up with $$$0\cdot 25$$$ in the final answer.
Say you have the numbers 1,2,3,4.
The sum of differences is 2-1 + 3-1 + 4-1 + 3-2 + 4-2 + 4-3. Note that it's also equal to 1*(-3+0) + 2*(-2+1) + 3*(-1+2) + 4*(0+3). First number in parenthesis (that you subtract by) is the number of numbers that is greater than that number, and the second number in parenthesis (that you add) is the number of numbers that is less than that number.
This is not the solution to the entire problem, just part of it.
I think NlogN can be achieved with PBDS or compression with segment or fenwick tree, just use contribution technique.
Is this comment (https://codeforces.me/blog/entry/11310?#comment-162921) the right strategy for F?
I reduced the problem as follows: first sort by x[i]. Then for every i, sum (x[i]-x[j]) over j<i such that v[j]<=v[i]. Brute force would be $$$O(N^2)$$$.
If for every i, you consider all j<i, won't you do 1+2+3....(n-1) = n(n-1)/2 number of operations which is O(n^2) ?
Yes via brute force, but if you do the sqrt decomposition, you could sort by x[i], then put all pairs into a $$$\sqrt{N}\times \sqrt{N}$$$ grid, and sort each row by v[j]. Then given $$$i$$$, you can compute the number of $$$j$$$ which have both $$$x_j<x_i$$$ and $$$v_j<=v_i$$$, in $$$\sqrt{N} \log N + \sqrt{N}$$$ time. However given the constraints this approach might be around $$$10^7$$$ or $$$10^8$$$ operations. There is a better way given in other comments, so my question is moot.
i think d will be hacked most...
Perhaps it is psycholigal problem...but again I did not solve B :/
At least somebody tell me what is wrong with this code
Was able to locate the problem, this code works better.
I am in a great trouble..I don't know when will be the end of newbie era from my life..Really I am depressed..So,what can I do???
Seek some damn therapy instead of asking random internet strangers.
I'm getting
Unexpected verdictwhile trying to hack a solution for problem C.hey im new in everything, is there a post afterwards with the solutions? if not how to solve problem c? i got runtime error all the time.
Yes there are. it's called editorial
I also got a runtime error once. Mine was because the array size I declared was 10e5 (not sufficient). I changed the array size to 2*10e5 + 5 (according to the constraints), and it got accepted.
What is the hack of D?
in D I used 4*10000 that gives TLE but 2*10000 was ok. is there any other approach for solving D.
Very strong tests in problem D!
Very strong tests in problem C! (see announcement)
probem D. I went over B from 1 to 1e4, and of course I was hacked. who hates this feeling..
hey ? No hacking phase?
According to codeforces... Hacks will be open in ~10 minutes.
My solution for E : First arrange nodes so as to achieve max depth sum (mis concluded this part for like 20 mins), ie, a linear chain.Now consider the node at the bottom and move it up greedily as much as possible so that the change in answer is less than equal to current answer — required depth sum.(Initial answer is sum of depths of all nodes in the linear chain).If we cannot move a node anymore upward and we do not have the required answer, then it is not possible to form such a tree, otherwise it is.
Could anyone confirm this?
I made the opposite: first construct a balanced binary tree (parent of x is x/2), then on each iteration take two deepest leafs v1 and v2, and attach v2 to v1. On the last iteration, maybe, you should attach v2 not to v1, but to some its parent.
Each vertex is moved at most once, so it is N^2. Looks like it is possible to do it in NlogN, but we don't have to do it.
It passed stress test for n, d <= 50, I think it is correct.
Actually thanks for the idea of stress testing, i forgot the input is only n and d so it can be confirmed for all values of d in range vmin to vmax that answer is found by the code or not.
Where is hacking phase? Just hacked someone's code and it crashed...
Sad to see this submission :(
https://codeforces.me/contest/1311/submission/71777964
What the fuck is that though?
Why -1
I assume, he hacked himself from another account
How to solve E guys ?
I don't have proof(maybe someone can hack it), and use a random method(pretty fast).
first prep lower_bound&upper_bound of n. it's easy to note $$$ub[n] = n*(n-1)/2$$$. while $$$lb[n]$$$ can be find recursively, each time you divide $$$n$$$ almost half. i.e. $$$lb[n] = n-1 + lb[x]+lb[n-1-x]$$$, where $$$x=n/2$$$.
then try divide&conquer, for random $$$x$$$ and valid $$$n_x$$$, and so other son should valid. Since in intuition there should be many valid partition.
Sorry, I am just begin to learn Graph (5 dáys). Can you go in more detail. Thanks <3
Auto comment: topic has been updated by vovuh (previous revision, new revision, compare).
why it-my[tst].begin(); isn't giving the expected value that was so weird wasted 1 hour trying to figure it out
here's my submission
Is anyone facing issue of illegal contest id while hacking??
It works from the submission page. It can be opened by clicking on '#' in solution preview
Me , What does it mean ??
B in O(nlogn) https://codeforces.me/contest/1311/submission/71790807
if you use vector instead of set it is O(n)
Are you sure it is O(n log n) ?
how to prove it ?
I dont good at proving complexity, I dont mean anything, sorry
vovuh Some people are hacked but their submission still apear in scoreboard (such as https://codeforces.me/contest/1311/submission/71798202). Is it what the contest want?
I think that is because of at some moment hacks were disallowed but uphacking was allowed. So, it seems like you hacked this solution during the uphacking phase and it is considered as correct (but uphacked) solution.
And I don't know what I have to do with it.
My bad :(
Why was case of overflow not considered. :rage: . So what if many people fail.Will u add test cases manually everywhere where people fail. Totally unfair.
Why is 71783447 accepted, not hacked?
Probably because they changed the accepted condition
I made a mistake, they changed condition on C. But the mistake seems fair, why did they do it?
Wow, this is new to me too
Can anyone hack my B and D? I have written bad codes and think they can be hacked
Codeforces Hack Round #624 (Div. 3)
haha :D
Problem D should have such test case instead of getting hacked for almost the whole contest
Most people considered A,B,C <=1e4 including me which lead to hacking :(
This contest is too unfair. You fixed the test case for C while you didn't do anything for problem D. It was a fair mistake done by contestants in problem C. Why did you do this unfair thing?
Face reality, the whole universe is not a fair thing. It is a competition.
Very good round but unfortunately too weak test cases. I fell from 500 to 2500 after hack. It is unfair that you ignored hacks on C but not for D.
The test data of question C in this competition does not exceed the 32-bit integer range, so do you calculate the rating this time?
Why are you ignoring us vovuh? What if high rated guys protested? Would you be so silent like you are now?
please stfu, like you didnt even participate in the contest, what is your problem?
cyan revolution is only a matter of time..
SPEEDFORCES!!!
In fact, both C and D has poor test case and that's not problem. but why you change only C?
We changed only C because we had a bug in author's solution. I didn't have overflow tests (both mistakes in C and D are mine and I'm very sorry about that) and only one of three solutions considered overflow with
#define int long long. So we considered to change the constraints in such a way that this issue will not affect participants because I had a problem in my solution.The problem D issue is that it has very bad tests and I wonder how I don't have at least one test case (of hundreds test cases) with $$$C > 10^4$$$. It was really surprising for me and I don't even know how to generate such tests in advice (the only way I understand is to write such a wrong solution and stress it).
Anyway, this is just an excuse and I blame myself for these mistakes. Sorry everyone who was affected by my poor brain work.
UPD: And for all who think that I'm silent and don't want to accept my mistakes or describe you the situation. I'm so silent because now I just trying to do all I can: write the editorial as soon as possible and I trying to do that right now.
You can easily modify the model solution to minimize first: number of moves, then minimize C. Now iterate through all valid triples $$$A, B, C$$$ such that C lies in range $$$(10^4, 10^4 + 20]$$$, run modified solution for triplet $$$\min(A, 10^4), \min(B, 10^4), \min(C, 10^4)$$$ and if it says, that optimal solution has $$$C > 10^4$$$ we just found a countertest.
In the same manner you can defeat a solution, that assumes too tight upper bound on $$$B$$$ like 71800958
Okay, I see. Thank you for explanation! But I didn't even think that the issue "$$$C > 10^4$$$ in the answer" will affect and break such amount of solutions.
So just to confirm, submissions that display as Accepted, but are actually hacked, that depend on $$$A,B,C<=10^4$$$ will be judged as WA/Hacked?
For me the difference is between +149 and -5, so I'm a bit on edge :D
As you saw, the actual bound on $$$C$$$ is a bit larger than $$$10^4$$$, so I think that all solutions that only consider $$$C \le 10^4$$$ will be rejected.
what is approach for E and F?
Can u explain D
iterate over value of c(1 to 3*1e4) and for every c make a tuple {a,b,c} which holds property (c%b==0 && b%a==0) where a and b which are factors of c. So, now one of this tuple is answer.
just fix A and B then check that C which lie very close to c and satisfy the condition that $$$A$$$ divides $$$B$$$ and $$$B$$$ divides $$$C$$$ . Now for fixing A and B you can iterate A from 1 to say 10000 and B as a multiple of A from 1 to say 11000 simply like in seive algorithm .
NOW after fixing A,B and nearby C you have to calculate that this A,B and C deviates how much from original a,b and c . Iterate in the above described value and calculate the minimum value. Simply Cool Algorithm.
What is the largest possible answer in problem D? The largest I found is:
Input :73 10000 10000 Output: 2 73 10001 10001
I meant the largest possible number of moves
Check numbers that divide primes close to 10000.
There are not that much numbers dividing a prime.
How long does it take to update my rating after contest??
its after hacking phase ends
Help me with how you approach Problem D
Just do three loops for three variables, and check for minimum answer Something like this: for(int i=1;i<=10300;i++) for(int j=i;j<=10300;j+=i) for(int k=j;k<=10300;k+=j) if(abs(a-i)+abs(b-j)+abs(c-k)<ans) ans=abs(a-i)+abs(b-j)+abs(c-k),a1=i,a2=j,a3=k;
This will give TLE I think, can you help me with optimized solution.
ok I got it, It is some what like nested loops in Sieve for finding primes. Thanks for the help.
So I'm pretty sure this is cheating, right? Submission
Why say that?
Seems like they're purposely making the code obfuscated.
You can check in the Official rules that that is prohibited.
Wow, that's not cool at all.I didn't see the code thoroughly.
You are right. The function name 'zao123jia' is the pinyin of Chinese word '造假', which means 'cheat' or 'fake' in English.
LMAO. I mean, if you're gonna fake something, at least don't leave the word FAKE in it xDDDD
It's time to call vovuh.
This is obvious a rules violation, it is stated explicitly that you cannot obfuscate your code.
Calling vovuh
Is this a hackforces ?
I wanna hack someone's code but it told me "Illegal contest ID", and so I could not hack anyone's code.Could someone help me?
Try opening the submission page by clicking the "#" button. Then try to hack from there. It worked for me.
It worked! Thank U!
I'm a rookie. I took part in the game last night, but why didn't my rating change?
Hi! I don't see any rating changes for me. Can I understand why? I seem to be fitting all the criteria mentioned above
I'm just the same as you.
I'm a new user. I want to participate in contest. How I can? anybody help plz
Press the contest bottom and find the conteset which you want to take part in. Then press the red bottom Register to finish your registration.
Where is the educational round?
I mistakenly thought that in problem F the sum of minimum distances over all pairs of points means that I should determine a moment when each point move to a certain coordinate so that the sum of distances is minimum during all times...
Good luck everyone!