Editorial — Codeforces Round #651

4 years ago, # |

-86

CodeForces? More like MathForces

→ Reply

Arcane

4 years ago, # ^ |

+52

How was this mathforces lol?

→ Reply

GiangBang

4 years ago, # |

-10

i got stuck in problem C because i thought it would get tle for checking primality for some numbers as large as 10^9

→ Reply

4 years ago, # ^ |

Lol. It would be fine if you just check up to sqrt(n) though.

→ Reply

shivam112311

4 years ago, # ^ |

plz post your solution for problem C

→ Reply

4 years ago, # ^ |

I think you missed some corner cases. Try cases where n==1, n==2, n==6, and n==18. Nevertheless, here is my submission 84452415 (It's in Java tho)

→ Reply

kazuya

4 years ago, # ^ |

← Rev. 2 →

Just prime factorize the number. If two is not a prime factor which means odd number AG wins. Else if 2 is a pf and its power is 1 then we have to check the powers of other pf's. Let sum of other powers be 'Count'. If its AG turn he will form an odd number with count — 1 powers and divide so that FF get a number 2*(prime number) so only option he has is to divide by the prime number and AG wins. Rest of the cases can be covered in similar way. You can check my submission.

→ Reply

4 years ago, # ^ |

try this video solution for clarity: (https://youtu.be/6vVDl0e5jjk)

→ Reply

GiangBang

4 years ago, # ^ |

yeah, you are right, i feel so stupid

→ Reply

shivam112311

4 years ago, # ^ |

I did that ..but wrong ans

→ Reply

4 years ago, # ^ |

Codeforces Round #651

Problem C check this

→ Reply

aarav.cube

4 years ago, # ^ |

Primality checking is O(sqrt(n)), so 10^9 should be fine.

→ Reply

shivam112311

4 years ago, # ^ |

← Rev. 3 →

this is my solution 84504888

→ Reply

aarav.cube

4 years ago, # ^ |

Try out this case: n = 30. Ashishgup should win because if he removes an odd prime, say 3, then FastestFinger has no choice but to remove the other odd prime, 5, leaving Ashishgup with 2 and giving him the win.

The case where there is more than one odd prime (powers are distinct) and exactly one power of 2, Ashishgup will always win, because he can remove all but one of the odd primes, and Fastestfingers will have no choice but to remove the last odd prime, leaving Ashishgup with 2.

→ Reply

jai_dewani

4 years ago, # ^ |

I too did got stuck in the same thought, since you can't make a prime table with sieve method and doing brute method will obviously wouldn't work (stupid me :P) so I went back to check if I did some mistake while coming up with a pattern only to waste 20 valuable minutes to understand my foolish mistake in undermining sqrt(n) method of finding prime

→ Reply

ayushgupta_

4 years ago, # ^ |

why to check primality if n is odd then ashish wins because he will divide the number by n

→ Reply

4 years ago, # ^ |

try this video solution for clarity:(https://youtu.be/6vVDl0e5jjk)

→ Reply

Ling_T

4 years ago, # |

← Rev. 2 →

A Quick editorial with 0 available tutorial at first few minutes. (x

→ Reply

4 years ago, # |

Can someone help me figure out why 84488594 is failing for problem D? Seems like I have the main idea..

→ Reply

ScotchOnTheRocks

4 years ago, # ^ |

Yes please! For the love of god please someone tell me what pretest 10 is :((

→ Reply

4 years ago, # ^ |

Try this case: 4 4 1 4 3 2 Your program gives 2 but the correct answer is 3 (I made the same mistake in the contest :P)

→ Reply

ScotchOnTheRocks

4 years ago, # ^ |

Thanks. Figured the mistake. Looks like I'm going to be stuck at 1730ish for a while lol.

→ Reply

pied-piper

4 years ago, # ^ |

What was your mistake can you tell?

→ Reply

4 years ago, # ^ |

Basically, if we only enforce invariant that the smaller subsequence cannot have consecutive elements, you might end up with two consecutive elements inside the bigger subsequence.

Not sure about you, in the counterexample that is provided my solution picked out 1 2 as the smaller subsequence. But the correct smaller subsequence is 1 3

→ Reply

4 years ago, # ^ |

Codeforces Round #651

Problem A and B

Problem C

Problem D

Problem E check it out guys for complete understanding

→ Reply

clairvoyant

4 years ago, # ^ |

if k is odd then we can't choose the Nth element to be part of even indices, similarly if k is even we can't choose the Nth element to be part of odd indices

→ Reply

henryz2004

4 years ago, # |

I almost got Problem C. I thought I followed the right logic. Can someone explain why it doesn't work? (failed on pretest 2)

→ Reply

4 years ago, # ^ |

-7

try this video solution for clarity: (https://youtu.be/6vVDl0e5jjk)

→ Reply

Jarif_Rahman

4 years ago, # |

I think they create the editorial before creating the problems

→ Reply

vivek1401

4 years ago, # ^ |

But they kept every portion blank :P

→ Reply

iamhpp

4 years ago, # |

+10

Wowwwww fast editorial! And nice problems!

→ Reply

PersistentLife

4 years ago, # |

-11

Maths only round？

Yes！

→ Reply

vbv2312207

4 years ago, # |

anone can tell how to get the intution behind using binary search in problems like D?

→ Reply

4 years ago, # ^ |

+22

Do lots of problems w/ Binary Search tag.

I've found there are two types of Binary Search Problems: problems you can solve with lower_bound / upper_bound, and problems similar to the one in this contest.

→ Reply

vbv2312207

4 years ago, # ^ |

exactly .....like suppose you do it with tags mind will look in that direction only .......how to get the idea automatically is what i am asking

→ Reply

4 years ago, # ^ |

I find that typically for maximization and minimization problems, I try to see if DP or greedy work. If not, then try binary search and brute force.

I guess it goes without saying that this requires you to come up with possible solutions and also counterexamples quickly before you start coding.

→ Reply

govindsaj

4 years ago, # ^ |

looking at the constraints might also help..since here the constraints are 2*10**5...so we can use O(nlogn)..which usually means we can use any kind of sort in the answer or we can use binary search with O(n) for each iteration of the binary search

→ Reply

kazuya

4 years ago, # ^ |

-9

can you suggest some problems like these ones?

→ Reply

4 years ago, # ^ |

1208B, 1077D are the ones I've done on CodeForces

875 on LeetCode is also a good one.

→ Reply

Raven__57

4 years ago, # ^ |

You can try these problems in Lightoj, they can help :D

→ Reply

bitch_house

4 years ago, # ^ |

← Rev. 2 →

I will share my idea. Whenever you see a monotonic function (step boolean function in problem D is monotonic) you can apply binary search. In fact monotonicity leads to the correctness of binary search.

→ Reply

goyalnikhil064

4 years ago, # |

@Ashishgup how can you prove that binary search would definitely work in problem D?

→ Reply

4 years ago, # ^ |

+10

Define $$$f(x)$$$ as $$$whether$$$ $$$it$$$ $$$is$$$ $$$possible$$$ $$$to$$$ $$$make$$$ $$$answer$$$ $$$<=$$$ $$$x$$$. Clearly, if $$$x$$$ works, then $$$(x + 1)$$$ works as well. You can easily check whether $$$f(x)$$$ is true in $$$O(n)$$$. Hence $$$binary$$$ $$$search$$$ $$$for$$$ $$$answer$$$ works.

→ Reply

goyalnikhil064

4 years ago, # ^ |

Yeah thanks!

→ Reply

jeetganatra

4 years ago, # |

← Rev. 2 →

-44

Deleted

→ Reply

DankCommenter

4 years ago, # |

← Rev. 2 →

-42

3 reasons why people like Ashishgup should be permanently banned from problemsetting:

1) Round 646

2) Round 648

3) Round 651

→ Reply

vbv2312207

4 years ago, # ^ |

get a life bro you had only 3 submissions credited to your account , atleast grind more and be in an order to say sth to the problem setters cz right now you are in no position to say so

→ Reply

Flower08

4 years ago, # |

+49

Why always asking names as output in C ? instead we can use Yes, No that would be easy and convenient.

→ Reply

an09mous

4 years ago, # ^ |

Agreed

→ Reply

weakestOsuPlayer_244

4 years ago, # |

I tried sieve on A.

//Ashishgup gets me again cause upto 10^6..

anyways still better than the horrible 2 no solves streak..

→ Reply

ajitshiva007

4 years ago, # |

-33

Today Problem C

→ Reply

LaKsHiTh_

4 years ago, # ^ |

+14

→ Reply

4 years ago, # |

On problem E, does anyone have an intuitive explanation why LCS doesn't work?

I think my submission LCS might recommend that we rotate an odd parity subsequence (which is useless). But my brain is fried so I can't come up with a counterexample.

Failing submission:

84510608

→ Reply

PizzaLovers007

4 years ago, # ^ |

10
1100100110
0011011001

Answer should be 3 (your program gives 2):

Rotate indices $$$0, 3, 4, 5, 8, 9$$$
Rotate indices $$$1, 2$$$
Rotate indices $$$6, 7$$$

LCS doesn't work because you have to account for both 101010... subsequences and 010101... subsequences, and LCS causes you to overlap them (indices 4-9 above).

→ Reply

4 years ago, # ^ |

Great explanation! Thank you very much :D

→ Reply

diradon

4 years ago, # |

Can someone explain why we cannot solve C using greedy approach? I tried to maintain 2 different array/sets, and started inserting numbers into them in increasing order, while ensuring that no 2 numbers with consecutive indices land in the same bucket. Final answer should then be min(max(bucket1), max(bucket2))?

→ Reply

4 years ago, # ^ |

I think you're referring to D.

Let's say n=4 k = 4. **Suppose your sorted array (value, index) pairs are as follows : (1, 2) (2, 1) (3, 3) (4, 4)

Your solution ends up selecting values [1, 4], max=4. We want [2, 3], max=3.

→ Reply

diradon

4 years ago, # ^ |

← Rev. 2 →

Hey, thanks for your reply. Although I think I might have failed to explain my solution properly. It'll work as follows:

(1,2), (2,1), (3,3), (4,4)

Bucket1: empty

Bucket2: empty

-> I look at (1,2), insert it in first bucket.

-> I look at (2,1), try to insert it in first bucket, but it already has an index which is adjacent to index of current element that is being considered, so I insert it in bucket 2.

-> I look at (3,3), insert it in first bucket

-> I look at (4,4), try to insert it in first bucket, fail, insert it in second bucket.

The buckets finally are [1,3] and [2,4], out of which I return 3.

This is the link to submission in case it helps: 84501650

→ Reply

4 years ago, # ^ |

You can try

6 6
1 2 1 5 2 1

I think in general, your solution puts the 1 1 1 in one bucket, but the other bucket becomes invalid 2 5 2 has adjacent elements

→ Reply

MyK_00L

4 years ago, # |

← Rev. 4 →

+24

Here's my simpler(imo) solution for F: find a node in the path as described in the editorial, note that this also gives you the lenght of the path you have to find. Keep the delimiting nodes of the path u,v at the beginning both equal to the node you found. While dist[u][v] != solution lenght, make a query with all nodes x with min(dist[u][x],dist[v][x])>=(solution lenght-dist[u][v]+1)/2. At least one of these nodes must be in the solution, so with each query you at least halve the remaining lenght of the path. So you will use 1+log2(path lenght)=11 queries at most. I did not get AC, and I think that is only because I did not read correct/incorrect strings, I'm pretty sure this should be AC... Ok, proofed by AC by reading the strings

→ Reply

akashtadwai

4 years ago, # |

How can we prove formally for question D (Odd-Even Subsequence) that the found element while doing binary search always exists in the given array? I tried on some sample tests its working fine, but I am not able to correctly identify why the element does exist in the original array.

→ Reply

robostac

4 years ago, # ^ |

The boundary where check(x) fails and check(x+1) passes can only exist if x+1 is in the array (otherwise the result of check wouldn't change).

→ Reply

dhruv111

4 years ago, # |

← Rev. 2 →

[deleted]

→ Reply

Wonsei

4 years ago, # |

What the f---! Binary searching over the answer is the COOLEST idea!! Thanks for the quality questions!

WOW!! I learn so much!

→ Reply

tourist_Niche_se

4 years ago, # |

+14

le editorial usually : come again another day

le editorial with FastestFinger : fast as F boi

→ Reply

devPratik

4 years ago, # |

← Rev. 5 →

-13

Ignore this comment #Brainfreeze

→ Reply

4 years ago, # ^ |

The highest odd factor is 15.

→ Reply

devPratik

4 years ago, # ^ |

My bad! Thank you for the clarification

→ Reply

4 years ago, # ^ |

Please help me with the tutorial for D.

I cannot get what does binary search over the "answer" mean in the key idea of the tutorial?

I am posting it here since I don't know how to get my doubt to you other than this way.

→ Reply

lohit_97

4 years ago, # ^ |

← Rev. 2 →

-8

sort the values in the given array.

lets index it from [1..n] where A[i] <= A[i+1].

Let left = 1, right = n.

Now, take mid = (left+right)/2. and check whether you can get a subsequence with A[mid] as min(max(odd_indices),max(even_indices)), if you can, then your answer lies in [mid,right] else it lies in [1,mid-1].

EDIT: I am not suggesting to use the sorted for check() function. check() function should be used with original array. I am suggesting Bsearch on sorted array (instead of Bsearching from 1 to 10^9).

Would recommend you to read about binary search and its applications for more clarity.

→ Reply

4 years ago, # ^ |

Sorry, I may not have been able to clearly state my question. I appreciate your reply.

I know how to implement binary search but was confused with the explanation in the tutorial which asked to binary search the "answer". I assumed the answer meant binary searching the original array and could not understand how is binary search possible for an unsorted array.

Later, after going through all the comments I found that people were talking about binary searching from 1 to 10e9. After mulling on it for a good amount of time I got that the "x" of the tutorial was indeed to be found using binary search (but not on the array given).

So, in all, I was able to upsolve the problem

→ Reply

The_mysterio

4 years ago, # ^ |

If you could kindly say, why are they binary searching on 1 to 10^9 instead of the sorted array? Thanks in advance

→ Reply

lohit_97

4 years ago, # ^ |

I don't think there is any specific reason for that. Maybe it is just done to reduce the complexity of explaining the solution.

→ Reply

The_mysterio

4 years ago, # ^ |

Actually, why is there not a probability for that to give wrong answer?

→ Reply

lohit_97

4 years ago, # ^ |

Why should it give a wrong answer? There isn't probability thing going on here..

→ Reply

4 years ago, # ^ |

If we have a $$$monotonic$$$ $$$function$$$ $$$over$$$ $$$a$$$ $$$range$$$ and it is $$$true$$$ $$$for$$$ $$$some$$$ $$$prefix$$$ and $$$false$$$ $$$for$$$ $$$some$$$ $$$suffix$$$ of the range and it is possible to check it's truth value at a point in the range, then you can search for the point where the function's value changes from true to false by $$$binary$$$ $$$search$$$. The idea being that if for some point it is true, then it will definitely be true for values less than that point.

→ Reply

4 years ago, # ^ |

Sorry, I may not have been able to clearly state my question and I appreciate your reply.

So, in all, I was able to upsolve the problem.

→ Reply

4 years ago, # ^ |

great! .. actually u could sort the array and do binary search over it as well ..

→ Reply

4 years ago, # ^ |

← Rev. 2 →

Yeah, it naturally occured to me after getting the idea of binary search uptil 10e9. In fact, once we sort the array we can fix the index k-1 as the upper bound in our binary search(i.e binary search between 1 to sorted_arr[k-1], where k is the length of the subsequence given as input)

Just that I was mislead by the tutorial or maybe misread the tutorial.

Anyways, thanks for your replies.

→ Reply

4 years ago, # ^ |

In Editorial of D, while doing binary search at for all <=x elements at odd positions it is understood that all elements at odd position should be <= x but why are we not checking that max element at even places should be greater than x

ans = min(max(odd pos) ,max(even pos)) = min( x , max(even posotion))

should't max(even position) be checked to be greated than x

→ Reply

4 years ago, # ^ |

If we find an odd sequence {$$$a_1 , a_2 , ..., a_t$$$} and its maximum value is atmost $$$x$$$ , then no matter what the even sequence is we can always say that the $$$answer$$$ $$$<=$$$ $$$x$$$ . Same goes for even sequence

→ Reply

4 years ago, # ^ |

← Rev. 2 →

I was solving the interactive problem F1 and got WA on test case 3. When I went through the test case I found that there were more than n-1 pairs of nodes in the test case for all the subtests.

Please, help me with understanding the tree diagram in such a case since as far as I know : a tree with n nodes has n-1 edges.

This was my first interactive problem and debugging this would really help me with such problems in future.

Here, is the link to my submission where you can see the test case 3: Code

I am posting it here since I don't know how to get my doubt to you( @FastestFinger ) other than this way.

→ Reply

4 years ago, # ^ |

The first two nodes are the hidden nodes not the tree edge.

→ Reply

4 years ago, # ^ |

Okay, got it. Thank you.

I would be able to debug it now on my machine.

→ Reply

pulkit14

4 years ago, # |

+11

ashishgup and his team are goats(greatest of all times)

→ Reply

C-3PO

4 years ago, # |

← Rev. 2 →

-14

→ Reply

4 years ago, # |

-25

The following is my recursive DP solution of problem 1370C - Number Game

84479320

→ Reply

snyper

4 years ago, # ^ |

← Rev. 2 →

+53

Fun Fact: naming the array "dp" doesn't make the it a dynamic programming solution

Fact2: your dp[] value never gets reused.

→ Reply

4 years ago, # ^ |

Thanks for the sharing the fun fact. I agree with you than naming an array 'dp' does not make the solution a dynamic programming solution. And I also agree with you that the dp[] value never gets reused for the same test case. However, in the multiple test cases problem, the stored value may be used if the even value $$$n \geq 4$$$ has been solved in previous test case.

The following is a small test program for this solution which shows that the dp values are reused in the multiple test cases problem.

Test Program

→ Reply

4 years ago, # ^ |

+10

Aaaaand using the array named "dp" over multiple testcases doesn't make it dp either. Just saying.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

Note that the array stores the XOR value between (p), the ID of the player to make the move, and the ID of the winner of the game, provided that both players make optimal moves. This solution of a sub-problem when $$$n \geq 4$$$ is an even number can be used by another test case that starts with $$$n$$$ or a larger value. Can you suggest more convenient names to the array and to this approach?

→ Reply

4 years ago, # ^ |

Hey man, you can choose any name you like. Even the current name "dp" has nothing wrong in it. You can use the array re-using approach all you want, and yes it will save you at least a little time if you are given such an input that makes you re-use the array. All I'm saying is that it is NOT Dynamic Programming. Re-using a precomputed answer, you can call that memoization at best. You did good, solved the problem, got an AC, congratulations! But for the love of God, don't call it dp.

→ Reply

4 years ago, # ^ |

← Rev. 5 →

Thanks for the kind correspondence. I appreciate your concern. I have always thought about dynamic programming to be among the approaches used to solve larger propblems in terms of the stored results of smaller related sub-problems. The following tutorial is very close to this point. DP

It interesting that removing the unordred map did not change the execution time of the accepted solution. 84540538

→ Reply

saiprasadDuduka

4 years ago, # |

In problem D, I didn't get how binary searching between 1 and 1e9 gives an answer which exists in the array? I understood the logic but isn't there a possibility where for a value x which is doesn't exist in the array satisfies the check condition?

→ Reply

PizzaLovers007

4 years ago, # ^ |

There may be cases where some $$$x$$$ satisfies the condition and isn't in the array, but the binary search finds the smallest possible $$$x$$$. It's never optimal to choose an $$$x$$$ not in the array because you can just use the largest value in the subsequence $$$\le x$$$.

→ Reply

https://mirror.codeforces.com/contest/1370/submission/84508975

4 years ago, # ^ |

The loop invariant for the binary search is that check(lo-1, 0) || check(lo-1, 1) is always false, and check(hi, 0) || check(hi, 1) is always true.

At the end of your binary search, lo == hi. At that point, you know that lo-1 is not a valid x, but lo = hi is valid. So, lo is the smallest possible answer.

→ Reply

CheldonShooper

4 years ago, # |

Is there any alternative solution for problem E?

→ Reply

Bot_Dan

4 years ago, # ^ |

Well the main idea in my solution is same i.e. finding out the longest length of alternating 0s and 1s. I implemented it by deleting the successive index. Here is the link if you want to see it:

→ Reply

4 years ago, # ^ |

just make brackets out of 1 and 0 and find its depth. consider only positions where s[i] and t[i] different.

→ Reply

3 years ago, # ^ |

← Rev. 2 →

Hey! what do you mean by depth of a bracket sequence?
UPD: Got it! Never mind

→ Reply

_asmah98

4 years ago, # |

← Rev. 5 →

Explanation for C :

Cases when n is odd or power of 2 is clear , also corner cases n=1 and n=2 can be handled separately.

Now when n is even we can observe that :

let prime factorization of n be 2^a1..3^a2….5^a3….and so on

if a1>1 then

ashish can simple divide n by 3^a2…….5^a3 and so on and give it to fastestfinger. What can fastestfinger do now ? since n is now power of 2. he will have to subtract one and thus ashish will win.

but if a1=1 then

ashish can’t do this since only one two will be left and fastestfinger will just subract 1 and hence win.

So if a1=1 and n has more than one odd divisor ashish will win why ?

for example take n=30 =2*3*5

ashish -> divide n by 3

n=10;

fastestfinger->has only one option that is divide n by 5

n=2;

ashish subtracts 1 and hence wins.

that is ashish will always take (all odd prime factors product except one number (example for n=30 he takes either 3 or 5 and leaves 5 and 3 respectively) so that fastest finger will have to divide by that “except” and then ashish will win by subtracting 1.

else if there is only one odd divisor fastest finger will win .

example n=14.. ashish have to divide by 7 so then n=2 and fastest finger will win.

→ Reply

sudipto.me

4 years ago, # ^ |

← Rev. 2 →

can you explain n = 36 please

→ Reply

C-3PO

4 years ago, # ^ |

For n = 36 : 2,3,4,6,9,12,18 36 = 2*2*3*3 so ashish will div it by 9 Now 36/9 =4 now fastest finger can only sub 1 from it Then it becomes 3 as 3 is odd ashish will win

→ Reply

_asmah98

4 years ago, # ^ |

Ashish divides by 9 N=4 fastest finger does -1 no other option Now n becomes 3 Ashish divides by 3 and wins.

→ Reply

trivedi

4 years ago, # ^ |

36. Ashishgup divides by 9 . n = 4 FastestFinger needs to subtract 1 . n = 3 Ashishgup divides by 3 . n = 1 FastestFinger cant do nothing Ashishgup Wins

Any case where n = (2^k)*(Non-prime-Odd), k!=1 Ashish can divide by that (Non-prime-Odd) Now Fastest is stuck with 2^k, which obviously has no odd multiples, hence forced to subtract Ashish gets 2^k -1 which is always odd and divides it by itself Ashish passes 1 to Fastest and wins.

→ Reply

sudipto.me

4 years ago, # ^ |

Thank you very much. I understand

→ Reply

_Enigma__

4 years ago, # |

+26

Did anyone else use DSU to solve problem D?

→ Reply

Lolboyyyy

4 years ago, # ^ |

Yep, although binary search would probably have been cleaner and faster to implement.

→ Reply

lemongrab

4 years ago, # ^ |

Please can you explain general idea for your dsu submission

→ Reply

_Enigma__

4 years ago, # ^ |

← Rev. 2 →

+25

Yes, I can try.

Thought Process: We need to fill either the odd or even places with as small elements as possible, to minimise the maximum. Basically, we need k/2 (or k/2+1 for odd positions and odd k) elements which are as small as possible and no two are adjacent.

To do this, we need to sort the elements while maintaining their previous indices.

Now, starting from the smallest, we perform the following:

Mark its position (original index) as visited
If either of the (original) neighbours have been visited, we merge the current position with them using DSU.
We calculate the maximum number of elements we are able to take. If it is <k/2 we continue, if it is = k/2 we need to check for few corner cases here whether to continue for one more iteration or to break right now.

The last visited number is the answer.

Now, how do we calculate number of elements we are able to take:

Maintain a variable to store how many we can take currently.
While making a new set, add 1 to it
Note that from each set we may take (x+1)/2 elements maximum.
While merging two sets, of sizes a and b, subtract their previous contributions from total, and add the contribution of the new merged set.

There are a few corner cases to handle too here:

If k is odd and we can take k/2 elements currently, we must ensure that it contains neither the first, nor the last element.
If k is even and we can take k/2 elements currently, we must ensure that it does not contain both the first and the last element.

→ Reply

joe69

4 years ago, # ^ |

how to make sure u don't take both the first and last element when k is even and what happens when two numbers are equal whose index will u add to dsu

→ Reply

_Enigma__

4 years ago, # ^ |

← Rev. 2 →

We note that we are forced to take the first (or last) element if and only if:

It has been visited
The size of its set is odd

→ Reply

4 years ago, # ^ |

← Rev. 2 →

I didn't thought about that answer is last picked number, and without it I had much more cases to consider, because I was calculating answer. So It was too hard to me to check all cases. And here is my workaround.

if subsequence length k is even, I solve twice. 1) for all numbers except last. 2) for all numbers except first. And awaiting size of k/2
if subsequence length k is odd, I also solve twice. 1) for all number. awaiting size of (k+1)/2 2) for all numbers except both ends. awaiting size of (k-1)/2.

For odd size two cases are correspondingly: minimum of maximum is on odd positions, and minimum of maximum is on even positions. Solve is to wait until we can fit required (k/2 or (k+1)/2/...) numbers.

My code can be easy modified to output subsequence because of this trick. :)

→ Reply

4 years ago, # ^ |

I am doing a similar thing by solving for k, and checking if x (lower bound) is coming from odd and even positions.

But my solution doesn't pass. It would be helpful if you could tell what is wrong, as our approaches are similar (in terms of splitting into odd even). Please have a look at this 84506317

→ Reply

4 years ago, # ^ |

No, your approach is more close to editorial. But with bug. You only checking values that <= x, which is wrong. You need to construct subsequences fairly, honestly, without "number of good elements is enough so it should work". At this moment you may pick first element in both cases.

→ Reply

4 years ago, # ^ |

(I think my code is not so clear) Let's say I am checking if the values <=x are occupying even positions. Then I require floor(k/2) values such that no two are consecutive (so that there is at least one value for each odd index between them ). Also I make sure that an even index does not consider the first value or the last one (last in case when k is odd). In this way I am not just looking for a good enough frequency, but a set which allows me to select values for the other (odd/even) indices also. This makes me feel that the above is not the bug.

If possible provide a test case to tell where something is getting added unnecessarily.

→ Reply

4 years ago, # ^ |

4 4
1 4 4 1

→ Reply

https://mirror.codeforces.com/contest/1370/submission/84502948

4 years ago, # ^ |

That makes the bug really clear. Thank you so much. Now it makes perfect sense to construct the subsequence honestly.

→ Reply

iprakhar22

4 years ago, # ^ |

All the elements (in increasing order of value) only increase the number of numbers we can take. (which is also why the binary search solution works)

In case of equal numbers, the answer wont change because of the order of taking them because if that number were to be the answer, the last taken occurrence can always lead to the satisfaction of the conditions, even if the occurrences before the last one won't.

→ Reply

iprakhar22

4 years ago, # ^ |

I used DSU too (and the same approach) but could not find a bug in my code. Ended up thinking DSU approach would never work. Thanks for the proof by AC :P

→ Reply

u33how

4 years ago, # ^ |

← Rev. 3 →

I too came up with a DSU-based solution to the problem "1370D. Odd-Even Subsequence". If anyone is looking for such implementation kindly have a look.

84624201

→ Reply

saksham2002

4 years ago, # |

Please help me out with Problem C[problem:1370C]

all possible cases which I thought were given right by my code.

→ Reply

Newton

4 years ago, # ^ |

check for 8 and 18

→ Reply

Satoru

4 years ago, # ^ |

← Rev. 2 →

in case 8 your code print "Ashishgup" , but it should be "FastestFinger"

explain:

n = 8 there is no odd divisor for 8 , so Ashishgup will decrease it by one

n = 7 then FastestFinger will divide it by 7

n = 1 Ashishgup can't make any move , so FastestFinger win

→ Reply

saksham2002

4 years ago, # ^ |

Thanks for making it clear

→ Reply

Satoru

4 years ago, # ^ |

Welcome bro <3

→ Reply

Takik

4 years ago, # |

Problem C can also be solved by calculating the Grundy number for the given n. It took only 31ms. 84482491

→ Reply

ritik_patel05

4 years ago, # ^ |

Can you explain the intuition behind using grundy number?

→ Reply

Takik

4 years ago, # ^ |

+13

The Grundy number of a game state is equivalent to the pile size if we think of the state as a single Nim pile. Now, if there is only one Nim pile and it has some stones, first player can just take all the stones. So, in this case if the Grundy number is non-zero, first player wins.

→ Reply

aditya_sheth

4 years ago, # |

In problem E, why are we not treating the strings as circular? or is it the case that not treating it circular will not change the answer.?

→ Reply

4 years ago, # ^ |

Circular won't change the answer.

→ Reply

4 years ago, # ^ |

I don't think it matters if the string is circular or not. My solution was to assign a +1 and -1 to a 01 and 10 respectively and find the maximum and minimum balance(Similar to a parenthesis sequence) and subtract them from each other. A rotation of both strings by an equal amount won't affect the results.

→ Reply

Relief

4 years ago, # ^ |

Your solution would have very simple implementation. Could you please elaborate on how you noticed the similarity to the parenthesis sequence and how it works? why the answer is the difference of those values?

→ Reply

https://mirror.codeforces.com/contest/1370/submission/84516783

4 years ago, # ^ |

Basically in one move I noticed that you could any neighbouring opposite parenthesis and make them vanish. So you could do this for all neighbouring parenthesis in the same orientation. And I also noticed that you could reduce an uphill sequence in the number of steps equal to the max balance same for the downhill sequence. So basically it narrows down to find max of max balance of all uphill sequences and min of min balance of all downhill sequences.

→ Reply

RD_TheCoder

4 years ago, # |

+31

→ Reply

devarshi09

4 years ago, # |

Am I the only one who failed to observe the pattern and brute forced problem C with a recursive solution?

→ Reply

SomeGuyTookMyHandleToo

4 years ago, # |

A pure win/lose recursive solution for C is accepted.

→ Reply

Dr_Strange

4 years ago, # |

How is rating change calculated any ideas?

→ Reply

4 years ago, # |

+16

Why does $$$binary$$$ $$$search$$$ work in D??

→ Reply

kazuya

4 years ago, # ^ |

Because why it shouldn't ? If we apply binary search on answer , Left = minimum element and Right = maximum element of array. And lets find mid. If we can make a sequence such that at odd indices all the elements are less than mid we can say answer will always be <= mid (Don't care what values are at even position). But there is case possible say k=5 and mid = 5 and the sequence till k-1 that we formed looks like 4 2 5 1 _ and the next elements in original array are greater than 5 (mid). Hence if we're just checking if we can form a sequence where all odd indices are supposed to have elements less than mid, in this case answer doesn't exist but check at even position we have 2, 1 and if we putt any value at last index answer will still be <=mid (in this case 2) . Hence we just have to check if for any mid we can form a sequence where either odd elements are less than mid or even elements are less than mid.

