### Akikaze's blog

By Akikaze, history, 5 weeks ago, ,

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 Akikaze Le, Stefan stefdasca Dascalescu, Quang-Minh MofK D. Nguyen and our dear Codeforces coordinator Dmitry _kun_ Sayutin.

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_nyaa 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 gritukan 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:

1. hamzzq
2. davidHernandes
3. oiyoayao
4. It5t
5. OnionGod
6. IPL
7. memset_inf
8. dsgsjk
9. FluffyT (the only official participants solved F1+F2, too bad she didn't solve E :<)
10. _wxw_

Div.1 + Div.2 participants:

1. dreamoon_love_AA (solved all problems!)
2. pwild
3. Heltion
4. hamzzq
5. natsugiri
6. kmjp
7. davidHernandes
8. JeffreyHo
9. betrue12
10. KrK

•
• +436
•

 » 4 weeks ago, # |   +42 $iS iT rAtEd?$
•  » » 4 weeks ago, # ^ |   +87 It obviously is. The only way Akikaze 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.
•  » » » 4 weeks ago, # ^ |   +61 You know too much. We're going to subdue you.
•  » » » 4 weeks ago, # ^ |   +10 Comrade Stefdasca share the points that you will atain when you do this round.
•  » » 4 weeks ago, # ^ |   -25 Good Luck Coders o_O
•  » » 4 weeks ago, # ^ | ← Rev. 4 →   +104
•  » » » 4 weeks ago, # ^ |   -11 Ha ha ha Really funnny
•  » » » 4 weeks ago, # ^ |   +1 I'm the same :v
•  » » » 4 weeks ago, # ^ |   0 true story
•  » » » 4 weeks ago, # ^ |   +15 Ahh, AbPlusil Are u god??U knew it 11 hrs earlier.
•  » » » 4 weeks ago, # ^ |   0 too
•  » » » 3 weeks ago, # ^ |   0 Oh my, I laughed at it thinking such scenario would be too rough.I was wrong. :P
 » 4 weeks ago, # |   +5 Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).
•  » » 4 weeks ago, # ^ |   +29 What is this OMEGALULRIP btw? Some kind of insider joke or some old meme!
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   -39 codeforces.com
 » 4 weeks ago, # |   +4 A lot of rounds recently! That is awesome!
 » 4 weeks ago, # |   +9 What's "the infamous OMEGALULRIP influence" ??
 » 4 weeks ago, # |   +8 Not all grape is GreenGrape XD
 » 4 weeks ago, # | ← Rev. 2 →   0 Meow :3
 » 4 weeks ago, # |   +12 Wait a second I didn't say anything about quarantining GreenGrape from pretests right? lenny eyes
•  » » 4 weeks ago, # ^ |   +15 Another round for Night Raiders?
 » 4 weeks ago, # |   +2 upvote: funny and cool announcement downvote: messy announcement with many unnecessary details
 » 4 weeks ago, # |   +2 I can see several rounds opened by you while I am waiting for my single proposal. Jealous! Hope I will open my round also.
•  » » 4 weeks ago, # ^ |   0 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. ;)
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).
 » 4 weeks ago, # |   -78 There are some guys who use to devote all the comments without any reason, please don't do this. Happy Coding
•  » » 4 weeks ago, # ^ |   0 Do not mind downvotes on your comment
 » 4 weeks ago, # |   +4 Again you posted a week before the contest =) Akikaze
•  » » 4 weeks ago, # ^ |   +12 Next time I might post it a month before the contest I suppose. ;) :thinking:
 » 4 weeks ago, # |   +17 downvote if you get OMELGALULRIP reference upvote if you don't know what it is
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).
 » 4 weeks ago, # |   -14 I_AM_BAD and I know it.
 » 4 weeks ago, # |   +16 I hope GreenGrape gave you only problems ideas not test cases ideas :V
 » 4 weeks ago, # |   0 How many points each question will be worth?
 » 4 weeks ago, # |   -17 I'm a gay!
•  » » 4 weeks ago, # ^ |   0 Who cares...
•  » » 4 weeks ago, # ^ |   +24 Well... Actually, front-end is OK
•  » » 4 weeks ago, # ^ |   0 Do you know Who is BITI?
 » 4 weeks ago, # | ← Rev. 3 →   0 GOOD LUCK AND THE BEST STANDINGS!!!
 » 4 weeks ago, # |   +6 Hack time is during the contest?
 » 4 weeks ago, # |   +4 How do sub-tasks work at codeforces?
•  » » 4 weeks ago, # ^ |   0 Maybe different test have different score?
•  » » 4 weeks ago, # ^ |   0 Last time they seperate the problem into to 2 problems and each has half of the score
•  » » 4 weeks ago, # ^ |   +2 There are tow different problems with the same quetions but different constraints!
•  » » » 4 weeks ago, # ^ |   +1
•  » » » » 4 weeks ago, # ^ |   0 Oh! I haven't ever seen this before! Sorry for that!
•  » » 4 weeks ago, # ^ |   +3 Thanks for the replies, but I guess it was irrelevant for me today.
 » 4 weeks ago, # |   +44 What's with all these female anime character profile pictures?
