If you solve GK in 2h30min you still have 5min to rest before this contest.

Score Distribution?

Gotta emphasize the message again.

completely failed after hacking myself(C)

It isn't hard to choose, just do the global round and forget about Leetcode.

It's simple, Codeforces > Leetcode

Sure

My dear friend, how do you want me to answer you. . .

just enjoy and solve problems, do not thinking about too much on rating changes, i believe u will have a better enjoyment ^-^

Me too, do you miss her?

Thanks for your support! o(*^w^*)o

no one wrote a comment

yeah because they wrote a full-blown blog

your algorithm will take 10^6 queries, and there are only 25 queries allowed. So you need to learn binary search https://codeforces.com/edu/course/2/lesson/6/1 , or from any other website which you prefer.

div-1 + div-2

https://postimg.cc/xJQHJC6s/4c459b91 really thanks alot my day was ruined i was excited to take part in this contest ( i even think i have registered earlier but maybe i am not remember) ps : its strange now i can register thnx

I would say the first 3 problems could all potentially be solved by someone who doesn't have a lot of experience with cp, but "beginner" includes a wide range of very different people.

Anyways, problems don't hurt, just go ahead and face them.. If you try and find them to be too tough for your level of experience just move on and go back to them another day or perhaps read the editorial once it's available.

.

Well, sorting the paths is easy. The real issue in that approach is 1) the best possible path relies on which paths can be used, requiring 2^|# leaves| states, and 2) it is not clear to me that greedily choosing the best possible path is optimal.

Let assume dp(u, k) return best result at u with k and k + 1 paths. Then for each node, we consider x = (k % num_child) best child. And the next best child is the answer for k + 1.176362632

You only will use a child maximum once, so you only push to the parent the best child you didn't used.

aabra ka dabra

It's essentially a special case of IMO2012 problem 3, except that this problem has an upper bound on the number of questions. But knowing this didn't help me anything, as in the IMO problem you just have to find a solution for the generalization to only one truthful answer in (k+1) questions (and in the end you can query 2^k + 1 numbers), but then your (mathematical) solution doesn't focus on minimizing the number of questions.

The mistake in your code is that the random numbers that it uses are of poor quality. Specifically, the lowest bit of the numbers returned by rand() has a low period, and adding the previous number and taking the result modulo N (when N is even) doesn't change that. In fact, it is not difficult to make a single test that will break any periodic RNG with a period less than 300000.

In 176407464, I modified your code to replace rand with mt19937, and it passed.

The limit is a little smaller in E2.

For E1, eliminating 1/4 for every 2 queries is fine. I used two intersecting subsets.

yes, wasted 2 hours 5 minutes + 100 elo on an unsolvable task. i and 1 look too similar.

lol I also wasted my 30 mins with this same mistake.

Wait this was me too, spent almost 2 hours on it ...

Bruuh

I used multiset, but with a memorization (I used vector<map<int, int64_t>> to record).

you can calculate Try(child, k) and Try(child, k+1) at one. This is my submission: 176362632

My idea was that we prepare two sets, $$$J$$$ and $$$T$$$ (for joking and truth). The idea is that if the latest query was honest, then the target is in $$$T$$$; otherwise, the target is in $$$J$$$. We can initialize them by querying half of the search space, where the half that's consistent with the answer goes to $$$T$$$ and the other half goes to $$$J$$$.

For each query afterwards, we can split $$$J$$$ into two halves: $$$J_1$$$ and $$$J_2$$$, and also split $$$T$$$ into two halves: $$$T_1$$$ and $$$T_2$$$. Then we query $$$J_1 \cup T_1$$$.

• If YES: Then $$$J' = T_2$$$ and $$$T' = J_1 \cup T_1$$$. We eliminate $$$J_2$$$ since consecutive answers cannot both be jokes.
• If NO: Then $$$J' = T_1$$$ and $$$T' = J_2 \cup T_2$$$. We eliminate $$$J_1$$$ since consecutive answers cannot both be jokes.

Let $$$J'$$$ and $$$T'$$$ be the new $$$J$$$ and $$$T$$$, and repeat. This way, we reduce the search space ($$$J$$$ and $$$T$$$ combined) by 75% in each query.

EDIT: Upon testing, I realized this doesn't work, since only half of $$$J$$$ is removed this way. The sizes of $$$J'$$$ and $$$T'$$$ are not necessarily the same, so half of $$$J_1$$$ is not necessarily 25% of $$$J \cup T$$$.