→ Reply

4 years ago, # ^ |

It doesn't look like a proof to me.

→ Reply

4 years ago, # ^ |

← Rev. 3 →

To prove that binary search works, we need to prove that the thing we do binary search over, is monotonic. Sorry if my sentence is incorrect. I'm not native english speaker. For example, if "We do binary search over an array", then the thing is "an array", so we need to prove that the array is monotonic. Proving something is monotonic in straight way is hard. So basic approach is to prove by contradiction. Assume that it is not monotonic then get contradiction.

What is the thing we do binary search over? (sorry again if it's wrong sentence) We do binary search over "can we make subsequence with cost not exceeding x?" As I said, we will prove it by contradiction. What means that the thing "can we make subsequence with cost not exceeding x?" is monotonic? For each x its value is either "yes" or "no", so monotonic means that it's either: all "no" for each x from zero up to some point then "yes" for each other x, or all "yes" for each x from zero up to some point then "no" up to the end. To prove easily, we pick which one we prove.

Now proof: Assume that it's non monotonic in the way "no", "yes". Then, to find out how can it be non monotonic, is to take definition of monotonic sequence and make negation. Monotonic means that first all "no", then all "yes". Negation of this statement is that after some x with answer "yes" there is some x' with answer "no". Word "after" means x < x'. But answer "yes" for x means that we can make subsequence with cost not exceeding x, thus it also not exceed x'. Thus answer for x' should be also "yes". Contradiction. Proved.

Now, to understand it under binary search view, we actually prove that if we pick some x in between and answer is "no", then for all x below it answer is also "no", so we don't need to check them. Contrary, if there would be some "yes" then this yes would be x in assumption, and "no" that we checked by binary search is x'. But we proved that for those x and x' it's impossible. I hope it's all clear now.

→ Reply

gohan123

4 years ago, # |

← Rev. 2 →

+35

Hello, when I registered for the round my rating was 2102 so I got registered as out of competition but in previous global round I became a candidate master (2088 rating). But cf still shows that I'm out of competition for this round. Can someone tell me if this round will be unrated for me? Thanks in advance!

Upd: Rating has been changed :)

