Codeforces Round #694 Editorial

4 years ago, # |

Nice round and fast editorial :) The solutions are pretty elegant to me as well lol

→ Reply

1470D - Странное расселение

4 years ago, # |

If we simply color the graph with two colors, how is it garanteed that no two adjacent vertex get the same color? Which is not allowed, conforming to rule "Teachers should not live in houses, directly connected by a passage."

→ Reply

4 years ago, # ^ |

Two students can connect to each other (get the same color) as long as there is a teacher connecting both of them. This algorithm can only guarantee that no adjacent black nodes (teachers) will get the same color.

→ Reply

4 years ago, # ^ |

← Rev. 3 →

"...color alternating... We continue this process until there are no uncoloured vertices left. We claim that the set of black vertices is the answer."

So, if the result of that coloring is that two adjacent vertex are black, then it is not a solution.

So, how is that the answer?

Edit: Consider a circle of len 3: 1-2, 2-3, 3-1. If we start coloring vertex 1 with white, vertex 2 and 3 will get black, and are connected.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

You colour every connected node of a black node white, so this won't happen.

→ Reply

4 years ago, # ^ |

Ah, ok. I misunderstood the algorythm, we do not choose all which are connected to a white one, but only a single one.

"Then let's pick any uncoloured vertex that is connected to a white one, paint it black, and paint all its neighbours white."

→ Reply

4 years ago, # ^ |

Actually, I'm just curious, but what will the solution be if we had to minimise the number of teachers? Is there a completely different algorithm for that?

→ Reply

bhushanbaby

4 years ago, # ^ |

That would be the minimum vertex cover.

→ Reply

mtw

4 years ago, # ^ |

More like a minimum independent dominating set.

→ Reply

clyring

4 years ago, # ^ |

← Rev. 2 →

Not exactly: Consider a line graph with 6 vertices: Then the only minimum vertex cover is {2, 5}, but isn't a legal set of teachers because the resulting set of open passages would not leave the graph connected.

Edit: Oof: I misremembered and got dominating set/vertex cover backwards. Vertex cover is totally unrelated to this problem, and even independent dominating sets aren't quite right because of my example above.

→ Reply

izlyforever

4 years ago, # ^ |

Note that: black and white are not symmetric!

White points can be connected by a passage while black points(where teachers will live) not.

→ Reply

4 years ago, # ^ |

Consider a circle of len 3: 1-2, 2-3, 3-1. If we start coloring vertex 1 with white, vertex 2 and 3 will get black, and are connected.

→ Reply

4 years ago, # ^ |

We first starting colouring one black node, then BFS/DFS the remaining ones. If the node is connected to any black node, then we colour it white. Else, we colour it black.

→ Reply

a1000

4 years ago, # |

Can anyone tell me why is my solution for Div2B wrong? 103425670

→ Reply

4 years ago, # ^ |

4 2

4 6 8 9

In this test case answer is 45 and your code gives 49

The final array should be [4,6,8,9,2,2,3,3,4,4], and your code sums first four elements(sum = 27) and calls recursive with[2,2,3,3,4,4] where it sums all elements(sum2 = 18) but after that it calls recursive for [1,1,1,1] and adds extra 4 to total sum. Those four ones are not a part of solution.

→ Reply

a1000

4 years ago, # ^ |

Thank you, I fixed the code but now it gives TLE on TC5, is there any fix for this? 103499496

→ Reply

4 years ago, # ^ |

No, the complexity of that code is to big to pass test cases. Let say that you have n = 10^5, x = 2 and ai = 2^25, you can see now that when you pass the array the first time you will add 2 * 10^5 numbers to the end and they will all be 2^24, if you continue doing that at the end you will have 2^25 * 10^5 size of array filled with 1. That's about 3 * 10^12 numbers, and obviously to slow to fit in 1 second, and also to big to fit the memory limit. The intended solution is not to do what is written in task but to think of a faster way. I advise you to read the editorial solution for this problem and try to solve it that way.

→ Reply

Letscode_sundar

4 years ago, # ^ |

can you explain the editorial ? i can't understand it quite well

→ Reply

4 years ago, # ^ |

← Rev. 2 →

Notice that when you put number Ai at the end of array you will place Ai/x x times, so if you will add them to sum you will add all X of them(since if one is divisible by x, the other one is the same so it is also divisible by x) that means you will add x * (Ai/x) to your sum. So basically you will add some number Ai multiple times(one time for each further division by x). Now lets explain how to count how many times you add which number.