•  » » 4 weeks ago, # ^ |   +39 Weebforces
•  » » 4 weeks ago, # ^ |   +18 Everyone wants to show off their waifu.
 » 4 weeks ago, # |   0 gg Everyone!
 » 4 weeks ago, # |   0 Good luck to everyone!
 » 4 weeks ago, # |   0 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?
•  » » 4 weeks ago, # ^ |   0 It happened in some previous contests though, the latest iirc was about 2-3 months ago.
 » 4 weeks ago, # |   0 Someone will solve all the problems at 6:13. Says, the contest poster. -Illuminati
 » 4 weeks ago, # | ← Rev. 2 →   +4 Yay! Another chance to change the rank! Maybe to expert xDWell, seems like I'm working on it.
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).
 » 4 weeks ago, # |   +43 Site is working so slooow
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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
 » 4 weeks ago, # | ← Rev. 2 →   -22 ,
•  » » 4 weeks ago, # ^ |   0 F1 and F2 differs in constraints of $n$.
 » 4 weeks ago, # |   0 Isn't the LCM problem harder for a Div2 C problem?
•  » » 4 weeks ago, # ^ |   +1 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. :)
•  » » » 4 weeks ago, # ^ |   0 Agreed.
•  » » » 4 weeks ago, # ^ |   0 It was for me bro...
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).
 » 4 weeks ago, # |   +8 Great round!
•  » » 4 weeks ago, # ^ |   +2 +balanced
 » 4 weeks ago, # |   +5 What a shame...how to solve C? i have no idea about it at all..
•  » » 4 weeks ago, # ^ |   +20
•  » » » 4 weeks ago, # ^ |   0 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
•  » » » » 4 weeks ago, # ^ |   +1 I always get stuck at Maths problems . :(
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 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.
•  » » 4 weeks ago, # ^ |   0 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.
•  » » » 4 weeks ago, # ^ |   0 This kind of seems like a task that you would have to have done in the past to understand it, or you must have known this type of mathematics to get a solution.Not having done this type of task ever before, I would have never in my lifetime guessed this was the solution..
 » 4 weeks ago, # | ← Rev. 3 →   +3 .
 » 4 weeks ago, # |   0 what was the logic in problem c??? anyone who got it accepted.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +13 $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). •  » » » 4 weeks ago, # ^ | 0 (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? •  » » » » 4 weeks ago, # ^ | 0 There might exist a factor less than the maximum possible value for which the LCM is smaller. •  » » » » 4 weeks ago, # ^ | ← Rev. 2 → 0 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. •  » » » » » 4 weeks ago, # ^ | +5 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...) •  » » » 4 weeks ago, # ^ | 0 I found that there are some solutions out there which iterate the divisors of a-b without sorting them (e.g. when divisor is 60, then 30 is iterated before 3 in such implementation), and it makes me wonder whether some of them would give the same lcm (and would not print the smallest valid k as a result). •  » » » 4 weeks ago, # ^ | 0 In the line : For each divisor d you can find such k as g∗ceil(b/g)−b ; what was 'g' here...? •  » » » » 3 weeks ago, # ^ | 0 g is the divisors of (b-a) •  » » » 4 weeks ago, # ^ | 0 I understand till here That means that you can iterate over divisors of a−b How did you get this formula g∗ceil(b/g)−b and what is g in it . and should the divisor d should be a multiple of b+k ? •  » » » 4 weeks ago, # ^ | 0 thanks u; » 4 weeks ago, # | Rev. 2 -33 ## What was the 5th test of D??? •  » » 4 weeks ago, # ^ | +3 5 answer 84 •  » » 4 weeks ago, # ^ | ← Rev. 2 → +3 ans(4) = 27$$ans(5) = 84$$ans(6) = 270$ Maybe 5th test is neither of them but you can at least check.
 » 4 weeks ago, # |   0 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?
 » 4 weeks ago, # |   +1 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.
 » 4 weeks ago, # |   0 how to solve F1 ?
 » 4 weeks ago, # |   0 I would like to ask if we could reduce problem E to a euler path problem like this one: SGU101.
•  » » 4 weeks ago, # ^ |   0 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.
•  » » » 4 weeks ago, # ^ |   0 can you please explain your approach?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 4 weeks ago, # ^ |   0 Sorry but I didn't understand why this works? Can you give me the intuition behind it?
•  » » » » » » 4 weeks ago, # ^ |   0 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}$.
•  » » » » » » 4 weeks ago, # ^ |   0 Oh, I forgot to tell that graph is undirected, it's really important here.
•  » » » » » » » 4 weeks ago, # ^ |   0 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)
•  » » » » » » » » 4 weeks ago, # ^ |   +6 Just add multi-edges, algorithm for euler path works well with them
•  » » » » » » » » » 4 weeks ago, # ^ |   0 it worked! thanks!
•  » » 4 weeks ago, # ^ |   0 I think yes, but the graph can have $O(n^2)$ edges
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   +8 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.
•  » » » » » 4 weeks ago, # ^ |   +5 Oh I see. Thanks :)
 » 4 weeks ago, # |   +26 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.
 » 4 weeks ago, # | ← Rev. 3 →   +5 Thank you for the great round! I guess E is Eulerian path problem, but not enough time for coding:(
 » 4 weeks ago, # |   0 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?
 » 4 weeks ago, # |   +17 Am I the only one who experienced problems with the website today?