→ Reply

SpeedCuber

4 years ago, # ^ |

+18

That's very unfortunate. How can codeforces have such a bug MikeMirzayanov

→ Reply

solaimanope

4 years ago, # |

+14

My solution for F is quite different from the one mentioned in the Editorial. Here it is:

By asking a query over all nodes, find $$$x$$$ and $$$d$$$. Let $$$s = f = x$$$ and $$$target = d$$$. Notice that, $$$target$$$ is the distance between the hidden nodes.

Now, while $$$dist(s, f) < target$$$, let $$$p = \lceil\frac{target-dist(s, f)}{2}\rceil$$$. Let, $$$l_s$$$ be the list of nodes which are at distance $$$p$$$ from $$$s$$$ and they are reachable from $$$s$$$ without using any nodes on the path between current $$$s$$$ and $$$f$$$ (exclusive). Define $$$l_f$$$ in a similar way. Now, we can guarantee that, at least one node $$$x$$$ exists from the union of $$$l_s$$$ and $$$l_f$$$, which is on the path between hidden $$$s$$$ and $$$f$$$. We can find that $$$x$$$ by asking a query over the union of $$$l_s$$$ and $$$l_f$$$. Then, if $$$x$$$ is an element of $$$l_s$$$, replace $$$s$$$ with $$$x$$$. Otherwise ($$$x$$$ is guaranteed to be an element of $$$l_f$$$), replace $$$f$$$ with $$$x$$$.

