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.

Good Luck Coders o_O

What is this OMEGALULRIP btw? Some kind of insider joke or some old meme!

Another round for Night Raiders?

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. ;)

Do not mind downvotes on your comment

Next time I might post it a month before the contest I suppose. ;) :thinking:

Well... Actually, front-end is OK

Do you know Who is BITI?

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!

Thanks for the replies, but I guess it was irrelevant for me today.

Weebforces

Everyone wants to show off their waifu.

It happened in some previous contests though, the latest iirc was about 2-3 months ago.

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$$$.

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. :)

+balanced

https://www.quora.com/How-do-I-find-the-natural-number-X-that-minimizes-LCM-A+X-B+X

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.

$$$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)$$$.

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.

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.

I think yes, but the graph can have $$$O(n^2)$$$ edges

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

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)

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.

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

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.

In theory, possibly. However, many of those tests are quite small (in case some would fail at some random small tests).

ll a[n],b[n];

FluffyT is a girl.You may change he into she.

The best algorithm I have ever encountered. HATS OFF MAN!

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.

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$$$.

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.

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.

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..

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.