Lets divide every number with x until it is divisible by x. After you have done that you will get number Ai written in a form x^p * c, where p is some integer(the number of times you can divide Ai until it is no longer divisible by x) and c is that last number that is no longer divisible by x(so if x = 2 and current number is 12 you can write it as 2^2 * 3, basically meaning 12 is divisible by x two times, since exponent is 2). After that you have to find minimum value of p(also first one if there are more minimums) for all given inputs, lets say it's at some position K.

After finding the minimum value note that all integers before that K will be added to the sum p(K) + 2 times, and after position K(including K) will be added p(K) + 1 times. Why is that? Since p(K) is minimal number of times some number in array is divisible by x you will add all elements of array to sum exactly p(K)+1 times(1 time at beginning and p(k) times after each division). Now you can add all numbers before position K one more time since they are all divisible by x more times, and once you reach position K the number that is there will stop the process since it is no longer divisible by X.

This is not easy to explain as you can see but once you understand it it is actually quite easy. I hope the solution is more clear now. If it's still not clear I can try to explain it to more depth.

→ Reply

the_bilbo

4 years ago, # |

Such an amazing contest. Love problems

→ Reply

VVD4

3 years ago, # ^ |

Spoiler

→ Reply

4 years ago, # |

1470A - Странный день рождения I overcomplecated that problem, 103444635

But I still do not get the intuition of the editorial. "To determinate a cheapest gift, let's store the index of the last purchased gift." The cheapest gift of which ones is meant here, and how can we find that by index (of the previous one)?

And, how does the example with persons A and B profe that a greedy solution works/exists?

→ Reply

4 years ago, # ^ |

The example with persons A and B is not an example, but a proof, that the optimal solution does not contain a situation such that a person with higher k_i got a more expensive gift.

I don't know if proof of the correctness of the greedy approach is simple, I for sure, cannot formalize it. But I understand it intuitively. Essentially, by giving the cheapest gift to the person with the greatest k_i, you will be always as well off as in any other situation. Then, you have to repeat the process for the same set of gifts, minus the cheapest gift and the same set of persons, minus the person with the highest k_i

→ Reply

4 years ago, # ^ |

← Rev. 2 →

try to think like that. If you have no gift then you are forced to give money to everyone. Now, If we have a gift then the friend who asked for the larger amount of money should earn this gift. This gift is gone so repeat the process from the next gift. (they are already sorted)

→ Reply

4 years ago, # ^ |

"Let's sort guest in order of descending value $$$K_i$$$." So, the friend which can get the most different gifts first, then the next... and last one in the list is the friend that can get the least different gifts.

How does this garantee that the friend with a bigger price (its $$$C_{K_i}$$$ ) gets a gift before a friend with lower price?

→ Reply

4 years ago, # ^ |

you force him to take that gift because the array is sorted decreasing. check this maybe will be more clear for you

→ Reply

4 years ago, # ^ |

← Rev. 2 →

If the friends are sorted by $$$K_i$$$ desc then they are not sorted by $$$C_{K_i}$$$. What am I missing?

Edit: Ok, now I got it. Sorting by $$$K_i$$$ is the same as sorting by $$$C_{K_i}$$$, because $$$C$$$ is sorted ascending, as the staments states clearly. I solved for the case that $$$C$$$ is not sorted, which also works for a sorted input, but is more complecated.

→ Reply

Legend_of_Azkaban

4 years ago, # ^ |

wait... what! $$${C_K}_i$$$ was sorted? Oh... I didn't notice that too. That is exactly why I was also confused by the editorial.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

I am not sure why I did not noticed earlier. Maybe I considered it to be not sorted because it would be more interesting problem if C was not sorted. Or simply because to much details and words.

→ Reply

rananjay23

4 years ago, # ^ |

If we assign gifts with lowest prices to people with higher c values then for people with lower c values we can give them cash amount c. Thus by doing this we will avoid spending large amount money.

If we assign lowest price to people with lower c values , then for people with higher c value we need to spend large amount of money either as gift or cash.

For example , suppose c value is 1 10 and k values are 1 2 . From second way total amount will be 11 ,whereas from first way total amount will be 2.

→ Reply

4 years ago, # ^ |

Yes, thanks, now I got it. I did not realized that C is sorted, so sorting the friends by $$$K_i$$$ is the same order as sorting them by $$$C_{K_i}$$$

My solution also works for unsorted $$$C$$$, and is therefore more cumbersome.

→ Reply

sergei_popov

4 years ago, # |

+20

Does anyone else feel Div 2 F easier then Div 2 D today. The questions were nice today, enjoyed it.

→ Reply

4 years ago, # ^ |