In each turn of the loop, the distance of $$$s$$$ and $$$f$$$ increases by $$$p$$$. Also, at the end of each loop, current $$$s$$$ and $$$f$$$ lies on the path between hidden $$$s$$$ and $$$f$$$. In the end, $$$s$$$ and $$$f$$$ will achieve the hidden values. Notice that, the distances we find after first query are useless in this solution!

→ Reply

islingr

4 years ago, # ^ |

← Rev. 4 →

I came up with the same solution (but failed to implement it in the given time, rip, code in case anyone wanted). The nice thing about this solution is that it takes atmost $$$10$$$ queries without having to resort to handling the kinda annoying edge cases which the editorial solution requires.

→ Reply

yvasant

4 years ago, # |

Can Anyone please help me understand why my these submissions to B give RTE

84447747

84439096

These are failing on test case : 3 1 3 5 7 9 11

While solution with while loop(84447747) passes on local, but I want to know even in for loop case if second(i<v[0].size()-1) condition fails why code goes inside this loop. Am I missing something basic here.

Would be great if anyone can help, Thanks in Advance!

→ Reply

robostac

4 years ago, # ^ |

v[0].size() is unsigned. If size is 0 and you subtract 1 from it you get a very large positive number.

→ Reply

Lithosphere

4 years ago, # |

can you do DP for question D? I tried and got nowhere

→ Reply

4 years ago, # ^ |

I don't think that DP would help here as any information stored with the state information as the length of some prefix should be sufficient only when there is some information on the length of subsequence actually considered.

Thus at least 2 dimensions — length of prefix and length of the subsequence are required at least. This would demand a lot of space.

→ Reply

Harshil_

4 years ago, # |

Can somebody tell me what was your thought process during solving Problem D? How did you get to the solution?

→ Reply

Shroudedwolf5

4 years ago, # ^ |

In my case , during the whole contest i was thinking about greedy or dp solution. Later i saw in the editorial the word binary search, closed the editorial, thought for a while and got the solution.

I think remembering to try to use greddy, dp or binary search for minimization/maximisation problems will help.

→ Reply

piyush33patel

4 years ago, # |

FastestFinger In A, why there wasn't this test case 100 1000000 1000000 . . .

My solution would have failed, right?

→ Reply

Everule

4 years ago, # ^ |

No. It passes that test case.

→ Reply

hunter_sam01

4 years ago, # |

Hi everyone, i really need help!!! Can anyone just tell me ,why am i facing RUNTIME ERROR on the 2nd question https://mirror.codeforces.com/contest/1370/submission/84517421

→ Reply

4 years ago, # ^ |

You are getting an overflow i think for cases where s1.size()==0 or s2.size()==0 so in your for loops s1.size()-1 will actually become 2^63-1 which is quite large and since size of s1 is 0 it would give a runtime error. To view this on line 21 try to print s1.size()-1

→ Reply

hunter_sam01

4 years ago, # ^ |

Thank you very much!!! I got what you are saying and will keep this in mind in future contest.

→ Reply

yvasant

4 years ago, # ^ |

← Rev. 2 →

Hey,

I also faced same problem turns out s1.size() is unsigned so subtracting 1 gives some big number(2^63-1) so you are entering in for loop.

here is edited version of your solution which would work soln

→ Reply

4 years ago, # |

← Rev. 2 →

Can somebody please explain how to solve E? Not the key idea, it is very easy, but why finding the maximum sum subarray of that array will work for E, because I cannot understand it from the editorial.

→ Reply

4 years ago, # ^ |

You can read Kadane's Algorithm to find the maximum sum subarray.It's a very standard problem. Here, it's the maximum absolute subarray sum so you can first find maximum positive subarray sum, then replace -1s with 1s and vice versa and then again find maximum positive subarray sum and take max of the two.

→ Reply

4 years ago, # ^ |

Thanks. I understand how to find the maximum sum subarray, but I don't understand how this relates to this task and why it will work. I'm sorry^ I have written my thoughts in first comment in the not right way, so it must be: "Why find the maximum sum subarray of that array will work for E?".

→ Reply

4 years ago, # ^ |

+11

I think the much simpler solution is the one with two sets of posittions. One set contains the 0s in s which are 1s in t, and the other set the 1s of s which are 0s in t.

With these sets we can more or less simply construct a list of indexes of positions of alternating symbols in s. In each step construct the longest possible list and remove all those elements from the two sets.

→ Reply

4 years ago, # ^ |

I tried to do something like this but without sets and it was giving TLE. How I can construct the longest possible list if I have indexes in sets?

→ Reply

4 years ago, # ^ |

← Rev. 3 →

Start with the smallest number of both sets, then take the next higher number from the other set, alternating. Since both sets are always of same size this works fairly simple.

Example 84498652

This one is more clean 84488036

→ Reply

4 years ago, # ^ |

Thanks, I will try it.

→ Reply

vineetjai

4 years ago, # ^ |

While creating a list of your iterating over all possible value of indexes but you don't have to iterate just do a binary search on the index. Let suppose you choose index ith for s[i]=1 and t[i]=0 then in the set of indexes were s[k]=0 you have to search for just a higher index than ith let say that j. So iterating from ith to jth is not a good idea it will give TLE. Instead you can do a binary search on indexes if you know ith.

I had also done the same mistake. My Solution for TLE.

The correct solution of SecondThread who used the same approach with higher(same as lower bound in c++) in treeset in java.

→ Reply

akane_psycho

4 years ago, # ^ |

Wouldn't the maximum absolute value of the sum of any subarray in a be reduced to maximum length subarray having only 1 or only -1 .

→ Reply

4 years ago, # ^ |

I solved E task by simply making brackets sequence from 1 and 0 and finding it's depth.

→ Reply

4 years ago, # ^ |

That is clever, because it is super simple code.

But... how did you come up with the idea?

I stopped thinking and started implementing when I saw a solution with sets of indexes, and simulating the shift process. Which is obviously more work.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

I came up with idea in following way. I did write some bunch of zeros and ones for two strings with equal amount of ones. Then I tried to shift few subsequence, and got idea that picking already matching positions is silly, because we can pick any subsequence. So, then, I threw off my test, and wrote new that doesn't match in each place. I wrote new two strings, and tried to move it as a whole. My hypothesis was that they match. So I tried to beat this hypothesis. Question was to find test where strings doesn't match. It was hard to make a good one, so here what I got:

10
1011000110
0100111001

I still have it because I was testing on it my solution. BTW: always save tests you make, with answers. It will help test a lot. So... When I had this test, I realized, that when I shift it as a whole, some ones are matching and vanish. For a moment I thoughts would it give better result if I shift subsequence? I had feeling that it would not. So I thought about following approach: move all once and remove matching. Repeat until all match. Then, I tried to write simulation using sets, I even wrote most of it, but it had issue. I stucked when I had to find those which will match on next step. And when I was thinking about it, they were matching like a brackets. Also, it's like you bought something and now you can sell it. Which is also like a brackets. So I started to think about brackets. First version that I wrote was calculating place where you can start to make correct brackets sequence, and then summing depths of each closing brackets. When I tested it on samples and on my own test above, result was too high. So I revisit why I am thinking about depth summation, and come up with idea that it's just maximum depth.

→ Reply

4 years ago, # ^ |

Thanks!

→ Reply

4 years ago, # ^ |

Oh! At first look I thought this is same: https://mirror.codeforces.com/blog/entry/79107?#comment-646441

So I didn't dig into details. But now I see it's much more complicated! Here is my algo in all details.

My algo in all details

Here is simulation that I'm talking:

1011000110 // shift as a whole
0100111001
-> you get this:
0101100011 // eliminate matching
0100111001
*** *  * * // matching positions, eliminate them!
-> you get this:
1001 // shift as a whole
0110
-> you get this:
1100 // after shift
0110
 * * // matching positions, eliminate!
-> you get this:
10 // after shift
01
shift once again, and we're done.

Now you can see that it's following in brackets terms:

1011000110 // shift as a whole
0100111001
()(()))(() // original. after shift () will vanish:
** **   ** // eliminate them
-> you get this:
())( // it doesn't look natural. but look at corresponding 1 and 0:
**  // matching brackets
1001 // it is same as we got with previous method!
0110
-> you get this after vanishing brackets:
)(
once more vanish them. and we're done.

So you need to consider string as circular, and find it's depth. Source: 84499468

→ Reply

4 years ago, # ^ |

I got a visualization like this, consider string of positions in s[] which differ to the ones in t[]: "10111000"

1: 101    0
2:    1  0
3:     10

The first line are the elements we can change with first operation, second with second etc...

So it is obvious that we need to depth of the bracket sequence. And shifting the sequence is trivial, we just have to consider max(depth)-min(depth).

→ Reply

Kellanved

4 years ago, # |

-24

C was harder than D. Other than that, nice contest!

→ Reply

4 years ago, # |

I am unable to find any fault in my code but my code is showing runtime error on test case 2 for problem B. Please help me to get out of this.
Link to my submission is https://mirror.codeforces.com/contest/1370/submission/84475986. Thanks in advance for reply :)

→ Reply

disgrace_2k

4 years ago, # ^ |

Did you check the case when the size of your vector is zero?

→ Reply

4 years ago, # ^ |

Yes, in that case, program counter does not goes to that loop as i=0 is not less than v.size()-1 as 0>-1

→ Reply

Phantom2611

4 years ago, # ^ |

← Rev. 3 →

nope v.size() returns unsigned intger , so when the vector is empty it returns 0 and since it is unsinged subrtacting one from it does not make it -1 but makes it 18446744073709551615 . So to avoid this typecast it to signed int first then subtract -1 .

(int)v.size()-1;

→ Reply

4 years ago, # ^ |

oh i see.....thanks for the reply

→ Reply

4 years ago, # |

For D, I did the same thing — binary search on x. However, I checked separately for odd and even indices, i.e, the maximum number of valid odd places satisfying <=x condition. Similarly for even indices. The count should be >= ceil(k/2) for odd and >= floor(k/2) for even (when assuming that to provide the answer).

I am unable to understand why my submission: 84506317 fails on test-22. It would be helpful if someone could give a smaller input which fails and/or tell me what mistake I have committed.

→ Reply

Lithosphere

4 years ago, # ^ |

why the ceil and floor @two-wrist?

→ Reply

4 years ago, # ^ |

If length is k is odd then there will be one more odd index than the number of even indices.

Ex: if k=5 , 3 odd and 2 even indices

1(odd) 2(even) 3(odd) 4(even) 5(odd)

→ Reply

dra2421

4 years ago, # ^ |

← Rev. 2 →

you can check my solution https://mirror.codeforces.com/contest/1370/submission/84553455. I have also checked separately for even and odd indices

→ Reply

4 years ago, # ^ |

What is the use of b.size()<k/2 and c.size()<k/2 in the ifs? Anyways, I think I have an implementation bug, which I am not able to find.

→ Reply

saajid_chowdhury

3 years ago, # ^ |

For anyone still stuck, try 4 4 1 2 3 1 (correct answer is 2) and 6 6 1 2 3 4 5 1 (correct answer is 4)

→ Reply

idk321

4 years ago, # |

My nlognlogn solution for D passed the pretests but not the system tests. First I sorted all the numbers in an array in ascending order by value. Then I used binary search to get the minimum length prefix of the sorted array which could alone form either the even or the odd indices (when checking whether is it possible I sorted the array in ascending order by index, thus nlognlogn).

→ Reply

sudipto.me

4 years ago, # |

Can anyone explain n = 36 for problem c. How "Ashishgup" wins this game.

→ Reply

Continuous

4 years ago, # ^ |

← Rev. 4 →

36/9 =4 4-1 =3 3/3 =1 So fastest finger has 1. Hence winner is ashish.

→ Reply

robostac

4 years ago, # ^ |

Ashishgup divides by 9 giving 4 to the other player. Other player can only return 3. Ashishgup can then divide by 3 to give 1 to the other player and win.

→ Reply

4 years ago, # ^ |

So 36 = 4 * 9. In his first move Ashishgup divides 36 by 9, so now number is 4. 4 = 2 * 2. Because 4 do not have odd divisors, another player must decrement it, so now number is 3. Than Ashishgup divides 3 by 3 and now number is 1. Now Ashishgup wins because another player cannot do a move.

→ Reply

ezdp

4 years ago, # ^ |

Ashishgup divides by 9. N = 4
FastestFinger is forced to subtract 1. N = 3
Ashishgup divides by 3. N = 1
because N = 1, FastestFinger loses -> Ashishgup wins

→ Reply

vinayak_jha226

4 years ago, # |

https://mirror.codeforces.com/contest/1370/submission/84475609 why is my answer wrong on pretest 2??

→ Reply

Satoru

4 years ago, # ^ |

your code printed 14 lines instead of 12 lines

→ Reply

goalfix

4 years ago, # |

Hi, can anyone tell me what is wrong with my approach for E? Instead of finding the min num of 1010s, I tried to find the longest consecutive 1111's that were not alr in correct position. Its failing on pre-test 10 and I'm not too sure why. A counter example would be nice. Thank you in advance! 84521497

→ Reply

giorgtarkha

4 years ago, # ^ |

← Rev. 2 →

imagine this input:

``10

``1110010001

``0001101110

I believe yours would output 3, while the answer is clearly 4.

→ Reply

goalfix

4 years ago, # ^ |

sflr but thank you!

→ Reply

giorgtarkha

4 years ago, # ^ |

no problem :)

