Now as the contest has finished could anyone please tell me how to solve D — Flat Subsequence

I don't have a math-heavy perfect proof but you can think in this way.

Lets call polygon of m sides be polygonIn and polygon of n sides be polygonOut. select one side of polygonIn and connect it to the center of polygon the angle will be (2*pi/m) also note that this angle is equal to x*(2*pi/n) (x is some integer) because the end points of a side of polygonIn must be end points of some x continous sides of polygonOut.

Example in case of hexagon and triangle x = 2 because end points of one side of triangle is also end points of 2 continous sides of hexagon.

so we get x*(2*pi/n) = 2*pi/m

x*m = n

n%m = 0

Matuagkeetarp

Here is Code which uses Sieve

ko_osaga hello I have a doubt why didn't you take mod m both sides in 2nd step only

x = (b-a)+km;

take mod m both sides

x%m = (b-a)%m

This gives us the same result is there is something wrong in my way?

Hello, I have a doubt in problem A as the given function has a unimodal graph. I was solving it with a ternary search. As everyone must be aware that there is a condition in a while loop of ternary search. The condition is while(high-low>=3) I found that when I wrote ternary search solution it was giving the wrong answer then I changed that 3 in the condition to 11 it was still giving the wrong answer but on much later test case and when I finally changed it to 100 it got accepted. Can anyone please tell me why it is happening?

As far as I know while(high-low>=x) reduces your search space such that you will finally have x+1 points from [low, high] and the minimum of the function is guaranteed to be in this range.

code failing at test case 6, X = 11 code failing at test case 34, X = 20 code accepted X = 100

Hi kartik8800 could you please elaborate the proof that after sorting if I buy some ith item I will definitely buy first i-1 items also

Supermagzzz In Question C instead of floor((number of zeros)/k) it should be ceil((number of zeros)/(k+1))

It may be a bit late but you can use kadane's algorithm with slight modification in code to solve Div2B first create an array with 0th to the n-2th element of the original array in it then use kadane to find the sum of maximum sum subarray of this newly created array let this be ans1. Then create a second array with 1st to n-1th element of original the array in it and again use kadane to find the sum of maximum sum subarray in it let this be ans2 then ans = max(ans1, ans2) is Adel's tastiness compare it with the total sum of the original array and you are done. Note by creating two different arrays we ignore the possible case in which both first and last element (total original array) was picked kadane's algorithm.

Code — Submission

Yea I also learned this today in problem D

This is not a way to ask doubt you should not spam discussion with full code just post link of your code and try to explain your logic a little bit.

EMEJ Thanks bro really great solution

Another solution for C

Let the position of rightmost zero in nth number be ith position then we know in next number (n+1 th number) all the bits from 0 to ith position will be flipped and only these bits will contribute to our answer so the contribution of any nth number to total answer depends on the location of rightmost zero bit in n-1th number. so we want to find how many numbers are there which have all bits 1 up to i-1th bit and has a zero on the ith bit. It turns out that the number we are looking for has form k*(2^(i+1)) + (2^(i)) — 1. (i = 0, 1, 2 ...) equate it to n for each i find k(take ceil) multiply it by corresponding i and sum them. the total sum will be the final answer

Thanks a lot, Benq amazing explanation.

Thanks a lot to all in this thread This explanation is much better than that of editorial

Yea I know that

Yeah sure, we have to observe that there are only limited strings (exactly 2*N) that can satisfy given conditions. A string should be such that first i characters are all one and rest are zeros or all first i characters are zeros and rest are ones i varies from 0 to n(size of given string). Then I simply calculated difference of each of the 2*N strings with given string and took the minimum answer

resolved

Number the vertex from 0 to n-1 (7) take 0th and 2nd and 4th and 6th vertex

Thanks for the reply but I found that even My code got accepted when I submitted it with GNU C++ 14 / GNU c++ 17 (64). but giving TLE with GNU C++ 17 although I don't know the reason

can anyone please explain to me why this N^2 solution of the problem B is giving TLE on test case 4. My Code

can anyone please explain to me why this N^2 solution of the problem B is giving TLE on test case 4. My Code

I have observed most people used std::set and messy implementations to find the starting point of the cycle but you can use a very easy floyd warshall cycle detection algorithm to find it. you can learn about it on the internet it very easy to understand

Here is my implementation I have heavily commented it at so that you can understand easily