Didn't even read F, got stuck on D and for way too long. The (simple in hindsight) observations took me too long and ultimately I ran out of time, trying to think of how to find a solution in O(nlogA)... which admittedly, I am still searching for, and the editorial mentions it's "simple". Alright then, keep your secrets haha.

It probably is simple though. Apparently I just had one of them bad days.

→ Reply

sergei_popov

4 years ago, # ^ |

The first observation is x.y is a square. The more important one I feel is the following.

Spoiler

Since we want to find squares any prime number raised to an even power(looking at the maximal power possible) that divides a number in our array(say ai) is as good as not a factor of the number ai. But if its raised to an odd power we know that any adjacent number we choose for it should also have to be divisible by an odd power of the same prime. So all that matters is whether the prime that divides ai has its power as an even or odd number. The other observation is that for queries with seconds >= 1 the answer is the same.

→ Reply

GoatTamer

4 years ago, # ^ |

To get the mod 2 power replacement as given in the editorial, we divide x by the largest square that divides it. To get the largest square that divides each number we can use a sieve-like precomputation once which takes O(AlogA).

→ Reply

4 years ago, # ^ |

Oh, now this strikes a bell.

So what you are suggesting, is to find the largest square that divides every number in the range, then replace every number in the array by itself, divided by that largest square divisor, and we will be left by the product of primes (with exponent equal to 1), which we are looking for. Darn, simple and elegant.

Then, let's say we are given x and y. Then let x' be x divided by its largest square divisor, similarly define y'. Then, x is adjacent to y if and only if x' = y'. Did I get it right? Brilliant. (And well in the range of my abilities, but oh well...)

→ Reply

amurto

4 years ago, # ^ |

← Rev. 2 →

Can you explain the process. I tried precomputing all perfect squares in range [1..1e6]. But then finding the largest perfect square for any number should still take root(n) complexity right? Since there are 1e3 perfect squares in the range and I don't think we can binary search.

→ Reply

GoatTamer

4 years ago, # ^ |

We use a sieve. Loop over all the squares from smallest to largest. For each square s we loop over all its multiples j and set largest square factor of j = s. Its a sieve but instead of considering primes we consider squares. The complexity would be $$$ A/1^2 + A/2^2 + A/3^2 + ... = O(A) $$$

I earlier said it was AlogA but then I remembered that sum of inverse of squares = pi^2/6.

→ Reply

alwyn

4 years ago, # ^ |

← Rev. 2 →