→ Reply

swapnil159

4 years ago, # |

← Rev. 2 →

How does number of queries get reduced by 1 after setting lower bound of binary search to ceil(l/2) ??

Consider a tree where there is an edge between ith and (i-1)th node for all i>=2.
And the two hidden nodes are 1 and 2. l in this case l would be 1. The max depth of a node would be 999. So earlier (when lower bound of binary search was 0), we would have searched in [0,999]. Now after changing that we will search in [1,999]. So this would also take 10 queries and hence 12 in total.

What am I missing here??

→ Reply

MyK_00L

4 years ago, # ^ |

You can also set upper bound to l. In any case I think my solution is more elegant/easier to understand

→ Reply

swapnil159

4 years ago, # ^ |

Thanks, figured that out. Just got AC. btw link you mentioned is of editorial. I had a look at your solution though, your code is really elegant. It's niceee.

→ Reply

MyK_00L

4 years ago, # ^ |

It is a link to another comment of mine in this page, which explains my solution, for some reason today I decided to use rust, since it won't be rated for me anyway, so code ended up being somewhat long...

→ Reply

marshu

4 years ago, # |

I have a question about C — Number Game: What if n is 18, shouldn't FastestFinger win? Here is my reasoning:

Ashishgup — 18 / 9 = 2 FastestFinger — 2 — 1 = 1 Ashishgup — 1

Since Ashishgup has 1, FastFinger should win. Is there something I am doing wrong since my answer WA on test case 2 when n = 18

→ Reply

krishna_0_9

4 years ago, # ^ |

Ashishgup will play optimally so he will divide by 3 and not 9

→ Reply

swapnil159

4 years ago, # ^ |

Ashish — 18/3 = 6
Fastest — 6/3 = 2
Ashish — 2-1 = 1
Fastest — ....

Ashish wins

→ Reply

4 years ago, # ^ |

AshishGup being one of the smartest(True Story) will divide by 3 in the first move making n=6 now if FastestFinger makes it 5 Ashish divides by 5 and wins otherwise is FastestFinger makes it 3 Ashish divides by 3 and wins.

→ Reply

4 years ago, # |

← Rev. 2 →

Someone please help me with the tutorial for D.

I cannot get what does binary search over the "answer" mean in the key idea of the tutorial?

→ Reply

_nicktz1408_

4 years ago, # |

Hey guys, I need help on problem D. The approach I found seems correct, but it fails on TC 10.

Here it goes: Let's say the optimal answer is x. Obviously, x should be equal to an element in our array. Otherwise, assuming we found an optimal answer, we could decrease it until it reaches $$$min(max(s_1,s_3,s_5,…),max(s_2,s_4,s_6,…))$$$ (our answer). Let's now say that $$$x = a_l$$$.

We can try to binary search $$$l$$$ in the following way: Say in our current step we are at $$$mid$$$. We sort the array in ascending order and we mark the first $$$mid$$$ elements (using true/false values). Then, we apply this marking to the initial arrangement. Now, we will try to create a desirable sequence and try to fit as many marked elements as possible at either odd or even indices (I will call them from now on subsequences). Say we can squeeze them in the even indices. Then, we get $$$min(max(s_1,s_3,s_5,…),max(s_2,s_4,s_6,…)) = max(s2,s4,s6,...) <= a_{mid}$$$, as $$$a_{mid}$$$ is marked as well. Hence, we get a valid sequence (and we can decrease $$$mid$$$ in our binary search).

One way to see if we have an answer is to get the maximum marked elements we can get in odd or even indices. If we have two adjacent marked elements, we can only use one of them in our subsequence, because if both of them are included in the even one, then we can't have any element in the odd index between them). So, we can use dynamic programming in the following way:

$$$DP_i$$$ denotes the max number of marked elements that there exist in even or odd indices in the first $$$i$$$ elements of our sequence. Here is our recurrence relationship: $$$DP_{i + 1} = max(DP_i, DP_{i - 2} + 1, if i is marked)$$$. That means, we can either ignore our current element and get the answer from the previous one or (if it's marked) we can include it, but we can't use the previous element, hence the $$$DP_{i - 2}$$$ term.

The maximum subsequence we can form will be equal to $$$DP_n$$$. If it's bigger than the desired length of the subsequence (more about it in a moment), then we can return true on the binary search predicate. But there is one more technicality we need to resolve. What should we do with $$$k$$$? Let's have a look.

*If $$$k$$$ is even, then it doesn't matter whether we are trying to fill an even or an odd subsequence, as they should have the same size. Therefore, we can try and find the min $$$l$$$ such as we squeeze exactly $$$k / 2$$$ elements in an either odd or even subsequence.

*However, if $$$k$$$ is odd, then the even subsequence will be one less. So, we have 2 cases: *if the first element in the array is not marked, then we include it in our odd subsequence and solve the problem on the interval $$$(2...n)$$$ with $$$(k - 1) / 2$$$. *if on the other hand it's marked, then it's best to include it on the odd subsequence. Then, we see that our problem is reduced to the above one (ie. interval $$$(2...n)$$$ with $$$(k - 1) / 2$$$).

Here is my submission: https://mirror.codeforces.com/contest/1370/submission/84494240

→ Reply

mohanraghug

4 years ago, # ^ |

← Rev. 2 →

+11

You might run out of positions for other parity. Try this case

5 4

1 2 3 4 1

→ Reply

_nicktz1408_

4 years ago, # ^ |

Thanks for your prompt response! :)

I did not even think about this!

→ Reply

durmanko

4 years ago, # |

← Rev. 2 →

However, we can solve C with DP.

Suppose that dp[n] = 1, is First player wins if we start with n, 2 if second wins.

Then dp[1] = 2, dp[2] = 1. For all odd N, dp[N] = 1. If n mod 2 = 0 and n > 2, we cant subtract 1 from n(because n becomes odd and second player wins).

So we can only divide N. lets find all odd divisors of N greater then 1.

Suppose we find divisor f which is odd. When if dp[n / f] = 2, it means that dp[n] = 1.

Dont forget to save dp states in recursion! Code: https://mirror.codeforces.com/contest/1370/submission/84458094.

→ Reply

Arg_007

4 years ago, # |

+20

In problem E , can someone prove that why is it never optimal to include any indices $$$i$$$ such that $$$s_i = t_i $$$ ? I couldn't prove this by myself.

→ Reply

dickings

4 years ago, # ^ |

← Rev. 2 →

I don't know how to prove it. But there always exist a way to get minimum number of operations by ignoring the place $$$s_i=t_i$$$.(The way is mention in tutorial).So we can ignore the $$$s_i=t_i$$$ place.

→ Reply

sanchit_1999

4 years ago, # ^ |

Taking those indices would always require atleast 2 cyclic shifts in some cases where not taking them does in lesser steps. Also, we don't even need more than one cyclic shift in any optimal answer for each subsequence as we could split string s into many subsequences. This proves that taking indices of equal parity will only increase the number of steps.

→ Reply

4 years ago, # ^ |

In editorial there is no proof. Ashishgup It's bad habit I think to not include proof but place some substitution instead. It it relies on very non-intuitive thing that $$$s_i = t_i$$$ can be ignored. I don't know how to prove it. Ashishgup if you have original proof though, I would like to see it, because here is what I got, and it's complicated enough. I added some redundant explanations just to make it rigorous. Short version could be made, but it is proof not substitution.

There are some moments in editorial that I would call mistakes. First, is that subsequences must be of the form 0101. And part with "assume $$$c \geq 0$$$ (otherwise we can interchange 1 and -1)".

Instead of proving that $$$s_i = t_i$$$ could be ignored, I'll prove that algorithm from editorial is correct, and it indeed find optimal solution. I'll use some facts and observation from editorial, but add more details, more facts and fix things I dislike. And fact that you can omit matching positions will be as a corollary of the proof.

Alright.

horrible wall of text

I'll start with point that is not restricted by any assumptions: there is optimal sequence of actions that use only subsequence of the forms 010101 and 101010. Proof by contradiction: suppose we don't have optimal sequence of actions that use only subsequence of this form. Then, we can pick any of optimal sequence, and replace action (shift of subsequence) by other action of form we need. How? For each group of consecutive 1 or 0 shift only first. For example:

1?1?1??00?10??11?10 // question marks - positions that we don't touch
1??????0??10??1???0 // this is equivalent shift
1??01?10?0111 // example 2 with 1 on both ends!
???01??0??1?? // this is equivalent shift

Why? Because all of consecutive ones within a group will move onto next selected positions. And, for each except last one within the group next position is also one. Thus, values on all positions within the group except first position won't change. And, last one within the group move onto position of next zero. It's equivalent to directly move first one to next zero. Similar thing holds for a group of zeros. (this is basically rephrased first point from editorial)

Now, consider array $$$a_i$$$ from editorial and we claim that $$$max\left(\left|\sum\limits_{i = l}^r a_i\right|\right) (1 \leq l \leq r \leq n)$$$ is an answer.

First, prove that we can achieve it by construcition. When this maximum is zero, then we don't need any shifts. Otherwise, we need to show how to reduce it by one. In other words: we need to find shift in original sequence of zeroes and ones that reduce this value (maximum subarray sum) at least by one. So we must reduce value on each subarray with this maximum.