Divide number set $$$S$$$ into $$$a, b, c,$$$ and $$$d$$$,then query1:$$$a∪b$$$,query2:$$$b∪c$$$. Trust the results of two queries,we get a new number set $$$S'=a∪b∪c/a∪b∪d/...$$$(size of $$$3/4|S|$$$).

Take a look at Ticket 16294 from CF Stress for a counter example.

+1

Why?

Take a look at Ticket 16296 from CF Stress for a counter example.

It's not about garbage pretests but strong programming debug testing skills IMO

Maybe because I am not good at math and interactive.

Each operation on index i only affects the relation between i and i+1, therefore each operation should be dedicated to some consecutive pair of items in which the first one is bigger than the second. Let's create a differences array in which we will store a[i] - a[i + 1] for each 0 <= i < n - 1 that satisfies a[i] > a[i + 1]. Sort this array in an ascending order, and these are your "missions". Now obviously we rather use the earlier operations to satisfy the small missions, so iterate over the missions array and subtract the value of the current operation (starting from the first operation) until you complete it.

if the responses are different, it means that the number is in the intersection between A and B

Not necessarily. The number can be in the intersection, with YES being the honest response, and NO being a joke.

if the responses are the same, it means that the number is not in the intersection between A and B

Also not necessarily. WLOG suppose the number is in A but not B. Answering YES to both is valid, since the second answer can be a joke. Answering NO to both is also valid, since the first answer can be a joke.

It sounds like you are counting joking responses as lies (ie valid but inverted) whereas they should just be ignored entirely. YES YES doesn't eliminate anything because it means it's either in A or B without saying anything about the intersection.

You don't need 1st operation at all. Just apply 2nd until array become [1] or [0].

Can't you just do this - 1. If there is atleast one "1", answer is YES 2. Otherwise answer is NO

Actually, your approach is correct with single distinction: you should reduce to 2*k-1 and apply 2nd operation twice (like in this corner case you mentioned).

In my opinion that's the best way a problem A/B can be. Still challenging, so you have to think to come up with a solution and beginners can develop their problem solving skills further than just improving implementation skills, but with a simple solution, so any beginner can solve it.

Lol me 2! Got FST'd for the first time! I got a time limit exceeded error on test 39. ANyone else?

Same! I think everyone who tried to be greedy without proof failed on TC 46

Maybe hard because of the variety of $$$k$$$

It has updates, so that would be O(N^5/3)

I coded Mo with updates in $$$O(n^\frac{5}{3})$$$ but I can't make it pass. Maybe it's doable with tweaking the constants enough. The general idea is the following.

Let's maintain $$$\mathit{cnt}[x]$$$ — the number of occurrences of a value $$$x$$$ and $$$\mathit{cnt}_2[i]$$$ — the amount of values that have $$$\mathit{cnt}[x] = i$$$. That is trivial with Mo with updates.

How to obtain the answer for the query $$$k$$$ from that? Well, we want to take gcd of all $$$i$$$ such that $$$\mathit{cnt}_2[i]$$$ is non-zero. Then check if it's divisible by $$$k$$$. Obviously, there are $$$O(\sqrt{n})$$$ non-zero values.

How to use that fact? Well, let's split the values into the ones that occur at least $$$P$$$ times in the entire array at least once throughout the updates. There will be about $$$\frac{n + m}{P}$$$ of them. To find them, maintain a set of values sorted by their $$$\mathit{cnt}$$$ and mark the top ones as big after every update. Must be $$$O(m \cdot \frac{n + m}{P})$$$ in total.

So, we can check the values of $$$i$$$ from $$$0$$$ to $$$P - 1$$$ naively and then $$$i = \mathit{cnt}[x]$$$ for all big numbers $$$x$$$. That sums up to a $$$O(P + \frac{n + m}{P})$$$ query. So the optimal $$$P$$$ is around $$$\sqrt{n + m}$$$. Since taking consecutive gcds doesn't make your complexity multiply by log, it's still just sqrt.

So there is a Mo with updates part that is pretty slow complexity-wise and all the other parts that don't exceed sqrt but have a large constant I guess.

It's correct. The number of position where given and sorted differ (which will always be even) is exactly twice the number of swaps needed. If answer is X, first X mismatches would have a[i] = 1 and b[i] = 0, and second X mismatches would have a[i] = 0 and b[i] = 1. These lead to X swaps.