I precompute the lowest prime factor for each $$$a_i$$$ (similiar to Sieve of Eratosthenes), then factorization can be done in $$$O(log_{a_i})$$$ by repeatedly dividing $$$a_i$$$ by its lowest prime factor (I think drayc's method is faster though).

103630714 (vector<int> lpf(N + 1))

→ Reply

Mokut

4 years ago, # |

1470B — you wrote __ "b- the total number of elements with a class of odd size or with the class equal to 1"

perhaps you meant total number of elements with a class of even size?

→ Reply

Mangooste

4 years ago, # ^ |

+11

You're right. We mean "a class of even size". It will be fixed soon.

→ Reply

ram2012k

4 years ago, # |

Any reason Why i am having TLE for problem 1471 C https://mirror.codeforces.com/contest/1471/submission/103443196

→ Reply

timreizin

4 years ago, # ^ |

← Rev. 2 →

You are not using fast io. ios_base::sync_with_stdio(false); cin.tie(0);

→ Reply

Mangooste

4 years ago, # ^ |

← Rev. 2 →

+22

The input is quite large, you should insert


ios::sync_with_stdio(false);
cin.tie(nullptr);

at the start of your main. Replacing endl by '\n' can also optimize your code.

→ Reply

4 years ago, # ^ |

cin.tie(0); cout.tie(0); also helps. One of them does next to nothing but the other one has a significant impact as well, although will make it so that your input flows to the console at the moment that the program comes to an end, which means it's rather bad for debugging. I never remember which one is which.

→ Reply

WizardMan

4 years ago, # |

where are the solution codes?

→ Reply

chandanagrawal23

4 years ago, # |

can anyone explain : (x*y) / gcd(x,y)² which means that numbers x and y are adjacent if and only if x⋅y is a perfect square.

we have to check whether [ (x*y) / gcd(x,y)² ] is perfect square

→ Reply

4 years ago, # ^ |

-6

Note k = x*y => (k^2/gcd(x,y)^2) = (k/gcd(x,y))^2 and thats a perfect square

→ Reply

4 years ago, # ^ |

← Rev. 2 →

What you wrote is true for any x and y. You essentially wrote that LCM(x,y)^2 is a perfect square.

→ Reply

4 years ago, # ^ |

give me a counter-example

→ Reply

4 years ago, # ^ |

← Rev. 2 →

There is no counterexample because this works for all x and y.

What you wrote: if k=x*y, then (k/gcd(x,y))^2 is a perfect square. It doesn't even matter what k is. You have written a tautology.

Edit: nevermind, it does matter what k is. But as long as k = x*y, then k/gcd(x,y) = lcm(x,y) is a whole number, so that squared is a perfect square. Still a tautology.

→ Reply

4 years ago, # ^ |

-8

your first comment was "what you wrote is not true for any x and y" .

→ Reply

4 years ago, # ^ |

It seems we have fallen victim to a minor misunderstanding. I wrote "what you wrote IS TRUE for any x and y".

Which, in that case, says nothing about x and y themselves, when the goal is to determine whether they are adjacent.

→ Reply

4 years ago, # ^ |

The editorial mentions, that LCM(a,b) = a*b/GCD(a,b). This is a well known fact. It is easy to prove, I will assume I do not need to.

What is LCM(a,b)/GCD(a,b) then? Well that is equal to (a*b/GCD(a,b))/GCD(a,b) = (a*b)/GCD(a,b)^2

And the numbers a and b are adjacent if and only if that number is a perfect square, so (a*b)/GCD(a,b)^2 = X^2 for some integer X. Which means, that a*b = GCD(a,b)^2 * X^2 for some X. Now that is true if and only if a*b is a perfect square itself. Then, we can divide that perfect square by GCD(a,b)^2 and we will receive another perfect square, denoted by X^2.

→ Reply

karary

4 years ago, # ^ |

← Rev. 2 →

→ Reply

Dan4Life

4 years ago, # |

← Rev. 2 →

→ Reply

jiggly_puff

4 years ago, # |

← Rev. 2 →

Can someone help figure out why my solution for A is failing on pretest 3, I followed the same approach as in the editorial ? https://mirror.codeforces.com/contest/1471/submission/103403583

→ Reply

rahulmysuru7

4 years ago, # ^ |

Int overflow issues. use long long instead of int to get ac

→ Reply

Lolboyyyy

4 years ago, # |

← Rev. 2 →

-11

Nvm it's not

→ Reply

pratikraut0000

4 years ago, # |

Hope to become EXPERT now with ~800 rank.

→ Reply

1024mb

4 years ago, # ^ |

nice try)

→ Reply

pratikraut0000

4 years ago, # ^ |

Yeah :(

→ Reply

Rafbill

4 years ago, # |

← Rev. 3 →

+44

Here's a short explanation of one of the alternative solutions for div1E. I think that it is simpler than the editorial's solution (or at least more standard).

The problem can be reduced to the following problem. Given a directed acyclic graph equipped with an ordering of the outgoing edges at each vertex, find the $$$w$$$-th path fast from the source to some sinks. Without additional information, there is only a naive algorithm in time $$$O(nc)$$$.

In this problem the vertices of the graph are pairs $$$(i,j)$$$, where $$$i \le c$$$ is the remaining money to pay for reverses, and $$$j < n$$$ is the position in the permutation. The edges are of the form $$$(i,j) \to (i-k,j+k+1)$$$ for $$$k \le i$$$, and correspond to reversing $$$j$$$..$$$j+k$$$. The sinks are the pairs $$$(i,n-1)$$$. The ordering on the edges is determined by the input permutation, so that the induced ordering on the paths corresponds exactly to the lexicographic ordering on the reachable permutations. We can use the construction of the graph to speedup the naive algorithm.

We can partition the edges into heavy edges ($$$(i,j) \to (i,j+1)$$$) and light edges (all of the other edges). A path can contain at most $$$c$$$ light edges, and each vertex has at most $$$1$$$ heavy outgoing edge. Then we can use path compression for the heavy edges, and use that to answer each query in time $$$O(c \log n + c^2)$$$.

→ Reply

john.pl

4 years ago, # |

Am I the only one who think that problem Div-1B/Div-2D could be divided in easy and hard version, with and without queries? I wasn't even close to solve the problem without changes in the array :'(

→ Reply

4 years ago, # ^ |

← Rev. 2 →

No, not really. It's literally the same problem with one extra observation. I solved the 'easy' version, but not the hard even though there wasn't much of a difference.

→ Reply

FULL SOLUTION FOR YESTERDAY'S PROBLEM

4 years ago, # |

← Rev. 8 →

+11

D2D/D1B is very similar to this problem https://mirror.codeforces.com/contest/1246/problem/B

Other than that, very good contest.

EDIT: Since this comment is downvoted I'd like you to tell me why they aren't similar? Change k for 2 in the other problem and it becomes 80% of this task. I even solved like that and got correct answer for each 0 query, because I thought there was one case only.

Maybe I am missing something, let me know so.

EDIT 2: Here's a solution that does the exact same thing I and many others did — https://mirror.codeforces.com/contest/1471/submission/103429802 The only difference, precalculate primes and the added case when query >= 1. Authors proposed a slightly extended version of the above mentioned problem.

EDIT 3: C'mon boys, what's wrong with you? Can someone point me what's wrong with the approach??? Just because I'm blue ain't mean I'm bad at recognizing problems.

EDIT 4: Literally no point in downvoting you, but hey upvote shitposts, quality stuff ain't matter.

EDIT 5: Here are sample solutions I've created:

PARTIAL SOLUTION FOR YESTERDAY'S PROBLEM

SOLUTION FOR THE ORIGINAL PROBLEM

→ Reply

_mentalist_

4 years ago, # ^ |

How to get such intuitions of taking prime factorisation helps in such problems. I was not even close to this approach before. Can anyone please help? Thanks in advance :)

→ Reply

4 years ago, # ^ |

Get a bit better at math and changing formulas up. In this problem the key observation was to realize that lcm(a, b) = a * b / gcd(a, b). Then you can see that a * b must be a perfect square. When is it a perfect square? When each factor appears an even number of times. Thus we keep a map of occurrences of lists of factors which occur an odd number of times. Something along those lines is also written in the editorial.

Back to the key part — practice math — get a decent book on it, preferably something more advanced than your usual schoolbook. There's many free resources online.

→ Reply

_mentalist_

4 years ago, # ^ |

Thanks, Dude will look into it :)