To make it happen, our idea is to pick subsequence of form 1, -1, 1, -1 or -1, 1, -1, 1 from array $$$a_i$$$. By definition of $$$a_i$$$ those forms are forms 1010 or 0101 in $$$s$$$ from which optimal answer can be constructed. Also by definition non-zero $$$a_i$$$ is when $$$t_i \ne s_i$$$. Thus, after shift all picked $$$a_i$$$ become zero. (this wasn't stated clearly in editorial)

I dislike apporach in editorial to prove it. Because it doesn't mention what if maximum subarrays with different sign, what if subarrays intersect each other what if we want to pick same -1 or 1 for two subarrays and so on.

Instead, lets pick first non-zero value in $$$a_i$$$ and then greedy make maximum alternating sequence. If last value is same as first, then don't pick it. After this process we have subsequence of form we want. Now, prove by contradiction. Assume that there is still some subarray with maximum sum on range (l, r) with same or greater value as previous maximum. It doesn't mean it was same value before! Look at that subarray values before shift ignoring zeroes. Ignoring zeroes this means that after -1 until selected 1 there are only -1, similarly after 1 until picked -1 there are only 1. In other words:

// let say this is what is in subarray (ignoring zeroes):
-1  ?  ?  ? 1 ? -1  ? 1 ? // question marks - not picked ones
-1 -1 -1 -1 1 1 -1 -1 1 1 // actual situation (we pick greedy)
 0 -1 -1 -1 0 1  0 -1 0 1 // values after shift
// the sum before shift has form -a +b -c +d, where a,b,c,d > 0
// the sum after shift has form -(a-1)+(b-1)-(c-1)+(d-1)
// it is equal to -a +b -c +d -1 +1 -1 +1 = -a +b -c +d

Because we pick greedy, we know its structure. If number of our picked values within array is even, this means previous sum over this subarray was the same. But it also means that before shift subarray wasn't maximum. Because either (l+1, r) or (l, r-1) would be better, because one of them is by one greater, and other by one less. For positive sum better is one with greater, and for negative sum better is one with less sum. So this is contradiction with the fact that this subarray absolute sum is at least maximum before shift, because its sum is equal to sum of subarray which is stricly less than maximum by absolute value

Assume now that number of picked elements is odd within subarray. And number of picked negative elements is greater within array.

// let say this is what is in subarray (ignoring zeroes):
-1  ?  ?  ? 1 ? -1  ? // question marks - not picked ones
-1 -1 -1 -1 1 1 -1 -1 // actual situation (we pick greedy)
 0 -1 -1 -1 0 1  0 -1 // values after shift
// the sum before shift has form -a +b -c +d -e where a,b,c,d,e > 0
// the sum after shit has form -(a-1)+(b-1)-(c-1)+(d-1)-(e-1)
// which is -a +b -c +d -e +1 -1 +1 -1 +1 = -a +b -c +d -e +1

If after shift it has negative or zero sum, then its absolute value is less than before, so we reduced it. If it has positive sum, then it wasn't maximum subarray, because if we "trim" -1 from both ends we get better subarray before shift was made. Contradiction with maximum again. Same argument applies if number of positive picked elements is greater within array.

Phew. Note! We proved that we reduce maximum at least by one, but we didn't prove it's exactly by one. It will be later.

Summary: we know how to construct sequence of actions to make strings equal after steps (or sooner) we calculate as maximum absolute value of sum over subarray. Now, we want to prove its optimality. We also prove it by contradiction.

Let $$$steps(a)$$$ be the maximum absolute value of sum of subarray $$$a$$$. In other words, $$$steps(a)$$$ — the number of steps we know how to achieve. Assume there is optimal sequence of actions that make $$$s$$$ into $$$t$$$ into $$$k < steps(a)$$$. We think that after each shift according to our sequence of shifts $$$steps(a)$$$ decrease by one until it reach zero. Here is where our answer comes. But in optimal sequence of actions that reach goal faster, it starts also from $$$steps(a)$$$ but turns into zero in less steps. It means that after some action from optimal strategy $$$steps(a)$$$ should decrease by at least two. It may increase at some point, but it has to decrease by at least two after some action. To prove it more clearly. Consider all values of $$$steps(a)$$$ calculated over current array of $$$a$$$ after execution of each step from optimal actions in corresponding order. There are k steps and by our assumption it's better than our answer: $$$k < steps(a)$$$. So among those values there is less than $$$k$$$ different values, so difference between some consecutive steps should be at least two. Thus, if better answer than ours exists, it should decrease our function $$$steps(a)$$$ with single action by at least two. (this was in editorial but in much fewer words, assuming you know this method of proofs, but we want rigorous proof, so I explain it in details.)

Let's prove that decrease $$$steps(a)$$$ function at least by two using any allowed shift is impossible. Prove it by contradiction again. Assume we can shift subsequence and decrease $$$steps(a)$$$ by at least two. If it is possible, then there is such $$$s, t$$$ and corresponding $$$a$$$ and corresponding shift of subsequence that reduce $$$steps(a)$$$ at least by two. Consider subarray of $$$s$$$ with maximum absolute value. Its absolute value should also decrease at least by two. This time we can pick position with $$$a_i = 0$$$, and $$$s_i$$$ can be 0 or 1 for it. After shift some of $$$a_i$$$ values are changed. Old observation: any shift is equivalent to shift of the form 010101 or 101010. New observation: for shifts of forms 010101 and 101010 $$$a_i$$$ change on all picked positions by definition of $$$a_i$$$. Second new observation: by definition of $$$a_i$$$ and fixed $$$t_i$$$ it means that for each position $$$a_i$$$ may have only one non-zero value. Also, selected $$$a_i$$$ can not have two consecutive -1 or 1 — it violates form 010101 or 101010. This allows us to reconstruct selected $$$s_i$$$ at positions of equivalent shift of selected $$$a_i$$$, and then find out $$$a_i$$$ after shift. Example:

1 0 -1 -1 0 1 // = a imagine it is selected in equivalent shift.
1 ? 0  0  ? 1 // = s by definition of a
//^- here should be zero by alternation of 0 and 1
//so this equivalent shift is impossible

// imagine it is selected in equivalent shift.
1  0  0 -1  0 -1  1  0 // = a 
1  ?  ?  0  ?  0  1  ? // = s by definition of a
1  0  1  0  1  0  1  0 // = s by the form of subsequence in s.
0  0  1  1  1  1  0  0 // = t by s and a
0  1  0  1  0  1  0  1 // = s after shift
0  1 -1  0 -1  0  0  1 // = a after shift

Also, by the form of subsequence in s, selected $$$a_i$$$ non-zero values should also alternate, and their alternation is shifted after shift. So, result of shift is completely determined by number of zeroes we have and their positions. If we had:

 1 -1  1 -1  1 -1 // hidden selected a before shift
    *     *  *    // places where we see zeroes, other is visible
-1  1 -1  1 -1  1 // hidden selected a after shift
 *     *        * // places replaced by zeroes after shift
                  // just bitwise complement

Now, key observation. It's the only four ways how $$$a_i$$$ may change:

 1 -1  1 -1 // hidden selected a before shift
 *  *       // place where we see zeroes
-1  1 -1  1 // hidden selected a before shift
       *  * // place where we see zeroes after shift
 ^     ^
// positions with 1 in both cases decrease.
// from 0 to -1, or from 1 to 0.
    ^     ^
// positions with -1 both increase.
// from -1 to 0, or from 0 to 1.

So, no matter zeroed $$$a_i$$$ or not, we always change it only in one way. It's counterintuitively but look and check yourself. Shift following

1010 // = s
1001 // = t
0101 // = s after shift
0 0 1 -1 // = a
-1 1 0 0 // = a after shift

Now, we know that any subarray of original $$$a$$$ has some consecutive number of picked elements, and their change value is based on parity of their index within subsequence, so two consequtive neglect each other and only remaining one if their number is odd will take effect in resulting sum of subarray. So, in other words, if m consecutive picked elements are within subarray and m is even, then sum doesn't change no matter what. If m is odd then change of sum of subarray is equal to change of $$$a_i$$$ of first shifted element, which is 1 by absolute value. Thus, you can't reduce absolute value of maximum sum of subarray using any of allowed shifts at least by two. As a consequence, our construction should reduce at least by one: because by two and more it can not, but it reduce.

Summary, for each allowed shift, there is equivalent shift which does the same but it consists only of changed positions (where $$$s_i$$$ change after shift). Value of $$$a_i$$$ on those positions is changed only based on first shifted $$$s_i$$$ and parity of index in subsequence no matter was $$$s_i = t_i$$$ or not. Thus, two consecutive $$$a_i$$$ neglect each other, and sum can be changed only by one. Done.

It was very hard to proof. As a corollary, during construction of sequence of shifts we ignored $$$s_i = t_i$$$, so they can be ignored.

→ Reply

coderfool

4 years ago, # |

→ Reply

4 years ago, # ^ |

← Rev. 2 →

same happened with me.... becauses of which i was only able to do problem A :( but after it i learnt a new thing and never going to do this mistake again

→ Reply

notexpertcoder

4 years ago, # ^ |

+10

stop making unnecessary memes

→ Reply

yotin

4 years ago, # |

+53

CaseForces :)

→ Reply

Abhay_123

4 years ago, # |

Hi, please tell me why I am getting runtime error in it. https://mirror.codeforces.com/contest/1370/submission/84441745

→ Reply

akt_114

4 years ago, # ^ |

Kindly mention the question for which you are seeking help.

→ Reply

Abhay_123

4 years ago, # ^ |

Problem B

→ Reply

Mani

4 years ago, # ^ |

problem has memory limit of 256Mb, you are getting MLE, try creating the array only once globally

→ Reply

Mani

4 years ago, # |

can someone plz explain editorial solution of E

→ Reply

mihirarora

4 years ago, # |

+13

This was kind of Mathsforces.. But liked the simplicity of problem statements and toughness of implementing them..

→ Reply

4 years ago, # |

← Rev. 2 →

Why I am getting RTE on this 84528459 submission on problem E? Upd: I get it

→ Reply

Odysseus96

4 years ago, # |

can anyone pls explain what does cur ^= 1; do???(code of problem D)

→ Reply

Hakiobo

4 years ago, # ^ |

← Rev. 2 →

It's cur = cur xor 1

They;re using cur as a boolean representing whether they can take the next number or not, as they cannot take consecutive numbers from the array in for the odd/even sub sequences. In this context, cur ^= 1 is just negating the current value of it.

→ Reply

Hakiobo

4 years ago, # |

+11

I have a non-binary search solution for D that instead uses Union-Find

Code: 84528808

Key idea: Iterate through the numbers smallest to largest, and soon as you can create a valid sequence for either the odd or even indices with the numbers so far, you have found your answer

Explanation:

First, sort a, but keep each number connected to it's original index Then go from smallest to largest on the number. For each number, get it's index in the original array. Check whether the numbers above/below it have been reached yet, and if they have, merge then current number into those groups. We can increase the length of a sequence possible if it does not merge with a group of odd size. (Each group is a sequence of sequential indices that have all already been considered)

Once we have a valid sequence that is long enough, our answer is the biggest number in a that we have examined.

Care needs to be taken with numbers near the beginning/end of the original array since the first number cannot be part of an even indexed sequence, and the last number cannot be part of one of the sequences depending on whether k is even or odd.

→ Reply

musafir_v

4 years ago, # ^ |

can you share you code, I came up with same idea but my solution didn't passed.

→ Reply

Omnis

4 years ago, # |

← Rev. 2 →

Here's an alternative $$$n\log(n)$$$ solution for D I found during the contest, but I'm stuck at a step, can anyone help?

The task can be reduced (using odd/even casework) to finding the subsequence $$$s$$$ of length $$$m$$$ of array $$$b$$$ which does not contain two consecutive elements from $$$b$$$, and has smallest maximum value among all such subsequences. This can be achieved by sorting the elements in $$$b$$$ in ascending order. Then, we iteratively add each element to a ordered list of "intervals". For example, if $$$b = [b_1, b_2, b_3, b_4, b_5]$$$, and the ascending order is $$$b_1, b_5, b_2, b_4, b_3$$$, then the list looks like:

$$$[(1, 1)]$$$ $$$[(1, 1), (5, 5)]$$$ $$$[(1, 2), (5, 5)]$$$ $$$[(1, 2), (4, 5)]$$$ $$$[(1, 5)]$$$

You can do these calculations by using a version of binary search on this list to find the right position. Then by tracking how the intervals change it is possible to determine what is the maximum length of a non-consecutive subsequence using only the numbers so far, and we stop when this is $\geq m$.

The problem is, it takes linear time to perform insertion/deletion operations on this list if implemented as a vector, which makes the overall runtime quadratic in $$$n$$$. Does anyone know of a data structure which can avoid this problem?

Edit: Found the comment above mine which uses Union-Find :)

→ Reply

pk_sinha53

4 years ago, # |

-13

Why there are N pairs of inputs in problem F1 and F2?