•  » » 4 weeks ago, # ^ |   0 Me too. Can't send D within last five minutes. But this is almost regular.)
•  » » 4 weeks ago, # ^ |   0 even i faced the same ..
•  » » 4 weeks ago, # ^ |   +6 I have recently started having trouble with loading website, not only during this contest
•  » » 4 weeks ago, # ^ |   0 Me too :(
•  » » 4 weeks ago, # ^ |   +6 of course not ... specifically after every submission, the page needed to be refreshed for the verdict which then too was not loading
 » 4 weeks ago, # | ← Rev. 3 →   +10 it looks like I should've used my googling skills to solve C instead of thinking
 » 4 weeks ago, # |   +5 how to solve D?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +21 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)
•  » » » 4 weeks ago, # ^ |   0 Number at (5,4) should be 14, not 9
•  » » » 4 weeks ago, # ^ |   0 thanks!
 » 4 weeks ago, # |   +15 D can be found on oeis (somewhat indirectly):Just take the partial sums of https://oeis.org/A000957, that's your answer.
•  » » 4 weeks ago, # ^ |   0 Oh，thanks!
•  » » 4 weeks ago, # ^ |   +50 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.
 » 4 weeks ago, # |   +8 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.
•  » » 4 weeks ago, # ^ |   +7 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.
•  » » 4 weeks ago, # ^ | ← Rev. 6 →   0 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
 » 4 weeks ago, # |   +11 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 :(
 » 4 weeks ago, # |   0 About problem D. SpoilerI think it wasn't catnip.
 » 4 weeks ago, # |   0 Any hint at problem F would be appreciated ^^
•  » » 4 weeks ago, # ^ |   +5 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.
 » 4 weeks ago, # |   0 ~160 tests for task with 7s TL.... Potentially ~18 minute for checking participant. Is it right?
•  » » 4 weeks ago, # ^ |   +6 In theory, possibly. However, many of those tests are quite small (in case some would fail at some random small tests).
 » 4 weeks ago, # | ← Rev. 2 →   0 Can anyone tell me why my solution for A failed for test case 11? https://codeforces.com/contest/1152/submission/53227715I tried the testcase manually and it showed 3 whereas the output given here is 1. What am I missing here?
•  » » 4 weeks ago, # ^ |   +1 ll a[n],b[n]; 
•  » » » 4 weeks ago, # ^ |   0 Ohh thanks a lot Been scratching my head since over an hourSilly of me to make that mistake
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).
•  » » 3 weeks ago, # ^ |   +12 FluffyT is a girl.You may change he into she.
•  » » » 3 weeks ago, # ^ |   0 Hmm any proofs other than him/her being fluffy? :>
•  » » » » 3 weeks ago, # ^ |   0 I can also prove that she is a girl and likes rabbits. :>
•  » » » » » 3 weeks ago, # ^ |   0 Oh, nice to know :>Edited. Send her my apology. :>
•  » » » » 3 weeks ago, # ^ |   +3 She is my classmate.
 » 4 weeks ago, # |   -37 The contest is very interesting. I think this is best solution for Problem A https://codeforces.com/contest/1152/submission/53234710Thank the author very much.
•  » » 4 weeks ago, # ^ |   +10 The best algorithm I have ever encountered. HATS OFF MAN!
 » 4 weeks ago, # |   0 because they use that logic for problem C, I do not understand, help me plis.
•  » » 4 weeks ago, # ^ |   +4 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.
 » 4 weeks ago, # |   0 Stupid mistake costed me B lmao :/
 » 4 weeks ago, # |   0 How to Solve B ? I can't think of any other way except brute force!
•  » » 4 weeks ago, # ^ |   0 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 !
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   0 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$.
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 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?
•  » » 4 weeks ago, # ^ | ← Rev. 4 →   +3 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.
•  » » » 4 weeks ago, # ^ |   0 I know it's strange right?! Could there be logical explanation or it's just a fluke that it passes all test cases?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +6 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.
•  » » » » » 4 weeks ago, # ^ |   0 Thanks a lot makes more sense now.
•  » » 3 weeks ago, # ^ |   0 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.
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 How can I develop my problem solving skills? What do I do to develop my skills in algorithms and data structure?
•  » » 3 weeks ago, # ^ |   0 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..
 » 4 weeks ago, # |   0 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)
 » 3 weeks ago, # |   0 nice round thanx
 » 3 weeks ago, # |   0 A good and interesting problem set after a long time. Hope to see more like this.
 » 3 weeks ago, # | ← Rev. 3 →   0 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.
•  » » 3 weeks ago, # ^ |   0 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.
 » 3 weeks ago, # |   0 good