→ Reply

ItsEZ

4 years ago, # |

B was the good one!

→ Reply

_xOrZ

4 years ago, # |

+14

What is Div2 F actually asking?

→ Reply

DiSTRuCtO

4 years ago, # |

← Rev. 2 →

Can anyone Please explain me the approach of DIV2 D please

→ Reply

s_aaron

4 years ago, # ^ |

using ceil function is causing the issue, You can get the lower end by using (v[i]+k-1)/k.

→ Reply

4 years ago, # ^ |

(My Approach. Different from Editorial)

Let LCM/GCD = (x*x). Therefore LCM = (GCD)*(x*x).

We know LCM=(product)/GCD.

By solving these equation we get-> Product of Numbers =(GCD*GCD)*(x*x).

Hence we can say that if the product of numbers is a perfect square then the numbers are adjacent.

For this brute force will give TLE so we need to think smarter. Every number X can be represented as->

X = k * (x*x); where 'k' is integer.

Therefore for 2 numbers to have a product perfect square, this k value must be equal for both them.Refer to this article for better understanding

Maintain count of number for each value of k. When w==0 print the answer corresponding to the value of k with most numbers.

For remaining numbers we observe that if the number of elements corresponding to the particular value of k is even, then the resultant product is always going to be a perfect square. Similarly if the number of elements corresponding to particular value of k is odd then we can never increase the size of the given set and the extra constant will always be multiplied odd number of times.

103476026 My Accepted Submission After the contest.

Hope it helped :)

→ Reply

jpratik15

4 years ago, # ^ |

Please can you explain the case when number of elements in a set is odd?

→ Reply

4 years ago, # ^ |

For example:

Let the initial Array is: 12 3 20 5 80 1

After the 0th second the array will look like this: 36,36,8000,8000,8000,1

8000 = (4*4) * (10*10) * 5; k=5 is the constant for 8000.

Now this case 8000 appears 3 times(odd number of times). All the three occurrences of 8000 are adjacent to each each other. Therefore in the next iteration/second all the occurrences of 8000 will be replaced with 8000*8000*8000.

When we multiply this way the constant 'k' which is 5, is also multiplied 3 times which makes it impossible to get a perfect square even after infinite iterations.

(5*5*5) can never generate a perfect square.

Consider the case if we had only two 8000. Then the numbers will be replaced with 8000*8000, which is a perfect square.

Hope it helps :).

→ Reply

AbdullaNurFaisal

4 years ago, # ^ |

Can anyone explain the even case? I don't seem to understand why the whole even group becomes 1. Can't 2 perfectly square numbers be "adjacent" to themselves?

→ Reply

4 years ago, # ^ |

We claim that after the 0th second or the first iteration, the set with even number of elements will always form a perfect square. Therefore in the next iteration all such the groups with even number of elements will combine to form single group.

Yes, you are right I forgot to mention if an element is already a perfect square.

