I'm so depressed that all of my hard work and dedication on preparing problems has failed as I couldn't achieve the first comment :(

On behalf of the contest setter's committee, I would like to congrate you for achieving the position of first commenter. Here's a golden titop prepared by the committee for all your dedication and hard work:

I think another problem with name SifidLee is coming XD isn't it?

3, info will be updated soon

Orz

That problem was prepared and authored by Mohammad.H915 ! not AliShahali1382

No light-hearted meme this time :(

CF Round 684 still gives me PTSD...

This is an exciting competition :))

Hope it meets your expectations brother

Why is scoring distribution so significant before the round? I don't quite understand, can you explain?

We're too busy :(

everyone who didn't pass A probably missed this case n==1 && m == 1

I think you should definitely buy this

Noob question: I've searched for these and couldn't find answers: Within the post above, it says "The rounds are open and rated for everybody". However, within the title, it doesn't say it is rated. On my graph, this competition comes under unrated. I'm quite confused. Is there a way to tell which competitions are rated or not, that I'm not aware of?

My solution is based on binary search on the answer. The boundaries for BS are l = 1 (you can always call 1 friend), and r = n. Now we are interested in whether can we call m = (l+r)/2 friends to the party? Let's iterative from first to the last friend and keep count of the number of the friends we have already invited (this will be cnt).

First of all — all friends to the left of the i-th friend are poorer, and all friends to the right are richer. If i-th friend satisfies these requirements we will call him, and update cnt = cnt+1:

1) a[i] >= m-cnt-1 //number of friends who will be richer than i-th is m-cnt-1 (since we are trying to call m friends with cnt already called + himself, that leaves us with m-cnt-1 friends to the right)

2) b[i] >= cnt //number of friend who will be poorer than i-th is cnt, since we called already cnt of them and all of them are to the left of the array

If in the end cnt >= m, then it is possible to call m friends, otherwise it is not. According to this we continue with our binary search.

Shitttt!! Got the blunder upon seeing others' code T-T

I feel like its really easy to go down the wrong route on D after making observations on the first sample for $$$\equiv 0 (\text{mod } 4)$$$ and $$$\equiv 2 (\text{mod } 4)$$$ part, but if you realize (or guess) it generally applies to $$$\equiv 0 (\text{mod } 2^x)$$$ and $$$\equiv 2^{x - 1} (\text{mod } 2^x)$$$ then its fairly easy to arrive at the solution.

Unfortunately took me wasting 1 hour hard coding a special case for pairs of $$$\equiv 0 (\text{mod } 4)$$$ and still overcount sample 2 to think about it properly and realize it.

It took me 1 hour to solve D and only 15 min to solve E. I thought there was a better solution but it turned out people did the same. Am I incredibly dumb or how did a lot of people come up with a not-so-trivial idea that fast?

binary search

Count of all non-empty subsequences where there is at least one odd number, or the count of even numbers with the least LSB is even.

Basically the idea in D is consider a number b then sum of all possible subsequences of b consecutive integers would be of the form b/2+rb when b is even, where r varies from -infinity to +infinity and when b is odd then it would be 0+rb here also r varies from -infinity to +infinity so the final conclusion comes that those subsets would be good where the m=(summation of even nos.)/2 is divisible the GCD of the whole subset. Here we should not bother about the odd factor of GCD as the m would always be divisible by the odd factor of GCD. Main concern is the power of 2 .Now by slight observation you could on just need to not count those subsets ,consider the even factor of GCD to be 2^i where i>=1 then the no of occurrences of no divisible by 2^i but not divisible by 2^(i+1) has occurred odd no. of times .Now let the total count of these subsets be m then the final answer would be 2^n-1-m

Binary Search on answer

Hint 1: 0 <= ans <= 2

Hint 2: m == 1 && n == 1 => 0

You have an $$$m\times n$$$ grid; you know one cell in this grid is chosen, for example $$$(x, y)$$$; you can choose $$$k$$$ cells from this grid. For each of these cells you choose, say $$$(x_i, y_i)$$$, you will be given the Manhattan distance from $$$(x_i, y_i)$$$ to $$$(x, y)$$$; then you are asked to determine $$$(x, y)$$$; now, the question is asking for the minimum number of cells you need to choose, which is $$$\text{min}(k)$$$, so that you can always find $$$(x, y)$$$ regardless of where it is in the grid.

https://codeforces.com/contest/1582/problem/C

