Привет, Codeforces!
Рад пригласить вас на Codeforces Round 559 (Div. 1) и Codeforces Round 559 (Div. 2), которые пройдут в 12.05.2019 17:35 (Московское время). Раунд будет рейтинговым для обоих дивизионов (я надеюсь).
Все задачи были придуманы и подготовлены мной. Большое спасибо Aleks5d, TLE, sunset, Sulfox, peltorator за тестирование задач и ценные советы, 300iq за координирование и помощь в подготовке раунда и MikeMirzayanov за отличные системы Codeforces и Polygon.
Вам будет дано 6 задач в обоих дивизионах и 2 часа на их решение. Советую прочитать все задачи. Удачи, высокого рейтинга и удовольствия от решения задач!
UPD
Контест завершился, поздравляем победителей:
Div1:
Div2:
Orz Sulfox, wish I will be red too!
Orz
memset0 can AK IOI!
Orz Sulfox
I'm not peltorator, I'm peltorator. Fix it, please.
No, the information in your nick is false.
I don't really care. Orz isaf27
orz demon1999
Actually, I have just found out that orz iz not just a meme word that can be added to anything with no actual sense, it's a Japanese word meaning frustration: https://www.urbandictionary.com/define.php?term=orz
So don't repeat my mistakes and don't orz anything you want!
you are behaving like a granny who tries to use the Internet
Here we see a Tsundere in his natural habitat
Please,No MathForces !!!
But why? The latest Mathforces was quite good!
UPD1: The round is carried over for 20 minutes.
UPD2: The round is carried over for 15 minutes.
UPD3: The round will be unrated.
People who has +200: Why do I participate?
Okay! Thank u for your unreasonable voting :V
I guess he will consider, if you give him some RAMADAN special biryani xD
FYI Ramadan is not about eating but fasting.
By the way, they don't eat Biryani in Russia :V
Hahaha,can't see your message at all
It's hard if not impossible to consider the prayer time. Because the prayer time in every country are not same and people from all over the world participate here. And every minute is a prayer time in somewhere in the world. So when do you suggest to schedule the contest?
Moreover, this platform have people from many religion, culture and region. The platform must not run by considering any religion, culture or region. The platform should be secularist and International.
I like the weekend contest, thank you.
I like the weekend contest, thank you isaf27.
I hope this will be IMO contest from isaf27, not 2 problems like "write a segment tree" and 4 problems like "write a link-cut tree with operations ADD, FIND_SUM and REVERSE_ALL_BITS in $$$ne^{\sqrt{\log n}}$$$ time and $$$n\log^{2.39}n$$$ memory".
Hope is a good thing.
maybe the best of things.
and no good thing ever dies.
Hope die the last)
I completely agree with you. Hope there will be some problems like find the equation of Euler line $$$\dots$$$
Actually, I gave the problem about Euler line to isaf27 and he didn't solve it because of its extremely high idea level, so I don't think we'll see it in the contest.
Please, don't discuss the problem from some contest in the future
Yes, I hope nobody runs into this discussion and sees any ideas of problems that are to be used in the future.
Blah-blah, blah, blah, so, isaf27, does your last statement mean that we can find the optimal length of twix in $$$\mathcal{O}(1)$$$ time per query?
We should find a formula dependent on the volume of Lipton. I can't answer your question now, it's too hard.
what's twix? what's the volume of Lipton? Could you give some links?
Never mind, local jokes :)
Have I misunderstood you? Do you want Mathforces?
Smh, All red contest. Hoping it will be balanced.
Sulfox is our red sun!
I guess there will be a massive drop in participation from India due to the finals of IPL. (Once in a year).
Fortunately it won't affect div1 much.
Good one
nice one!!
[deleted]
looking forward to Sulfox 's contest!
This is not my contest. I just test these problems for the correctness.
Will your profile picture change to megagnar when you're angry
Maybe he is looking forward to the one in the future.
Bad schedule for Man City & Liverpool fans! :p
good schedule for CSKA and Zenit fans
help me pls :(
Am I the only one who is facing problem accessing the problems and submitting the solution? Each time I submit the solution I am getting the verdict "You have submitted the same code before" but in "my submission" tab I am not able see the submission :(
It's almost half way and I am facing same problem now even! Can't submit my solution for A and B (or don't even know if they has been submitted successfully or not?) Doesn't matter which problem I am going to submit, I receive the same verdict all the time :(
unrated? site was down for the first 30 minutes for some people
Maybe we can finally switch to using dynamic cloud providers instead of fixed hardware in the ITMO basement?
Why is it impossible to register on m1.codeforces.com? I tried to register 10 minutes before the contest but the main site was down so I couldn't. And I can't even read the problems if I'm not registered. :(
I'm doubtful if the round should be rated. Quite a lot of people throughout the world experienced traffic issues. I think that absence of the score distribution in the round announcement post at this moment (45 minutes have passed) indicates the severity of the problem.
Everyone knows that the problemsetters, the coordinators and the Codeforces Headquarters endeavored to deliver the best contest. The same applies to the current participants, who tried to solve the prepared problems despite of the mayhem. But is there any reason to persist a rated contest if the impact of the techincal issues is apparent, for the sake of sportsmanship? Unrated contest is not a total failure; there are things to gain and learn, and the efforts of the contest managers do linger.
Sorry about the technical issues, it seems some misconfiguration happened in process while I jump between servers. I work hard to diagnose and fix it.
The notice about the micro-sites (green information bar in the header) appeared about 1 hour before the contest. Also I remind it in the official Telegram channel. Am I right that m1/m2/m3 work good without technical issues? I think it means if you follow recommendations you was able to read and solve the problems without any timeouts.
But i wasnt able to know scoring distribution, and i couldn't view standings.
Neither was anyone else, which at least is fair.
m1/m2/m3 worked perfectly for me. It loaded almost instantly.
It was fine, i didn't know what to do the first 2 minutes but then it was fine just like a regular contest.
Yes , light weight sites worked good ...i submitted 3 problems from there without any unnecessary delay. Thank You!
You can't log in to m1/m2/m3 sites with a google account because of which I couldn't submit for the first 15 minutes.
MikeMirzayanov crashed his scooter into a rack of servers,so site was down for 30 minutes .Is the round still rated?
There is no reason to make the contest unrated. The technical issue was in the beginning of the contest. Everyone could use m1 m2 or m3.codeforces.com. Participants who didn't use those sites and therefore lost time could still decide not to submit and don't participate in the round. Submitting code means you could use the system well or you accepted that you lost time. Everyone who submitted code made the decision to participate in the rated contest.
.
Main site was down at the start for less than 10 minutes. All the mirrors were still up. Rounds have been rated in more drastic cases, if I remember correctly. So please make this rated, even if the participant count was lower than usual because of technical issues.
Last week we got an unrated round because of weak pretests on problem A lol.
That round being unrated was one of the worst disappointments I have ever faced
I agree. That contest was all right except problem A.
for me the page didnt work normaly for like 45 min
That's unusual. I had no downtime on the mirrors and only like 10 minutes on main site.
Neither did anyone else.
The main problem was even though I tried to use m1/m2/m3, somehow I wasn't registered(though I was), so I had to wait for 20 minutes to register and then submit solutions to m1. I guess I'm not the only one, who was unregistered without knowing.
Then why didn't you register in advance? It is not that the site has been down for the whole time it has been able to register.
I was registered in advance, but then system unregistered me, so I couldn't enter the contest on m1/m2/m3.
There are almost 24 hours that can register. When did you register?
Someone posted the solution to div2 A in the blogs already lol.
Problem D is Windy Path (Problem L) from the 2016 ACM-ICPC Pacific Northwest Regional, with slightly higher bounds.
Thank you. I was sure that I saw this problem in some contest but couldn't remember the exact contest.
The bounds is not important. I'm sure that almost people have the same solution for both.
Good tasks, thanks!)
изи)
Div 2C was a little unclear. Spent 20-25 minutes trying to understand what the question meant.
TIL you can submit in the mini-sites. I just read the problems :/
Doesn't matter much for me though since it took me so long to solve A that the servers were up when I was ready to submit
Me: Reading the problem statement of Div 2 C
made wild assumptions and passed for some reason
Can you please explain why it was so hard to understand? It got two clarifications and I could not understand why.
The statement was confusing. The word "some" was somewhat misleading. I would have separated the key sentence into two sentences as follows: "Boy i gave at least b_i sweets to each girl. Girl j received at most g_j sweets from each boy."
In theory everything was written in the statement, but for example I thought that each boy has to give at least $$$b_i$$$ sweets each girl and I couldn't get it right without asking a question to first sample.
I thought bi is the upper limit for the number of candies the girls received from each boy. Then I figured out that is wrong, so i thought it means the upper limit for the total number of candies received
Actually the main reason for the problem should be my poor English...
There isn’t any actual problem about the statement, everything should be alright after reading the samples I guess
How to solve C?
Hint: Solve the problem assuming there are no missing values, after that it will be easy to extend it to the general case.
You can see my greedy solution (but i cannot prove it). Answer my comment if you have questions. 54046042
You uploaded Div2 C code, but T1duS asked Div1 C.
I already got it. I forgot that there is a div1 in the same with div2
Build a graph for relative order of p : if p[i] < p[j], there is an edge from i to j
If there is a valid topsort order, there is the answer
We build an edge from i+1..next[i]-1 to i and an edge from i to next[i].
However, there are O(n^2) edges.
To solve the problem, use segment tree to represent a range of nodes build two edges from [l..r] to [l..mid] and [mid+1..r] so there will only be O(n) number of nodes (not more than 4*n)
EDIT: Hope I won't get TLE on systest :C
EDIT2: Accepted :D
I think there is an easier solution. For any -1 in the input, use i+1 (point them at the next node); this should not change the existence of a solution. As you read the nodes, keep track of the previous nodes that point at following nodes with a stack, and make sure they nest properly. Finally, sort the nodes using (next_i, -i) and assign values according to this order. I think this works . . .
It is sufficient to add edges of two types:
i to next[i]
the first index j to the left of i such that next[j] > i (if it exists), where we add an edge from j to i
So there are only O(n) edges anyway. (Code)
Couldn't get an AC in the contest. I used a greedy algorithm.
Let us try filling the array smallest to largest.
We can observe that if next[i] = j, than for any x, i < x < j , next[i] <= j.
Also, permutation[x] < permutation[i] < permutation[j] . We can just fill the subarray (i+1 to j-1) first, and then fill i.
We can then go on working on array starting from j.
How about making the round rated for only positive rating changed users? (This happened previously in codeforce)
When? I think this would cause huge inflation.
That would lead to rating inflation.
This has never happened before
Why? The only upside is that it would make everyone "feel good".
Div 2E seems to be easier than Div 2D.
How to solve Div2D?
Try to write a brute force and observe patterns. ;)
The key is the number z = (n — k) / 2.
You build a string with [z zeros, a one, z zeros, a one, ...]
e.g. n = 14, k = 10, 00100100100100
You can repeat the pattern 0000...001 over and over up to n length.
The number of zeros in the repeating pattern is (n-k)/2.
I am actually surprised why there has not been more solves. Makes me doubt the solution
I couldn't figure out this pattern by myself. What was the idea behind it to came up with this idea?
Tried some things with pen and paper, observed the pattern, coded a brute force solution and observation proved valid for all n upto 20. So, went for it : P
Even in the examples, u can see the patterns...
Say you are given $$$n$$$ and $$$k$$$. Set $$$d = \frac{n-k}{2}$$$, $$$l0 = floor(\frac{d+2}{2})$$$, $$$l1 = floor(\frac{d+1}{2})$$$. Now the string of $$$l0$$$ zeroes, $$$l1$$$ ones, repeat works. The special case is $$$k=1$$$, in which case you can only have one 0 or 1, and can use 0111... as your string.
This works, since the string is cyclic with length $$$l0 + l1 = d+1$$$, and the start-point x (zero-indexed) of some substring mod $$$d+1$$$ uniquely determines its content, and the content for all residues is different. Therefore WLOG $$$x \leq d$$$. Let $$$s$$$ be the length of the substring. We must also have $$$x + s + (d+1) \gt n$$$, since otherwise the string occurs again $$$d+1$$$ characters later. So now we have: $$$s \geq n - x - d \geq n - 2d = n - (n-k) = k$$$
Completing the proof.
Submission: 54040228 (function count is unused, I just used it to test the code)
Is the formula $$$n + 1 - 2 \cdot (\frac{n-k}{2} + 1) = n + 1 - (n - k + 2)$$$?
You're right, the inequality should have been strict. Fixed.
Besides, do we really need to treat k=1 as a special case? I just use the overall implementation and i still got an accepted.
I can not access the site util the contest had passed 20 minutes. Stabilize the main site plz.
and problems need clarification too!
Smh, the issue has been already raised almost 10 times before your comment.
How to solve C?
I repeat my comment, but anyway : "You can see my greedy solution (but i cannot prove it). Answer my comment if you have questions. " 54046042
Maybe he means Div1 ???
If you see a purple or a red guy asking for C, its probably not Div2 C that he's asking for.
make $$$nxt_i = i + 1$$$ for each $$$i$$$ $$$(nxt_i = -1)$$$
When I asked why Div2C sample3 's note said the first boy presented 1,2,1 sweets instead of 1,1,2 it just replied me to read the global announcement :(
(The problem has been fixed without announcement during the content.)
How to solve div1D?
Problem D is Windy Path (Problem L) from the 2016 ACM-ICPC Pacific Northwest Regional, with slightly higher bounds.
I think traversing convex hull and recalculating it after removing a point each time should do the trick.
Lemma: Given any point $$$P$$$ on the convex hull, there always exists a solution that starts at $$$P$$$.
Proof: We use induction (with the algorithm below).
Clearly we can do it for $$$N = 2$$$. For general $$$N$$$, let $$$X$$$ and $$$Y$$$ be the points adjacent to $$$P$$$ on the convex hull. Because the entire set of points lie on one side of both the lines $$$\overleftrightarrow{PX}$$$ and $$$\overleftrightarrow{PY}$$$, we choose $$$X$$$ to be our next point if the first direction is to turn left, otherwise $$$Y$$$ if we want to turn right. Then we can remove $$$P$$$ from the set of points and continue by induction on $$$N - 1$$$ points, as $$$X$$$ and $$$Y$$$ will still remain on the convex hull after removing a point.
Time complexity is $$$O(N^2)$$$. You don't need to find the entire hull; you can find $$$X$$$ and $$$Y$$$ in linear time using one step of gift wrapping.
If I make 2 submissions for a question, both correct.. will the first solution be checked?
I think olny the last one accepted in pre test.
the first sumbissions are skipped, only the last one is valid.
Very Unfair Contest. First Server problem,then Div 2 C not clear and also announcement were not upto the mark.It should be unrated.
I did terribly, but I still think it was a good contest. Although CF going down all the time is really annoying, there are m1/m2/m3 sites that work pretty consistently. Also div2c/div1a wasn't that unclear. They explained anything that might be confusing under the samples.
Learn Russian :)
div2c was rather clear
but there are some noobs who cant read
It seems that the English version was more ambiguous than the Russian version.
Hello, non-master
hello, geylord
I am a newbie. How to solve Problem(B) Div 2.?
This is how I solved it. First of all, notice that we can rewrite the $$$k$$$-extension condition for a pair $$$(i,j)$$$ to the following:
The important observation is that the right hand side of that equation does not depend on $$$k$$$, so for every pair we have an upper bound to the value of $$$k$$$.
Since this must hold for every pair $$$(i,j)$$$ such that $$$1 \leq i,j \leq n$$$ and $$$ i \neq j$$$, we conclude that an upper bound for $$$k$$$ is $$$\underset{ 1\leq i\neq j \leq n }{\min} \frac{\min(a_i,a_j) }{|i-j|}$$$, since $$$k$$$ should be less than all those upper-bounds in order to be a $$$k$$$-extension. Moreover, by definition we have that all $$$k$$$ that are less or equal than that number work. By choosing the biggest $$$k$$$ as possible (which is the smallest upper bound) we have our answer.
Now that we know what the answer is, the remaining question is how to calculate it efficiently. An idea to do this is to find a small amount of candidates for those pairs and calculate the upper bound only for those pairs. To do this you can prove that the pair that attains such minimum must necessarily be paired with either $$$a_1$$$ or $$$a_n$$$, this gives us only $$$2n$$$ candidates and we can simply try all of them.
1159D - The minimal unique substring
What is wrong??
54043161
Maybe I am wrong as I am from Phone, but it seems for 9, 5 it would give 101010111, which has shortest unique 3
omg its true... Thank you for the information!
Had the same idea, but realized it would fail for larger n values...
какова причина делать мультитест в C?
чтобы ТЛлили все решение не за O(n) / O(n log n)
имхо
Ну или для того, чтобы все поучились чистить инфу для каждого отдельного теста
Ten minutes after the game I saw the surface, sad
You think the geniuses are those who prove the Fermat's theorem? No, the geniuses are those, who made div2 D )))
This round in a nutshell : "I'm just gonna make some crazy assumptions and hope they pass the tests." Also, the difference between C and D was too much.
D was not that difficult. If you can brute force, you will easily find the pattern.
However, if you are talking about clarity in problem specification, I agree 100%
You've got a good point, perhaps I_Didn't_Do_Enough_Things_For_WA
почему после проверки сразу не дают баллы?
Can we see the tests pls?
How to solve div1C pls?... :)
In this task we just need to check, that topsorted-order of vertices is correct.
Can we see the tests pls?
Hello，I got some questions with problem C (Div2)
for
2 1
0 0
1
I think the answer should be -1.right?
I missed this situation during the contest.And I think my solution 54038745 will be WA after system test，but it's still accepted Σ( ￣□￣||).
The minimum value of N and M is 2.
thank you
That single constraint snatched all my hacks
I think that case is not valid, n and m must be at least 2
thank you
How to solve Problem B?
for every item in the array, the value of k for that specific item = value/distance, where distance is maximum distance possible i.e either from 1st or from the nth item, now from all these values of k the minimum one is the answer. Pseudo code : i from 1 to n k=min(k,a[i]/max(n-i,i-1) print(k)
I am not getting why we are taking individual values min(k, a[i]/max(n-i, i-1) ? aren't we supposed to consider the every pair? i.e.min(k, min(a[i], a[j])/|i-j|) ?
We can take individual values because in min(a[i],a[j]) if we take individual values it won't affect our answer in the end, because even if we calculated for the bigger value also, when taking min(k,a[i]/dist) that value will automatically be eliminated .
Can you tell me why my submission to Div.1B got WA on test 22?
Test 22 is $$$(n, k) = (5783, 2359)$$$, and my output is '0{$$$1067$$$}10{$$$2357$$$}10{$$$2357$$$}' (0{$$$n$$$} means $$$n$$$ zeros) Judge says minimal unique substring for my output is 1069.
Edit nvm I read it wrong
as tfg said 0{1068}1 i completely overlooked that mybad
For t="0{$$$1067$$$}", I think we have at least two $$$l$$$s in problem statement, $$$l=1$$$ and $$$l=1069$$$...?
0{1067}10 appears more than once
0{1068}1 happens only once.
That`s it
In Div2E/Div1C.
Does anybody know why this 54049263 gives MLE? When I change stack to set I get AC in this 54047364
My Approach: Construct a directed graph where edge (u,v) means a[u] < a[v] and then do topological sort on that graph.
The way I construct it is if nxt[i] = j that means there is an edge(i, j), also there is an edge between all elements [i+1, j-1] and i since all of them must be less than i. I only keep track of the least previous element.
Here's an example where ix, jx means nxt[ix] = jx:
i1 i2 i3 ... j3 j2 j1. Edges are (i1, j1), (i2, j2), (i3, j3), (i2, i1), (i3, i2). I don't add (i3, i1) since it's redundant.
In a case like i1 .. i2 .. j1 .. j2 In the MLE submission I exit immediately and say that it's impossible. In the AC submission with set I let the topological sort handle it.
Change
vector<stack<int>> Pop(n);tovector<stack<int, list<int>>> Pop(n);and MLE should be gone. This is happening because when you pop elements from thestack, the underlying container (dequeis the default) is not actually freeing up space.dequewill hold the allocated space during the entire runtime of the program. So just change the underlying container tolist, which on the other hand frees up space when an element is removed from it. Now you are maintaining $$$N$$$ stacks which can have upto $$$N$$$ elements, thus requiring too much space if space is not freed when elements are popped off the stacks.listwill free-up space and your program wouldn't run into MLE. Also,setwill free-up space as soon as your erase from it. Thus your second program doesn't run into MLE.Thank you so much for the answer! I've changed the internal container from
vector<stack<int> > Pop(n)tovector<stack<int, list<int> > >once and tovector<stack<int, vector<int> > >once and both got AC without changing the other stack to set.However I've got 2 questions.
1- Shouldn't my total amortized memory be N not N^2? at each iteration I do at most one push_back in some deque in Pop[i]? even if I don't free up memory shouldn't that be fine because the total number of elements in all N deques will still be N? specially since AC solution passes in 27~35KB so I'm not on the edge of running out of memory.
2- Why does changing the underlying container to
vector<int>still pass although the vector doesn't shrink the capacity with the pop_back() calls either? I know that deque requires more memory than vector but is it really that much more?Please note that I've only changed the underlying container in
Pop. I haven't changed the other stack to set, neither have I changed its underlying container either. I've only made changes tovector<stack<int> > Pop(n).Here's the latest 2 submissions: 54094520 , 54094473
OMG finally purple! Gonna try not to lose this next contest lmao
and 2019 congrats man!
Thank you for your contest !!!!!!!!!!!!!!! I very love it
Please translate the tutorial to English isaf27, can't understand google translation of 1159D - The minimal unique substring's solution
I tried solving Div2 E with a solution of complexity O(t*nlogn) and am getting a TLE. Can anyone suggest why? Submission link — https://mirror.codeforces.com/contest/1158/submission/54055728.
I basically replace all -1's with a positive value in the following manner ~~~~~ int o = n+1; for(j = n-1; j>=0; j--) { if(inp[j]>0) o = inp[j]; else inp[j]=o; v.push_back(make_pair(inp[j],o)); } ~~~~~ I then sort this v vector and construct the answer array by using the values in the inp array. Finally, for any element if according to the input array, the first element greater than the current element(stored using a stack and array) is at an index before than that in the input array, then the answer is -1. The sorting step might be the time consuming step but I don't get how I am violating the time limit.
I think your problem might be this line:
Your ans array is pretty big and never resized, so for every input you're going to be running this loop over all of ans.
Can someone help me with Div2-D ? Not able to figure out the greedy approach.
English editorial anywhere?