I have used this logic->

(it.S % 2 == 0 || it.F==1)

here it.F is 'k' and it.S is count of elements with a particular 'k' value. For perfect squares k=1.

→ Reply

4 years ago, # ^ |

a^b is a perfect square if 'b' is even or 'a' itself is a perfect square. I meant this.

→ Reply

AbdullaNurFaisal

4 years ago, # ^ |

Hi, sorry I still don't understand. Let me demonstrate what confuses me,

Trying this case: 4 4

Here, the power 2 in 4 is even for both numbers. They themselves are perfect squares. Now according to the problem, 2 numbers x and y are adjacent if (x * y) is a perfect square. In our case (4 * 4) = 16, it is a perfect square.

I understand the fact that grouping all numbers that have even prime powers lead to a single group consisting perfect squares. Those numbers becoming = 1? What does this mean? It means they become 1 group or they become actual the value 1?

4 4 should become 16 16 after multiplying themselves as 4 and 4 are adjacent. Then 16 and 16 should do the same and become larger. So the answer should be 2? I don't understand how 1 is coming here.

→ Reply

Refer to this article for more info

4 years ago, # ^ |

it.F is the 'k' value I talked about earlier.

any number can be represented as:

x= k * (X*X)

example: 8000= 5*(40*40);

for perfect square this 'k' is 1.

That's why i am equating it to 1.

That map consists of count of 'k'.

→ Reply

strawhatdragon

4 years ago, # |

How to go about solving problems? Like once I read a problem statement I am sometimes stuck on how to proceed. even for problem A. Any tips?

→ Reply

4 years ago, # ^ |

Practice, if problems are hard try solving some easier problems from problemset, try competing in Div 3 contest. You can see the rating of all problems and search for those which you can solve and than as you progress you will be able to solve harder problems.

→ Reply

4 years ago, # |

← Rev. 2 →

Fun solution for Div2 E / Div1 C. Ask 300 random questions. After

if n < 600 just check every position for solution keeping in mind that position of answer is the one which still has k cards and following person has less than k cards.
if n >= 600 check every 300th position for 1st number which is not k. After finding the number check pos + 300 if there is number smaller than k the solution is one of 300 positions after pos + 300. If the number at pos + 300 is greater than k then solution is between pos and pos + 300. In both cases we use maximum of (300 + 1e5 / 300 + 300) < 1000 questions.

→ Reply

toniskrijelj

3 years ago, # ^ |

Sounds great, but you failed system tests so I assume that approach is wrong?

→ Reply

3 years ago, # ^ |

← Rev. 2 →

+13

Solved it with this idea after the contest, during the contest I had a bug.

→ Reply

4 years ago, # |

https://www.geeksforgeeks.org/count-of-pairs-in-an-array-whose-product-is-a-perfect-square I found a useful article on geeks for geeks for Div 2 D. I was to solve D after taking hint from this. Hope it Helps :)

→ Reply

wargang

4 years ago, # ^ |

thank u so much bro! u saved me so much effort

→ Reply

92anurag

4 years ago, # |

In div-2 F / div-1 D

Can someone please tell me why java version gives TLE whereas c++ is getting accepted. (i am new to java)

Java version

C++ version

→ Reply

Othmane

4 years ago, # |

Can anyone please tell me how we can represent each element $$$a_{i}$$$ as $$$x^{b_i}⋅c_i$$$ in Div2-B

→ Reply

4 years ago, # ^ |

If a = 12 and x = 2 you can represent a as 2^2 * 3 where b = 2 and c = 3, you always want to get b as high as possible so you can divide a by x until it is not divisible anymore let say you did it b times. You can see that now you transformed a into x^b * c where c is not divisible by x.

→ Reply

PurpleCrayon

4 years ago, # |

← Rev. 2 →

I didn't notice that the array $$$c$$$ in problem Div2 C/Div1 A was sorted. Though this was my fault for not noticing it, I think it would be easier for a lot of contestants if the setters wrote something like "The array $$$c$$$ is sorted in nondecreasing order" in bold. During the contest, I solved the problem for the general case using a segment tree. Here's my accepted submission: 103434787

→ Reply

4 years ago, # ^ |

Me too. The whole look and feel of the problem is that C shouldn't be sorted. I'm pretty sure that in an earlier version of the problem C wasn't sorted, and that sorting was added later to make the problem easier, maybe to fit it better between B and D.

→ Reply

Harshit_90

4 years ago, # ^ |

Actually i am not quite sure that this will get accepted...as the question asks about no more than 2 turns ie upto 2 turns are allowed.......so after repeating your algo one more time the TC will become (n+m)*(n+m)*(n+m) and as n+m sums to 2000 .....i think it will give TLE......