Me haha, spent half an hour on trying to make DP work but failed.

+1. What I think is the worst is that the statement does not mention about the range of $$$k$$$, so it is incomplete (if strictly speaking). Such a "dumb" with an incomplete statement is... not good.

Newbies smiling in the corner.

+1. I think that not including this case in samples was an absolute shame. Problems were good but this issue alone is sufficient to make me downvote the round.

I'm generally okay if the corner case involves some thinking. This one is, on the other hand, just boring and annoying.

Let's read the statement again. The author intentionally left out $$$k \geq 0$$$, which made the definition of giving $$$0$$$ cells to the computer and receiving $$$0$$$ numbers extremely unnatural. Do we even receive if we give nothing? If you hate contestants that much, please don't set the first problem.

We can just greedy, consider a[i] is the smallest number in the array. We add the largest number a[n-1] to the set, then the next element is the largest that not bigger than a[k]=(a[n-1]+a[i])/2. Then the third should be the largest that not bigger than (a[k]+a[i])/2. My submission right after the contest :( https://codeforces.com/contest/1610/submission/136680210

Binary search https://codeforces.com/contest/1610/submission/136670710

Binary search on the range of answer

monotonicity: if we can invite some k friends, then we can invite some k-1 friends. we want to find the smallest x s.t. we can't invite x friends, then the answer will be x-1.

the greedy strategy to check a x: if we can invite some x friends, and say the first (the poorest one among all invited friends) friend's index is $$$f$$$, then both $$$a_f \geq x-1$$$ and $$$b_f \geq 0$$$ must be satisfied. similarly, for the second invited friend whose index is $$$s$$$, $$$a_s \geq x-2$$$ and $$$b_s \geq 1$$$ must hold, ... and so on. so for a given x we can loop through all friends (from the poorest to the richest) and keep track of the number of current invited friends, then check whether we can indeed invite x (or more) friends in the end.

A vertex can be an Oddysey vertex only if the weights of its incident edges have an odd sum. It turns out that it is always possible to make every such vertex an Oddysey vertex.

From well-known Euler path stuff, it is always possible to partition the edges of any finite graph with exactly $$$k$$$ odd-degree vertices into $$$k/2$$$ paths and some number of cycles, such that the path endpoints are exactly the $$$k$$$ odd-degree vertices. Do this for the subgraph consisting of weight-1 edges and for the subgraph consisting of weight-2 edges. Then we can direct the cycles arbitrarily and just need to direct the paths so that every vertex which is an endpoint of a path in both subgraphs has one path coming in and one going out. (But that can be done by the same routine!)

no need for mention

i was confused why you are being so mean, until i saw the spoiler...

I'm a stupid chicken that floats on water. Can confirm that I can see that it will TLE

MikeMirzayanov hey man! can you fix this.

Here's my working submission: 136686415. The mistake is that in Java comparing Integers using == is unreliable. Better to compare integers using .equals().

If there is anything unfair about it it is the fact that your friends were given a reply. Obviously it is part of the problem to understand what the possible answers are.

For convenience only. Imagine you have some condition cond which is true for all x <= b and false for all x > b (just like in task C). Now you want to find the smallest integer number x for which cond(x) == false (it is b + 1 as you can see). Typically your code will look something like the following:

while (low < high) {
  int mid = (low + high) >> 1;
  if (cond(mid)) {
    low = mid + 1;
  } else {
    high = mid;
  }
}
assert(low == high);
assert(low == b + 1);

Imagine now, that the task has changed and now you wanna find the greatest number x for which cond(x) == true. Of course you can use the same code as above, but sometimes you will have to write additional conditional expressions for border cases. However in some cases we can use another approach without any additional code:

while (low < high) {
  int mid = (low + high + 1) >> 1;
  if (cond(mid)) {
    low = mid;
  } else {
    high = mid - 1;
  }
}
assert(low == high);
assert(low == b);

In the second code example we cannot use int mid = (low + high) >> 1;, because high may be invalidated in case high = low + 1 before last iteration. That's why it is necessary to add one in the second approach.

Good to see someone found it :)

[edit:] guess who. Hind: Someone who doesn't have Lee in their username and they are not from China.

The problem is it's not guarantied that the t-shirt will actually reach you in finite time. So if you buy, then they have to fix it I think, hard to fix...

Your code should not pass because it's $$$O(n^2)$$$.

Actually its the first time I appreciate living in Iran...