→ Reply

humbertoyusta

4 years ago, # |

+19

I have an alternative solution to E:

Lets define a new string a as follows: we delete all indexes such that si = ti, and in the remaining ones we append si at the end of a.

Then a looks like 001110.

We need to take subsequences like 01010101 or 101010, and delete them.

We can see that it can looks like a bracket sequence, but like 01 and 10 can't be deleted in the same operation, we will change each 01 by '(' ')' and each 10 by '[' ']' greedily.

So, now 0110 look like [](), 110010 like (())() and 00111100 like (())[[]].

We can delete any balaced subsequence of depth 1 which contains only () or [].

Then the optimal solution is just the sum of the depth of the strings formed by all '(' and ')', plus the depth of the string formed by '[' and ']', we can compute this easily with the classical algorithm used to check if a bracket sequence is balanced.

We can't do it in less operations, because in each operation we can reduce the depth of "()", or "[]" by at most 1.

→ Reply

sigma_g

4 years ago, # ^ |

I was thinking about the same approach in contest, but I could not figure out how to convert the given string into a valid bracket sequence? For example, the conversions which you mentioned "now 0110 look like [](), 110010 like (())() and 00111100 like (())[[]]." As you can see, sometimes you are putting ( and another times you are putting [. How do you make that decision?

→ Reply

Charis02

4 years ago, # ^ |

← Rev. 2 →

+21

You can do it greedily. Basically, you can maintain a counter, and add 1 whenever you encounter a 0, add 1 to the counter, and whenever you encounter a 0, do counter--. This means that whenever the counter is positive, we will have the [] type of brackets (it is not optimal to have both at the same time). Whenever it is negative we will have the () type. So, the answer would be max(counter) — min(counter), because we want the maximum depth of [] and also the max depth of () (which is negative so we have a — sign).

I solved it with this idea during the contest here.

It turns out this is exactly the same as taking the absolute maximum subarray sum, as the editorial.

→ Reply

humbertoyusta

4 years ago, # ^ |

I just do the following, maintain two counters, one for 01 and one for 10, when i found a 1, check if i had a 0 non-matched previously, and put a ')', else put a '[', similarly when i found a 0, check if there is a 1 non-matched previously, put a ']', else put a '('. The prove of this greedy is non trivial, but it can be reduced to subarray of maximal absolute sum like Charis02 says above.

→ Reply

Imtiaz1710

4 years ago, # |

Can anyone explain problem c for value 54? How it will be "Ashishgup"?

→ Reply

4 years ago, # ^ |

54, 6, 2, 1. 54 = 2 * 27. So keep only 1 odd number (3) in 27. FF will have no choice other than taking that. Then take a 1.

→ Reply

code_warrior

4 years ago, # |

Can anyone explain why should we use binary search in problem D! I have read the tutorial again and again and still not been able to understand why should binary search works fine here ? How can we say that the problem is monotonic (the necessary condition for using binary search)?

→ Reply

void.abyss

4 years ago, # ^ |

← Rev. 2 →

Let $$$p$$$ be our answer. Now, let $$$can(x)$$$ be a function that will give us whether our answer can be $$$\leq{x}$$$.

Now notice that for values $$$\geq{p}$$$ our function will give us true value, for values $$$<{p}$$$ it will give us false. That's why it is monotonic. I hope you understand.

→ Reply

YPK

4 years ago, # |

Whenever there is "Determine the winner of the game if both of them play optimally." for me it sucks.

→ Reply

dickings

4 years ago, # |

Can anyone prove that We can ignore all the indices where si=ti as it is never optimal to include those indices in a rotation. in E.

→ Reply

vipul73921

4 years ago, # |

Ashishgup, in problem E, i have tried the approach of first finding longest occurring of 0101 or 1010 pattern in mismatched string. But I am getting wrong ans in pretest 10. Can anyone help me figure out what am i doing wrong?

Here is my submission for problem E. 84505487

→ Reply

4 years ago, # |

← Rev. 2 →

Codeforces Round #651

→ Reply

4 years ago, # ^ |

Great tutorial! Next time, i suggest you to improve your upload video quality. At least at 720p:) Thx

→ Reply

4 years ago, # ^ |

surely

→ Reply

code_aryan123

4 years ago, # ^ |

Bro , I love your editorials...!

→ Reply

n1colai

4 years ago, # |

← Rev. 2 →

Deleted

→ Reply

cis_pie

4 years ago, # |

Can someone explain how can we solve D using dp strategy?

→ Reply

AbhishekAg

4 years ago, # |

+15

Binary search: ruining careers since 1962.

→ Reply

helewrer3

4 years ago, # |

Nice problem D!

I did not know that binary search could be utilized like this, was really informative. Thanks for the problem!

→ Reply

18ucs134

4 years ago, # |

Can anyone explain me in problem D solution why we are taking odd and even indices of original array while we have to take indices of new subsequence of length k.

→ Reply

kalzor

4 years ago, # |

← Rev. 2 →

In problem D,can't we apply Binary Search on the range of min to max elements of the array rather than 1 to 1e9?Will it give correct or wrong answer.Can anyone please clear this up for me?

→ Reply

towrist

4 years ago, # ^ |

You can use that too, since all possible answers are actually the elements of the array. But why bother. But it can be done.

→ Reply

tmstrixx

4 years ago, # |

Can anyone help me in F2 why it is giving WA https://mirror.codeforces.com/contest/1370/submission/84557344

→ Reply

arpitP

4 years ago, # |

← Rev. 2 →

#include<bits/stdc++.h>
using namespace std;
string game(int n,int c)
{
    if(n==1&&c==1)
    return "FastestFinger";
    if(n==1&&c==2)
    return "Ashishgup";
    if(n%2!=0&&c==1)
    return game(n/n,2);
    if(n%2!=0&&c==2)
    return game(n/n,1);
    if(n%2==0&&c==1)
    return game(n-1,2);
    if(n%2==0&&c==2)
    return game(n-1,1);
}
int main()
{
    int T,n,c;
    cin>>T;
    while(T--)
    {
        cin>>n;
        c=1;
        cout<<game(n,1)<<"\n";
    }
}

can pls someone tell me whats wrong with my code?

→ Reply

shubham107

4 years ago, # ^ |

When n is even you are letting the other player win by making n odd. Consider the case of n = 18. You could win by first dividing by 3.

→ Reply

kkdrummer

4 years ago, # |

Great Contest, u guys are making India Proud :))

→ Reply

AbhishekAg

4 years ago, # |

Getting TLE for this (problem E) on case 11......Can someone tell why?

→ Reply

coderz189

4 years ago, # |

In problem E "Now we can pick any 1 from this subarray and a −1 either from its left or right to reduce its sum by 1, thus completing the proof" How is this step equivalent to one operation?

→ Reply

VandanRogheliya

4 years ago, # ^ |

← Rev. 2 →

Let the index of 1 which we select be i and index of -1 outside the subarray be j.

Initially:

s[i] == 1
s[j] == 0
t[i] == 0 
t[j] == 1
a[i] == 1
a[j] == -1

We rotate indices i and j for string s. (Doing one operation)

Result:

s[i] == 0
s[j] == 1
t[i] == 0 
t[j] == 1
a[i] == 0
a[j] == 0

Hence, a[i] == 0 and a[j] == 0 because s[i] == t[i] and s[j] == t[j].

Now subarray sum has also been decreased by 1 because one of its 1 changed to 0.

→ Reply

crimsonred

4 years ago, # |

In F you can also root the tree at its centre which ensures the depth of the tree is at most $$$500$$$ and then do a binary search to find the farthest secret node from the root. The second part can be done by querying all nodes which are at a distance of at least $$$mid + 1$$$ and at most $$$high$$$ from the root. If the distance returned by the query is equal to the distance between the two secret nodes, the distance of the farthest secret node lies in $$$[mid + 1, high]$$$; otherwise, it lies in $$$[low, mid]$$$. Here $$$low, mid$$$ and $$$high$$$ are parameters in the binary search.

→ Reply

ManavJ07

4 years ago, # |

The binary search in F2 should be from dis/2 to min(*max_element(dis_tree,dis_tree+N),dis). Because there can be a case where the dis is very small and only making low=(dis/2) would not be enough.

For example when dis=4 and depth=1000, then the low according to editorial will be 2 and high = 1000 thus the queries won't be decreased.

→ Reply

Tathagat_shah

4 years ago, # ^ |

← Rev. 2 →

UPD : Got it!

Thanks!

→ Reply

Maho

4 years ago, # |

why do we need task F1?Is there special solution for this problem?

→ Reply

naklecha

4 years ago, # |

Can someone please explain why this is failing the 10th test case? I am not able to figure out why. Newbie here. https://mirror.codeforces.com/contest/1370/submission/84574756

→ Reply

4 years ago, # ^ |

Always stick with meaning of variables and functions. Your check function say 1 if "not greater", so answer is less than equal. So actual value you output should be consistent to this. Perhaps there are other bugs, but fix this one first.

→ Reply

kkite_gk

4 years ago, # |

My solution for 1370E - Binary Subsequence Rotation was to add s[i] to the array incor for each s[i] != t[i]. Then break down the values in incor into chunks consisting only of '0's and '1's (e.g. 000, 11, 0). And then count the max length among all chunks(including the one that starts in the end of incor and ends in its beginning), and that would be the answer. (I can provide the proof for this)
But this solution fails on test 10: 84575875
Any ideas why?

→ Reply

saiyambharara

4 years ago, # ^ |

i also had the same approach. the solution fails for test 10

→ Reply

YakovPolykovsky

2 years ago, # ^ |

try this test: len = 22 ; s = 0000001111101111100001 ; t = not s ; after first rotation first and second chunks of 11111(5) and 11111(5) will be combined to 11111111(8) so the answer is 9

→ Reply

bipinpathak

4 years ago, # |

← Rev. 2 →

Here's my approach for E

For each operation we would like to build a subsequence made up of alternatives 1's and 0's which are out of their position so that all of them can be corrected in a single move.
So we will be searching for alternative 1's and 0's (which are out of their place) to form a subsequence.
We are interested in knowing the number of operations, so we will keep a count of "up" and "down" which correspond to number of subsequences we have initialized which need 0->1 and 1->0 as their next element respectively.(s[i]->t[i])
Whenever we need to make 1->0 we will decrement "down" and increment "up" (also check down>0 before decrementing). And vice versa for 0->1.
At the end sum of up and down will be our answer.

Link for the code

→ Reply

Gagandeep98

4 years ago, # |

Can someone please explain the thought process and intuition behind problem E?

→ Reply

Whiplash99

4 years ago, # ^ |

← Rev. 3 →

Refer to my code.

Brief explanation:

We need to convert $$$s$$$ to $$$t$$$. To do this, we are allowed to take any subsequence, and rotate it. We need to find the minimum number of such rotation steps needed to convert $$$s$$$ to $$$t$$$.

First of all, for it to be possible to convert $$$s$$$ to $$$t$$$, they should have the same number of $$$1$$$ s and $$$0$$$ s. So check this.

The positions where $$$s[i]=t[i]$$$ don't need to be touched. Now, let's look at the positions where $$$s[i]\ne t[i]$$$. Consider the string: $$$1100$$$. If we rotate this, we get $$$0110$$$. Here, the second position remained $$$1$$$ even after the rotation. So it was useless to include it. We could have instead simply taken the first, third and fourth positions: $$$100$$$, to have the same effect: $$$010$$$. This can in turn be reduced to $$$10$$$ being converted to $$$01$$$.

Thus, for a move, we'll only take subsequences which have alternating $$$0$$$ s and $$$1$$$ s. The minimum number of moves required will be equal to the minimum number of such subsequences of alternating $$$0$$$ s and $$$1$$$ s that we can obtain.