i am replying here because of quota of 2 distinct recipients per hour......srry for that.............it would be easy for me if u give me our email id or something

→ Reply

4 years ago, # ^ |

I sent you another message.

→ Reply

HackerMonk

4 years ago, # |

+15

Div1-C is really interesting! Many people passed with different solutions. I wrote a very complicated algorithm that passed in the end, but the provided solution turned out to be very neat. : )

→ Reply

ankan2526

4 years ago, # |

← Rev. 3 →

is the statement of A correct? 'which means that we divide each element by x, round it up to the nearest integer, and sum up the resulting values.' rounding 4/3 will give 1 right?

→ Reply

4 years ago, # ^ |

It should be $$$2$$$ because that $$$1<\frac{4}{3}<2$$$.

→ Reply

ankan2526

4 years ago, # ^ |

but 4/3=1.333, and the nearest integer is 1...

→ Reply

4 years ago, # ^ |

The statement says "round it up" which means that we find the nearest integer that is bigger than it.(it's just the same as the function ceil()) And $$$\lceil \rceil$$$ also means that.

→ Reply

ankan2526

4 years ago, # ^ |

ohh, got it. Thankyou!!

→ Reply

uttaran_das

4 years ago, # |

Can anyone tell me, what is wrong with this solution for problem Strange List? 103415511

→ Reply

denkora

4 years ago, # |

← Rev. 2 →

In B-StrangeDefinition, you say numbers are adjacent iff x*y is perfect square. How about numbers 15 & 135.

LCM(15,135) = 135 
GCD(15,135)= 15,
LCM(15,135)/GCD(15,135) = 9 = 3^2

Can anyone elaborate on this?

→ Reply

4 years ago, # ^ |

15 * 135 = 15 * 15 * 9 = 15 * 3 * 15 * 3 = 45 * 45

Nothing wrong with these numbers.

→ Reply

believebelieve

4 years ago, # |

← Rev. 2 →

div2-D/div1-B : Can someone explain to me why this code gives TLE as the approach is the same as editorial. Do I need to change the code in implementation?

→ Reply

4 years ago, # ^ |

It gives TLE because you use the function sieve() many times. The time complexity of the function is around $$$O(\sqrt{N}log log\sqrt{N})$$$ ($$$N=1000005$$$ and this is not very exact) and it will be used $$$t$$$ times ($$$t \le 3 \cdot 10^5$$$).

You should use the function exactly once in the beginning. If you still don't know how to do that, you can click here to have a look at the AC submission.

→ Reply

believebelieve

4 years ago, # ^ |

Thanks a lot! I had to insert sieve() in the main function, not in every test case. Due to that silly mistake, it cost me too much time at debugging. Again thanks a lot.

→ Reply

harpaljadeja

4 years ago, # |

← Rev. 3 →

How is this guy legendary grandmaster?

→ Reply

4 years ago, # ^ |

This is the New Year gift from Codeforces. You can read this article to get more information.

By the way, I am also using that.

→ Reply

Mokut

4 years ago, # |

← Rev. 3 →

PROBLEM DIV2D/ DIV 1B
Does anyone see why this code gets WA3?

103550283

→ Reply

khaufnak

4 years ago, # |

Can somebody help why does Div1B, Div2D TLEs here: https://mirror.codeforces.com/contest/1470/submission/103549863?

→ Reply

khaufnak

4 years ago, # ^ |

← Rev. 2 →

Oh well, I switched to a fast writer implementation and it passed.

→ Reply

Gary2005

4 years ago, # |

Can someone explain how the binary search work for Div1 C.

→ Reply

codephilic

4 years ago, # ^ |

← Rev. 2 →

+22

On ith second second , the number of cards at index (imposter+i) becomes greater than k and number of cards at index (imposter-i) becomes less than k. The number of cards at index (imposter) is always k.

So, at ith second,number of cards in range [imposter-i,imposter] are <=k and cards in range [imposter, imposter+i ] are >=k

After 2*root(n) turns, you finally have the index 'i' whose number of cards will be greater than k, so, you can apply binary search in range ['i'-root(n) , 'i'] to find index with k cards

→ Reply

Gary2005

4 years ago, # ^ |

Thank you

→ Reply

rananjay23

4 years ago, # ^ |

← Rev. 4 →

+16

Gary2005 and codephilic , It's not necessary that impostor will be present in ['i'-root(n),'i'] , because with each query the game is also played , thus the impostor could be also present at position less than 'i'-root(n) since we have asked 2*root(n) queries .

We can do binary search in ['i'-(n-3)/2],'i'] if n is odd , ['i'-(n-2)/2,'i'] if n is even (left limit will wrap around if it goes less than 1).Here 'i' is any position with value >k. I found the range by going through lot of simulations.

