Once again, TREMBLE BEFORE THE MIGHTY OMEGALULRIPGRAPE.
(He last walked the Earth in round 538 btw.)
Hello Codeforces!
We are here to invite you to Codeforces Round #554 (Div. 2), which will take place at 24.04.2019 17:35 (Московское время).
The round will be rated for all Division 2 participants (with rating less than 2100), yet any Division 1 participants are welcome to join us out of competition.
The round will be cat themed. Raise your paws and prepare your catnips!
(Or even cat memes, while you're at it).
You will be given 6+1 problems ( 6 problems, one of them has 2 subtasks ) to solve in 2 hours. The round's problems were prepared by Xuan-Quang xuanquang1999 D. Nguyen, Duy-Bach AkiLotus Le, Stefan stefdasca Dascalescu, Quang-Minh MofK D. Nguyen and our dear Codeforces coordinator Dmitry cdkrot Sayutin.
Gladly (or sadly), no interactive problem tonight!
Also, the tribute should be given to everyone within the team — we all make it possible:
- Andrew GreenGrape Rayskiy for various problem suggestions and the infamous OMEGALULRIP influence. ;)
- Xuan-Tung neko_nyaaaaaaaaaaaaaaaaa Nguyen for testing the rounds and various suggestions in the core theme idea. Nya~.
Last but not least, I want to give a huge appreciation to MikeMirzayanov for the awesome Codeforces and Polygon platform, which makes this contest possible.
P/s: I will be at the Discord CP Community to discuss the problems after the coding phase. However, please follow the rules and don't discuss the problems during the contest by any means.
Wish everyone good luck and high rating!
P/s(2): Commies united!
P/s(3): A dear thank-you to Grigory vintage_Vlad_Makeev Reznikov for the last-minute complete testing as well! ;)
UPD1a: Another comrade, Quang-Minh MofK D. Nguyen joined the fun! Kudos for the problem suggestion! ;)
UPD1b: The problemset contains 6+1 problems ( 6 problems, one of them has 2 subtasks ).
UPD2: Score distribution: 500-1000-1500-2000-2000-(2250+750).
UPD3: Editorial will be available tomorrow. Sorry for the waiting, we have quite a lot of things to polish. ;)
UPD4: The contest is finished. I hope that you're satisfied. And here come our winners ;)
Official participants:
- hamzzq
- davidHernandes
- oiyoayao
- abandonedw1
- OnionGod
- IPL
- memset_inf
- dsgsjk
- FluffyT (the only official participants solved F1+F2, too bad she didn't solve E :<)
- _wxw_
Div.1 + Div.2 participants:
- dreamoon_love_AA (solved all problems!)
- pwild
- Sugar_fan
- hamzzq
- natsugiri
- kmjp
- davidHernandes
- Jeffrey
- betrue12
- KrK
$$$iS iT rAtEd?$$$
It obviously is. The only way AkiLotus and stefdasca can be orange in the blog post is if they participated in this round, got a high rank and this blog post is actually using colors from the future.
You know too much. We're going to subdue you.
Comrade Stefdasca share the points that you will atain when you do this round.
Good Luck Coders o_O
Ha ha ha Really funnny
I'm the same :v
true story
Ahh, abilis27 Are u god??
U knew it 11 hrs earlier.
Oh my, I laughed at it thinking such scenario would be too rough.
I was wrong. :P
Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).
What is this OMEGALULRIP btw? Some kind of insider joke or some old meme!
codeforces.com
A lot of rounds recently! That is awesome!
What's "the infamous OMEGALULRIP influence" ??
Not all grape is GreenGrape XD
Meow :3
Wait a second I didn't say anything about quarantining GreenGrape from pretests right? lenny eyes
Another round for Night Raiders?
upvote: funny and cool announcement downvote: messy announcement with many unnecessary details
I can see several rounds opened by you while I am waiting for my single proposal. Jealous! Hope I will open my round also.
Once the first one is accepted, proceeding with later proposals should be a cakewalk (provided the problems in the next proposals are well-prepared) and require less waiting time. ;)
Anyway, would be glad to join yours soon. ;)
Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).
There are some guys who use to devote all the comments without any reason, please don't do this. Happy Coding
Do not mind downvotes on your comment
Again you posted a week before the contest =) AkiLotus
Next time I might post it a month before the contest I suppose. ;) :thinking:
downvote if you get OMELGALULRIP reference upvote if you don't know what it is
Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).
I hope GreenGrape gave you only problems ideas not test cases ideas :V
How many points each question will be worth?
I'm a gay!
Well... Actually, front-end is OK
Do you know Who is BITI?
Hack time is during the contest?
How do sub-tasks work at codeforces?
Maybe different test have different score?
Last time they seperate the problem into to 2 problems and each has half of the score
There are tow different problems with the same quetions but different constraints!
Not always, https://codeforces.net/problemset/problem/1092/D2
Oh! I haven't ever seen this before! Sorry for that!
Thanks for the replies, but I guess it was irrelevant for me today.
What's with all these female anime character profile pictures?
Weebforces
Everyone wants to show off their waifu.
gg Everyone!
How does the subtask thing work? Does that mean that the problem will have partial scoring? I guess this will be the first time that a rated CF contest has partial scoring for problems?
It happened in some previous contests though, the latest iirc was about 2-3 months ago.
Someone will solve all the problems at 6:13. Says, the contest poster. -Illuminati
Yay! Another chance to change the rank! Maybe to expert xD
Well, seems like I'm working on it.
Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).
Site is working so slooow
it is always a good idea to use one of m codeforces sites during the contest http://m1.codeforces.com/enter http://m2.codeforces.com/enter http://m3.codeforces.com/enter
,
F1 and F2 differs in constraints of $$$n$$$.
Isn't the LCM problem harder for a Div2 C problem?
It was a math problem, not that hard, or not that easy. The number of submissions(1285) reflects the same, that it was not that hard. :)
Agreed.
It was for me bro...
Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).
Great round!
+balanced
What a shame...how to solve C? i have no idea about it at all..
https://www.quora.com/How-do-I-find-the-natural-number-X-that-minimizes-LCM-A+X-B+X
I spent almost all contest time on that problem and now see my error thanks to that link. I was keep using prime factors instead of divisors :P
I always get stuck at Maths problems . :(
Find the difference (b-a), and for every factor of (b-a), try to find the number(greater than a) which is the nearest to a and a multiple of the factor. Now that number — a will give you x, and you can solve it further. Constraints did help me think this way.
According to Euclidean algorithm, when a != b, "GCD(a + k, b + k) == GCD(b — a, a % (b — a) + k)" (when a < b). Then all we need to do is find all divisors of "b — a" (Traverse from 1 to sqrt(b — a) is enough), for each divisor d, let "d == a % (b — a) + k", so we can calculate k and corresponding LCM, then find the minimum. Exceptionally, consider the "a == b" case.
.
what was the logic in problem c??? anyone who got it accepted.
$$$lcm(a, b) -> min <=> gcd(a, b) -> max$$$
$$$gcd(a, b) = gcd(a - b, b)$$$ if $$$a > b$$$.
So $$$gcd(a + k, b + k) = gcd(a - b, b + k)$$$. That means that you can iterate over divisors of $$$a-b$$$. For each divisor $$$d$$$ you can find such $$$k$$$ as $$$g * ceil(b / g) - b$$$. And just print $$$k$$$ that gives minimum value of $$$lcm(a + k, b + k)$$$.
(I probably misunderstood the question, but) if we are to maximize gcd(a — b, b + k), then why do we need to iterate over divisors of a — b? Isn't it we just find k such that the gcd attains the max possible value, i.e. a — b?
There might exist a factor less than the maximum possible value for which the LCM is smaller.
Countertest: $$$a = 3, b = 1$$$.
$$$a - b = 2$$$. So $$$k$$$ must be 1 ($$$gcd(3 + 1, 1 + 1) = 2$$$). But real answer is zero.
if $$$k = 0$$$ $$$lcm(3 + 0, 1 + 0) = 3$$$.
if $$$k = 1$$$ $$$lcm(3 + 1, 1 + 1) = 4$$$.
I think I understand what's wrong with my logic...
The thing in my mind is LCM(a + k, b + k) = (a + k) x (b + k) / GCD(a + k, b + k). While my focus is on maximizing the denominator with respect to k, I overlooked the fact that k also impacts the numerator...
What a stupid mistake and flawed logic (sigh... spending like an hour debugging my logic...)
In the line : For each divisor d you can find such k as g∗ceil(b/g)−b ; what was 'g' here...?
What was the 5th test of D???
5 answer 84
$$$ans(4) = 27$$$
$$$ans(5) = 84$$$
$$$ans(6) = 270$$$
Maybe 5th test is neither of them but you can at least check.
Why was x from problem B 1e6? I have a greedy solution that works in O(steps) (in our case steps is 40). Is the official solution dp?
LOL, I overrated D, it shouldn't take so much of my energy like that, so not able to even read statement of E and F. Great round anyway.
I would like to ask if we could reduce problem E to a euler path problem like this one: SGU101.
I got AC on pretests with euler path. I think it's quite easy to prove that any solution gives euler path in a graph, and any euler path is a solution.
can you please explain your approach?
Let values $$$b_i$$$ and $$$c_i$$$ be vertices of the graph, and edges would be $$$(b_i, c_i)$$$. Then you just need to find euler path in this graph and it would give answer, or there is no answer if such path does not exist. And before all you need to check that $$$b_i \leq c_i$$$ for all i.
Sorry but I didn't understand why this works? Can you give me the intuition behind it?
Whole problem is to reorder pairs $$$(b_i, c_i)$$$ in such way that it would give you some array a. Pairs need to form a path because pairs $$$(min(a_i, a_{i+1}), max(a_i, a_{i+1}))$$$ and $$$(min(a_{i+1}, a_{i+2}), max(a_{i+1}, a_{i+2}))$$$ obviously share one element, which is $$$a_{i+1}$$$.
Oh, I forgot to tell that graph is undirected, it's really important here.
If i understood correctly then a particular vertex b[i] may appear twice in the resultant array. So, if we just add the edges between bi and ci then how can we differentiate between them? (like in sample case 3)
Just add multi-edges, algorithm for euler path works well with them
it worked! thanks!
I think yes, but the graph can have $$$O(n^2)$$$ edges
Could you elaborate on how you model the graph?
My approach is to use numbers appeared in b' and c' as vertices and add edges only between each pair of b and c. So if it is correct, the number of edges would be O(n) I guess?
I think he means that for each i, you will have two possibilities for two consecutive elements at some position in a, either b'[i],c'[i] or c'[i],b'[i] (given that c'[i] >= b'[i]). Let these 2 pairs be pi1 and pi2, you will add an edge from pix to pjx (i != j) if pix.second == pjx.first. This may result in n^2 edges.
Oh I see. Thanks :)
The solution to Problem C could be found on multiple Q/A forums. Aren't the setters supposed to make sure this doesn't happen?
The exact problem has been discussed here and here.
Thank you for the great round! I guess E is Eulerian path problem, but not enough time for coding:(
sorry for not being clear about codeforces rules, but is it reasonable to skip all the previous submits that had passed pretests and only accept the last submit?
Am I the only one who experienced problems with the website today?
Me too. Can't send D within last five minutes. But this is almost regular.)
I have recently started having trouble with loading website, not only during this contest
Me too :(
of course not ... specifically after every submission, the page needed to be refreshed for the verdict which then too was not loading
it looks like I should've used my googling skills to solve C instead of thinking
how to solve D?
Let's consider a rectangular grid with $$$n \times n$$$ cells. Denote the lower left vertex as $$$(0,0)$$$ and the opposite as $$$(n,n)$$$. For every correct bracket sequence, there is a path walking from $$$(0,0)$$$ to $$$(n,n)$$$, without crossing the diagonal( you can touch but cannot go to another side), which is related to Catalan number.
Denote the number on the vertex to be number of ways walking in this rule. The question ask for the largest set of edges such that there are no two edges with a common vertex. i.e. we can think as the sum of all number in the vertex such that no two vertex does not touch each other. The best way to take the set of vertex is taking $$$(x,y)$$$ with $$$x+y \mod 2=1$$$
(illustration of 4x4 grid, typo fixed)
Number at (5,4) should be 14, not 9
thanks!
D can be found on oeis (somewhat indirectly):
Just take the partial sums of https://oeis.org/A000957, that's your answer.
Oh,thanks!
Oh crap. Of course I verified that the $$$f(n)$$$ in this problem is not oeis-able, but I haven't guessed that the $$$f(n) - f(n - 1)$$$ may oeis.
What is the easiest way to to find the Euler Path of a graph? ( In code ). I got to this on problem E but I couldn't implement it in time.
Check this https://cp-algorithms.com/graph/euler_path.html For undirected graph to keep track of deleted edges, edges should be $$$(b_i, c_i, i)$$$ and $$$(c_i, b_i, i)$$$, so when you delete an edge you do something like $$$used[i] = 1$$$, then it would be easy to check for both $$$(b_i, c_i)$$$ and $$$(c_i, b_i)$$$ if it's deleted or not.
I think an easy way to solve this is using multiset to store the graph. Using multiset you are able to delete the edges without much effort. Here's my code: 53257834
Today, i found the codeforces site to be extremely laggy and massive loading time was there even to just open the submission portal.This is what ruined the contest for me today :( I even dare say that the loading time must have taken 25-30 mins for me today during the contest :( MikeMirzayanov and others please tell me if i am wrong :(
About problem D.
I think it wasn't catnip.
Any hint at problem F would be appreciated ^^
My solution for F1 was a $$$O(2^{m} nk^{2})$$$ dp.
Suppose the planets you've visited are $$$a_{1}, a_{2}, ..., a_{k}$$$ in order. If you add edge for every $$$i$$$ such that $$$a_{i} < a_{i + 1}$$$, then the visited path basically looks like a bunch of forward paths. Now it's not hard to construct those forward paths by dp. Notice that a planet $$$i$$$ can only be connected with $$$i-m, i-m+1, ..., i-1$$$ in a forward path. So you've to store a mask of size $$$2^{m}$$$ in your dp state to know which of the last $$$m$$$ planets are endpoints of some forward path. You also have to store number of planets you've chosen so far. But only constructing those forward paths is not enough, because there're multiple ways you can choose to merge them, so another thing you need to store in your state is number of forwards paths that can still be merged.
DP transitions are now not very difficult. In fact, the transition is a linear recurrence and the coefficients do not depend on current planet, so F2 can probably be solved via Berlekamp–Massey algorithm.
~160 tests for task with 7s TL.... Potentially ~18 minute for checking participant. Is it right?
In theory, possibly. However, many of those tests are quite small (in case some would fail at some random small tests).
Can anyone tell me why my solution for A failed for test case 11? https://codeforces.net/contest/1152/submission/53227715
I tried the testcase manually and it showed 3 whereas the output given here is 1. What am I missing here?
Ohh thanks a lot
Been scratching my head since over an hour
Silly of me to make that mistake
Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).
FluffyT is a girl.You may change he into she.
Hmm any proofs other than him/her being fluffy? :>
I can also prove that she is a girl and likes rabbits. :>
Oh, nice to know :>
Edited. Send her my apology. :>
She is my classmate.
Good
The best algorithm I have ever encountered. HATS OFF MAN!
because they use that logic for problem C, I do not understand, help me plis.
Let $$$a \le b$$$ and $$$d = b - a$$$ and $$$k$$$ is answer. Denote $$$x = a + k$$$, then $$$x + d = b$$$. So $$$lcm = x * (x + d) / gcd(x, x + d)$$$ . It's obvious that $$$d$$$ is multiple $$$gcd(x, x + d)$$$ and $$$x$$$ is the least multiple $$$gcd(x, x + d)$$$ (to reach the minimum). So we need to check all divisors of $$$d$$$ and find for each of them minimum $$$x$$$ which is greater then $$$a$$$ and multiple this divisor, calculate $$$lcm$$$ and choose $$$x$$$ at which the minimum $$$lcm$$$ is reached.
Stupid mistake costed me B lmao :/
How to Solve B ? I can't think of any other way except brute force!
Break down the input number into its binary form. It will take at most 20 bits. Now do as the problem says. Our target is to make the binary representation of input number to contain all 1s, so will try to make every 0 convert to 1 in our binary representation. For every 0 bit in the binary representation, store it's index in the answer(vector in CPP) and xor all the following bits(including this one). Then in the next operation add one to its binary representation. You will also have to keep an optional check to see at what which step the binary representation will contain all ones. Since for each bit we will use at most 2 operations, we will use at most 40 operations. I don't think it's the most optimal(or even optimal) strategy but it appeared pretty intuitive to me(though i got a couple of wrong answers) as we can represent number less than 1000000 in 20 bits and we are allowed 40 questions(2 for each).
Please tell me if something wasn't clear or if something was wrong !
Some greedy stuff.
First of all when it comes to $$$XOR$$$ or any bitwise calculation, first thing I consider is to do binary stuff. Change number to binary form then do some mathematical magic, you know...
So when I look into the problem $$$A$$$, first observation is if you $$$XOR$$$ a number with a random $$$2^n-1$$$, actually you reverse $$$n$$$ consecutive bits of this number from the last bit. Then I tried to reverse the problem, like you already get the last result (some $$$2^n-1$$$), then you minus 1, and take a random $$$XOR$$$ with $$$2^k-1$$$ ($$$k$$$ don't need to be smaller than $$$n$$$). Then I realize this problem is all about processing consecutive bits $$$1$$$ or $$$0$$$.
Change the input form (number $$$x$$$) into binary bits. Then you repeat processing $$$x$$$ from the last bit to the first bit like this until bits of $$$x$$$ are all $$$1$$$:
Case 1: Your number $$$x$$$ is like this: ......1110000000.000 (0 consecutive bits $$$1$$$ from the last bit) or .......11100..0011111.111 ($$$k$$$ consecutive bits $$$1$$$ from the last bit and $$$k>1$$$). In general it's $$$k$$$ consecutive bits $$$1$$$ from the last bit with $$$k\neq 1$$$. Then you just do $$$x=x\oplus 2^k-1$$$ and $$$x=x+1$$$.
Case 2: There is just 1 consecutive bit $$$1$$$ from the last bit. Let $$$k$$$ be the number of consecutive bits $$$0$$$ from the bit stands in the left of the last bit (pretty sure it's a bit $$$0$$$, cause we just have 1 consecutive bit $$$1$$$). Then you just do $$$x=x\oplus 2^{k+1}-1$$$ and $$$x=x+1$$$.
Actually I just tried some drafts before trying my greedy guess. First I minus 1 to $$$2^n-1$$$, which you get a bit array like 111111111...110 as the result. Then you $$$XOR$$$ with a random $$$2^k-1$$$ which you get a bit array like 1111..1100000..001 as the result. Then you minus 1 again and get 1111..1100000..000 then $$$XOR$$$ again and get 1111..11000..00111..111. Then I realize every step you need to deal with consecutive bit $$$1$$$ or consecutive bit $$$0$$$ plus one bit $$$1$$$.
Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).
My submission for problem D is actualy wrong since in my solve function what I am returning is basically the maximum length after taking modulo which will result wrong comparisions. For the 1st call it may return 5 and for second call it may return 15 but since I am taking modulo before returning the 1st value could be 10^9+7+5 but I will not consider it as maximum value. Can someone tell me if there is a reson or test cases are weak?
No effing way! I did the exact same thing. But I didn't submit my solution because it was obviously wrong (in fact I submitted it, but with some extra prints and I didn't bother to remove them). What my plan was: translate the code to python (for big integer arithmetic) and pre-compute (and hardcode) all solutions up to 1000. But I was 1 or 2 minutes too slow.
But now that I read your comment, I submitted my original (supposedly wrong) solution and it got accepted! I also tested it on all 1000 possible cases and it somehow gets the right answer on every one. I guess sometimes wrong solutions just give right answers ¯\_(ツ)_/¯. I just wish I'd known that during the contest.
I know it's strange right?! Could there be logical explanation or it's just a fluke that it passes all test cases?
I guess the intuition is that in most cases you're taking the max of two values that differ by very little (since the left and right tries are for the most part very similar). The less the values differ by, the smaller the chance to get it wrong.
For example, say you were taking the max of $$$a$$$ and $$$b$$$ and you know they differ by exactly 1 (suppose $$$b$$$ is greater). Then, the only case in which $$$max(a, b) \; mod \; M \not= max(a \; mod \; M, b \; mod \; M)$$$ is exactly when $$$b \equiv -1 (mod \; M)$$$, which occurs with a probability of $$$\frac{1}{M}$$$. For our problem, that's 1 in a billion times.
Obviously, in our problem values might differ by more than 1, but still. A similar thought process can be applied as long as the difference is small. And even if you get it wrong once, there's a chance that it won't actually affect your final result.
In other words... it's obviously a "fluke". But it's a rather "probable" fluke when you think about it.
Thanks a lot makes more sense now.
Probably the function is specific enough for those incorrect ideas to work too and it is probably impossible to make a test against it since the input is just a small number.
Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).
How can I develop my problem solving skills? What do I do to develop my skills in algorithms and data structure?
In short, you need to learn more.
Take a shot at "Competitive Programming 3" of Steve Halim. I highly recommended it as the book has almost latest algorithms and data structures, with exercises to practice what you learn. Although you should support the author by buying the original book, you can find its pdf in the web.
Try to learn from the experience ones. They have knowledge about the competitive programming scene, and should give you best advice about how, what to learn, what mistakes to avoid..
I really find how bad I'm at math,in order that I only solve 2 problems (T2 cost me 1 hour and 58 minutes)
nice round thanx
A good and interesting problem set after a long time. Hope to see more like this.
I think that the checker for the task D might be incorrect. I have sent the solution with dp[i][j][0/1] — max answer for the tree where the root contains i opening brackets has balance j and the root is unused/used in the answer. It is easy to calculate and the answer is max(dp[0][0][0], dp[0][0][1]). However, we calculate the values using modul so the maximum operation is invalid. But my submission(53297703) receives OK.
It looks like in all cases either the second value you're taking the maximum of is 1 larger than the first value(meaning a very tiny chance to fail) or the values are the same.
good