To calculate this, we simply iterate over the positions where $$$s[i]\ne t[i]$$$. We keep a count of the number of running subsequences which shall now accept and $$$0$$$ and those which shall now accept a $$$1$$$. Note the the subsequences which shall now accept a $$$0$$$ had their last element as a $$$1$$$, and vice versa.

While iterating, if $$$s[i]=0$$$, then we shall attach it to a running subsequence, which had its last element as $$$1$$$. After this, this subsequence shall now have its last element as $$$0$$$, and it shall now only accept a $$$1$$$. This decreases the count of the number of running subsequences which accept $$$0$$$ by $$$1$$$, and increases the count of those which accept $$$1$$$ by $$$1$$$. If there are no subsequences which accept $$$0$$$, then we'll simply have to start a new subsequence from this element. The case where $$$s[i]=1$$$ is similar.

Finally, the answer will be the sum of the number of running subsequences which accept $$$0$$$ and those which accept $$$1$$$.

→ Reply

Gagandeep98

4 years ago, # ^ |

← Rev. 3 →

Thanks. One thing that I was missing to get was that we can attach other shorter length ones to the largest subsequence. Hence only largest pattern of the subsequence matters.

→ Reply

rmaa

4 years ago, # ^ |

Thanks for the explanation, but I'm still a little confused about what you're saying.

For example I can have the sequence of indices that are 01010 (so the indices expect 10101) but when rotated once it will be 00101 which isn't right. So isn't the condition that the strings that we're generating must be alternating AND also end on a different value from the one that it started on?

How would keeping track of the number of sequences that accept 0 and 1 take care of this necessary condition?

→ Reply

Whiplash99

4 years ago, # ^ |

That's a great question.

Actually, notice that we'll never get this type of subsequence. If we get $$$01010$$$ from $$$s$$$, it means that the corresponding positions at $$$t$$$ are $$$10101$$$. We have already checked that $$$s$$$ and $$$t$$$ have the same number of $$$1$$$ s and $$$0$$$ s. Thus, it means that they have the same number of unmatched $$$1$$$ s and $$$0$$$ s too. Thus, we'll always get even length subsequences. I don't know how to prove this, but it seems correct by intuition to me, as the number of $$$0$$$ s and $$$1$$$ s in $$$s$$$ and $$$t$$$ are same.

→ Reply

winter_summer

4 years ago, # ^ |

← Rev. 2 →

Thanks Whiplash99. 1.it's really helpful. 2. I would say better than editorial.:XD

→ Reply

shreyakjain

4 years ago, # |

the second test case of 1370 D is wrong. input : 4 3 1 2 3 4 output: 2

while one can choose subsequence as {2,1,3} giving minimum =1. Please reply fast.

→ Reply

ManavJ07

4 years ago, # ^ |

you cant shuffle. Subsequence means delete numbers without changing the order.

→ Reply

towrist

4 years ago, # |

← Rev. 5 →

In Problem E

How to rigorously prove that it is always optimal NEVER to take indices $$$i$$$ with $$$s[i]==t[i]$$$? I am struggling with the proof.

→ Reply

vezcraz

4 years ago, # |

Video Tutorial for E

→ Reply

rachit901

4 years ago, # |

To prove the greedy method of making a subsequence with target value x in Problem D. Lets prove for even indexes. 2 things to prove:-

If we are on an even index, push any number irrespective of its value to our sub-sequence for the next number. Let the array be a b c d e f. If our subsequence currently has a c, including d will be a c d + odd_subsequence(e f), excluding d will be a c e + odd_subsequence(f). Clearly the former is a better choice since we have a possibility to construct longer subsequence there.

If we are on an odd index, push the nearest number <=x to our subsequence as our next number. let the array a b c d e f g h. If our subsequence currently has a c d, if e <= x and f > x, it is obvious to push e f to our subsequence. Another case will be if e <= x & f <= x, should we think about omitting e ?
If we include e, the subsequence will be a c d e + even_subsequence(f g h), if we exclude e, the subsequence will be a c d f + even_subsequence(g h). Clearly the former is a better choice since we have a possibility to construct longer subsequence there.

→ Reply

Kognition

4 years ago, # |

← Rev. 3 →

There's another observation for problem F that may offer a solution in even fewer queries, but I'm having trouble finding a bound for its performance. Basically, the idea is that when you do a query during your binary search and find that the result when querying the layer $$$m$$$ is [ $$$v$$$, $$$x$$$] where $$$x > \ell$$$, not only do we know that the target node is higher up than $$$m$$$, we know that the ancestor $$$\frac12(x-\ell)$$$ levels up from $$$v$$$ is a node that is on the path, so we can adjust our lower bound as well!

Since the query answerer must minimize $$$x$$$, it seems like this should actually provide a nontrivial bound improvement, but I was having trouble proving anything or constructing a hard case. My code didn't actually AC until I put this optimization in, so I think my implementation was probably not great (I had the optimization of discarding the largest subtree), but it's possible that this offers a nontrivial optimization. I tried editing the editorial implementation but it still took 11 queries on some tests, and I'm not sure if this is due to implementation. Does anyone have any thoughts?

EDIT: hm, I don't think this offers any improvement since the target node could just be in the bottom layer, never utilizing the insight I described.

→ Reply

Sambhu98

4 years ago, # |

if a number is even and divisible by 4 then after dividing it by its greatest odd divisor it will be of form 2^x x>1 can anyone make me understand this, really not getting it , with proof will help..thanks in advance

→ Reply

Kognition

4 years ago, # ^ |

Consider some number like 360, which is $$$2^3\cdot 3^2 \cdot 5$$$. It is divisible by $$$4=2^2$$$. Now, how do you find its greatest odd divisor? Simple, just take out all the 2's. i.e. $$$3^2 \cdot 5 = 45$$$ must be the greatest divisor (why?). When we divide this number by the greatest odd divisor, that is the same as removing all the odd prime factors. What does that leave us with? Only the 2's. i.e. the number will be of the form $$$2^x$$$. Now, since it was divisible by 4, that means $$$x$$$ must be $$$\geq 2$$$, which is the same thing as saying $$$x > 1$$$.

→ Reply

Sambhu98

4 years ago, # ^ |

this explanation was really helpful , thank you, i should have thought in this way(^_^).

→ Reply

Prateek_Jakhar

4 years ago, # |

Can someone please explain to me why in Problem C, while checking for primes we are only checking divisibility up to 50000?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

it is because for all the numbers greater than 50000,u can observe that either the number cant be divisible or it is the number itself. For example consider 1000000000,among all its prime factors at least 1 of them come below 50000 and the other can be found out by dividing this factor from the number.Basically for checking primality,it is enough to go till root n.Hope it answers your question.

→ Reply

pranav.vinchurkar

4 years ago, # ^ |

Ideally it should be sqrt(10^9). 50000 is slightly more. (he should have taken the latter)

The max factor of a number is sqrt(n), thats why. No need to check after that.

→ Reply

4 years ago, # |

← Rev. 3 →

can someone tell how the check function works for the following test case in problem D? n=5 k=5 arr=4 11 6 10 5 and check of 10 is happening

→ Reply

4 years ago, # ^ |

You need to make two sequences for even and for odd. If "good" values on odd, you get 4 11 6 10 5. 4 6 5 are good so they are on odd positions. And for even positions you pick first number you cah get. that's why them 11 and 10 (even if 10 is good number). For even case you pick 4 6 10 5 you pick 4 and 10 on odd positions because you can use anything for them. And, you pick 6 and 5 because they're good and you want to make good on even positions in this sequence. Second sequence is shorter than k so it doesn't work, but first sequence is working, so function should return "yes" because you can make subsequence not exceeding 10.

→ Reply

4 years ago, # ^ |

but 10 sould be a part of it right?

→ Reply

4 years ago, # ^ |

"check of x is happening" in your words doesn't require subsequence to have x. it requre that cost is less or equal to x.

→ Reply

4 years ago, # ^ |

got it thank you

→ Reply

rohan_ardulous

4 years ago, # |

← Rev. 2 →

Can anyone help me with F1? 84662486. I don't get to know what is the problem in my code that is leading to failure on 9th tc of test set 5

→ Reply

4 years ago, # |

I need a help with a solution that I have of problem 1370F2 - The Hidden Pair (Hard Version). I understand the editorial and I know how it works. But I have a solution of my own, which I don't know why should fail. The idea is simple, and quite similar to the one in the editorial.

Let, the hidden nodes are $$$s$$$ and $$$t$$$. Their distance is $$$L$$$. So, let the path between $$$s$$$ and $$$t$$$ be $$$P(s,t)$$$, and $$$|P(s,t)|=L$$$.

QUERY First, query for all nodes, which will give one of the nodes on $$$P(s,t)$$$ and $$$L$$$. Let's call the node $$$x_1$$$.
Root the tree at $$$x_1$$$. Find all the nodes that are $$$min(L,maxDepth)$$$ distance away from $$$x_1$$$.
QUERY query over all these nodes. Here, I hope that a node $$$x_2$$$ is returned where $$$P(x_1,x_2)$$$ contains one of $$$s$$$ or $$$t$$$. Why do I hope that? Without loss of generality, let's say $$$P(x_1,x_2)$$$ contains $$$s$$$. Then $$$dis(s,x_2)+dis(t,x_2)$$$ will be equal to $$$2*dis(s,x_2)+L$$$. As we know $$$L$$$, we can know $$$dis(s,x_2)$$$ and get $$$s$$$ by following the path $$$P(x_2,x_1)$$$.
QUERY As we have found one of the nodes, clearly we can query over all the nodes that are $$$L$$$ distance away from it and find the other node. This will solve the problem in $$$3$$$ queries.

Now, the only thing I need to prove is that in step 3 or query 2, I really get a node $$$x_2$$$ such that $$$P(x_1,x_2)$$$ contains one of $$$s$$$ or $$$t$$$. Let's take the proof out of the context. All I need to know is that in an infinitely large tree, if a path $$$P$$$ consists of nodes $$$p_1, p_2, ...p_L$$$, is it possible to have a node $$$x$$$ which is $$$L$$$ distance away from $$$p_k ($$$ for every $$$1\leq k\leq L)$$$, have minimum $$$dis(p_1,x)+dis(p_L,x)$$$, but not have any of $$$p_1$$$ or $$$p_L$$$ on the path from $$$p_k$$$ to $$$x$$$? I find the idea really simple, and believe that it is correct. Can anyone show me the mistake (or the lack of it)?

→ Reply

Kognition

4 years ago, # ^ |

← Rev. 2 →

This is not correct. On your third query, $$$P(x_1, x_2)$$$ is not guaranteed to contain $$$s$$$ or $$$t$$$. Consider the tree rooted at vertex 1 given by

Where $$$s=4, t = 2$$$. You will query node $$$6$$$ and get vertex $$$3$$$ as a result. In general when you query a level if the resulting distance is not equal to $$$L$$$ you will only be able to gain information about a node that is on $$$P(s, t)$$$ not $$$s$$$ or $$$t$$$ themselves. This unfortunately does not result in a decrease in overall queries, either.

→ Reply

4 years ago, # ^ |

-8

Thanks. When you said, "This is not correct.", I think you mean that this is not correct in a finite tree. Because if the tree was infinite, $$$P(x_1,x_2)$$$ would definitely contain $$$s$$$ or $$$t$$$. In fact, I can prove it right now, just feeling lazy. Thanks again for finding the fault.

→ Reply

cgDude

4 years ago, # |

can someone help me why this code for problem E is exceeding its time limit even if its O(n) solution? https://mirror.codeforces.com/contest/1370/submission/84710589

→ Reply

4 years ago, # ^ |

The way of thinking should be following: if it's indeed O(n) then TL means infinite loop. Otherwise it's not O(n). So, check both: for infinite loop and for "is it really O(n)".

→ Reply

cgDude

4 years ago, # ^ |

It's giving correct results till test case 9 but in treat case 10 it's exceeding

→ Reply