I have another idea: because $$$ 1000 <2 ^ {10} $$$, we can perform the $$$ log_2 {k} $$$ query, and the $$$ i $$$ query the union of the sets which binary expression of the set number's $$$i-th$$$ bit equals to $$$1$$$ in the $$$ i $$$ th query. This can also find the position of the maximum value :-)

1 8 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8

For this test case in C question, the answer should be Ashish but according to the editorial it is Ayush. Please correct me if I am making a mistake. Thanks in advance

That really wonders me how you think in that much easier way.

you're doing a nice job.

but what about "video tutorial for D" for the next contest? ;)

:(

Never imagined B and C could both be easier than A.

Agreed, fast editorials, good problems, nice memes, strong pretests. (At least for me lol) Great contest!

I think your comment. XD

same bro

by looking at the constraints

Because scanning memory byte-by-byte is extremely fast. Reds write brute forces if they pass because it takes less time to write.

I had actually done the same

i have done the same .....and solution is accepted.... but question says that element should not be consecutive ... and in the solution we have not consider this

My O(n^2) solution passed easily.

Here is my Solution

Numbers of Test cases were 100 ! It would be 10^8 in total ! My Solution failed for O(N*N) approach then I opted for using a prefix sum array !

Umm I will attempt to explain ! For choosing out K elements who sum up to give an Odd Number ! So it is prerequisite that We calculate in handy about how many odd and even integers are there in this array , now if no odd number exists it is clear that sum will never be able to get odd ! Another case is when You Have K as odd and CountOfOdd greater than equal to K you can fit these odd numbers in K and get a result , (For eg if you take 1 3 and 5 and sum up it gives 9 so it should be remembered that Taking ODD count of Odd Numbers and summing up gives and Odd Number , Another case will be when You have Not sufficient odd numbers to complete you K in that scenario you can take 1,3,5.. of the odd numbers you have in your count and can opt for taking other even numbers ,There is a catch for N==K case ! it is explained well in Editorial I think

Great explanations :)

11 14 1 6 3 12 20 you can see sum is odd

take 11 14 1 6 3 12 20, the sum will be odd

You can take 11 14 1 6 3 20 16 which has odd sum 71

Read this : comment by mike

You likely hit stack overflow. It's a shame an equivalent C++ solution passes just fine.

For Python you might be able to set a new stack limit. I'm not too sure if CodeForces allows this but you could do:

import sys
sys.setrecursionlimit(10**7)

This may give an error but it's worth trying. (On a side note, a Java solution with dfs also works fine)

I did similar thing using JAVA and I am simply applying DFS here, https://codeforces.me/contest/1363/submission/82320024 , but its showing TLE on 9th test case. IT IS SO SAD CODEFORCES.

I ended up finding one solution, and creating one solution.

1) At first I searched for a while, and found "bootstrap recursion" that someone posted a while ago. Solution: https://codeforces.me/contest/1363/submission/82165464

2) I implemented an iterative dfs. That was challenging, because you need to deal with the return values for the "recursive" calls, and also maintain local variables. Unlike a simple dfs, you can't just push all your neighbors onto a stack, but you have to push one, finish with it, somehow get a return value, and then push the next. I kept a counter that shows how many of the node's children visited the node, and when the counter reached len(neighbors), I filled the return variable, and popped it from stack. Maybe it's trivial and this solution is simple, but I looked a while for solutions for this and did not find even one (only a reference to a pdf that didn't work, about this matter). Solution: https://codeforces.me/contest/1363/submission/82215100

It seems that when asking for the maximum of all indices not in the same subset as the index with the maximum value, you assume the input set was ordered, then use z to iterate through the indices to ignore. If the set containing the index which has the maximum value in the array is not ordered smallest to greatest, extra indices are printed in the query.

I guess it meant that both of the guys wanted to remove it first(special node). To do so they will make each other to remove unwanted leaf nodes. So they will start from the farthest.

Note that not all of the indices need be in a subset. In one of the last loops you print all subsets except one, but since some index might not be in a subset, it could print less indices than indicated (the first number after ?), then block waiting for input.

I made/choose all of them. :) (Although FastestFinger helped with the editorial of F)

can u please tell me my mistake in problem D,it;s giving a weird error in test case 1 itself.

https://codeforces.me/submissions/Lord_Saga

You don't ever initialize vis, so some garbage / data from a previous test case could affect something down the line.

• 29 it goes

Posting the same qn again and again ain't gonna fetch you the answer. I hope you understand that. Be patient someone will eventually pick up your qn.lllll

Remember, node $$$x$$$ can be picked up when it's degree is $$$<2$$$.

The answer should be Ayush, indeed. Let's simulate it.

Ayush picks $$$8$$$.

Ashish picks $$$7$$$.

Ayush picks $$$6$$$.

Ashish picks $$$5$$$.

Ayush picks $$$4$$$.

Ashish picks $$$3$$$.

Now, Ayush can pick either $$$1$$$ or $$$2$$$. He chooses $$$1$$$, and wins.

yes it is possible and it is problem E not D

Because of memory overflow

The second one <3

can u please tell me my mistake in problem D,it;s giving a weird error in test case 1 itself.

https://codeforces.me/submissions/Lord_Saga

hoping to get a reply.

try to use ss.clear() instead of creating a new vector everytime. check this 82160254

Ayush picks node $$$4$$$. Now, it is like the first test case, only the roles are reversed. No matter what Ashish picks, he will make node $$$2$$$ pickable for Ayush.

UPD: I read your question wrong.

If Ayush takes node 4, Ashish is forced to take either 1 or 3, both leaving 2 as a leaf node.

What if the index with the maximum value is not in any of the subsets?

Ummmm ! Now that you have mentioned I suppose it can be done using recursion with some clever memoization where recursively create all the strings of the form 1111's followed by 0000's and strings of form 00000'ss followed by 1111's We will create all the strings and check for a minimum ans out of all such possibilities and to add some memoization for any string we can calculate number of mismatches upto some index and later use it for fast computation !

But Yes DP will be overdoing things a single prefix array will suffice to crack this problem !

Happy Coding :)

I don't think Ashish is the winner in this case ! in the first chance Ayush will go for 3,4,5 or 6 which are the leaf nodes and subsequently he is playing optimal so if you make any sort of choices from this state You will always Find Ayush having the last laugh!

Your code seems to fail for the same test case I generated in this comment.

My idea is make the tree rooted from node x and calculate the amount of sons it has for each brach. Since for win the game I have to make the node x leaf, and for that need to eliminate all nodes of each branch first(all except one branch, I mean if there are k branchs, it is enough to eliminate k-1 of them) then the game is reduced to a modified nim game where the goal is reach the state {0 1} and for each turn the player can select one "heap" (amount of sons calculated previosly) and decrease it by 1.But I can't find a winning strategy for that game, please let me know if I am making some mistake..