submission

→ Reply

codephilic

4 years ago, # ^ |

We are querying every index at the interval of root(n)

so if impostor is present at any index less than [i-root(n)], we will detect that while querying index [i-root(n)]

so, i guess [i-root(n), i] is sufficient.

→ Reply

rananjay23

4 years ago, # ^ |

Yeah you are right , i understood now . Thanks for clarification .

→ Reply

Gary2005

4 years ago, # ^ |

I didn't use any binary search and $$$3\sqrt n$$$ queries can also pass.

→ Reply

PurpleCrayon

4 years ago, # |

+10

For Problem E (Div. 1 C), no binary search is needed. You can query random indices until you hit one that is not equal to $$$k$$$. If that element is less than $$$k$$$, just keep incrementing your index until you hit an element equal to $$$k$$$. If it is greater than $$$k$$$, just keep decrementing your index until you hit an element equal to $$$k$$$. That element is your answer. The number of queries it takes is approximately $$$2*r$$$, where $$$r$$$ is the number of indices it takes to hit an element not equal to $$$k$$$ when randomly picking indices. One thing to note is that the probably of failing is reasonably high, but if you use the trick mentioned here, it should pass comfortably. Here is my accepted submission: 103489905

→ Reply

sirius

4 years ago, # |

← Rev. 5 →

for problem div1B/div2D, can someone explain why one of my solution is giving TLE and the other is getting ACed when the only difference between them is declaring the variables, maps, and vectors as long longs and integers.. TLE Solution , Accepted solution

→ Reply

ShubhamAvasthi

4 years ago, # ^ |

Check this blog.

→ Reply

sunhero

4 years ago, # ^ |

Because, you are using endl instead of '\n'. endl does '\n', and then cout.flush(). Because of that, you are getting TLE.

→ Reply

ShubhamAvasthi

4 years ago, # |

← Rev. 2 →

What does the following mean in the editorial for Div. 1 C — Strange Shuffle?

"Now let's prove that the number of cards that players $$$p+1,p+2,…,n,1,…p−1$$$ have is not increasing. Again, if we consider a single step: $$$b_{i+1}=⌈\frac{a_i}{2}⌉+⌊\frac{a_{i+2}}{2}⌋≥⌈\frac{a_{i−1}}{2}⌉+⌊\frac{a_{i+1}}{2}⌋=b_i$$$."

→ Reply

ShubhamAvasthi

4 years ago, # ^ |

← Rev. 3 →

I figured out what this means. Initially, $$$a_{i-1} \le a_i \le a_{i+1} \le a_{i+2}$$$, since $$$a_{i-1} = a_i = a_{i+1} = a_{i+2}$$$ $$$\forall i$$$ such that $$$p \not\in \{ i-1, i, i+1, i+2 \} $$$.

Now, if at any step, $$$a_{i-1} \le a_i \le a_{i+1} \le a_{i+2}$$$ holds, then $$$b_{i+1}=⌈\frac{a_i}{2}⌉+⌊\frac{a_{i+2}}{2}⌋≥⌈\frac{a_{i−1}}{2}⌉+⌊\frac{a_{i+1}}{2}⌋=b_i$$$ holds as well, i.e. $$$b_i \le b_{i+1}$$$.

From this argument, we can conclude that the array will remain non-increasing at every step at such indices.

→ Reply

Sam_Hack_King

4 years ago, # |

Hi everyone.

In Question A For my code, in test 4 it is giving

wrong output format Expected integer, but "1e+010" found

How to handle this? Someone, please tell...

→ Reply

4 years ago, # ^ |

← Rev. 3 →

1e+010 means that your code calculated 10^10. You can handle such issue by using long long int instead of double or if you are using double you can write the following

cout.precision(0); cout << fixed << ans;

This will not print any decimal digits and fix the output to write exact number. It would be helpful if you could provide your code.

→ Reply

xherbq

4 years ago, # |

anyone knows why it shows that error? 103656147

→ Reply

https://mirror.codeforces.com/blog/entry/86464?#comment-744951

4 years ago, # ^ |

← Rev. 2 →

you can see in this comment I explained the error both for Time and Memory limit

→ Reply

born_in_autumn

4 years ago, # |

In div2B,Can anyone tell me what's wrong with me? I use a pair to save the number of times each number appears, but I can't pass the fifth example 103698706

→ Reply