Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | tourist | 3764 |

2 | slime | 3592 |

3 | maroonrk | 3535 |

4 | Benq | 3513 |

5 | jiangly | 3509 |

6 | ecnerwala | 3508 |

7 | MiracleFaFa | 3466 |

8 | ksun48 | 3452 |

9 | Um_nik | 3426 |

10 | greenheadstrange | 3393 |

# | User | Contrib. |
---|---|---|

1 | awoo | 192 |

2 | -is-this-fft- | 191 |

3 | Monogon | 183 |

4 | YouKn0wWho | 182 |

5 | Um_nik | 181 |

6 | antontrygubO_o | 173 |

7 | maroonrk | 168 |

8 | SecondThread | 165 |

8 | errorgorn | 165 |

10 | kostka | 164 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Round #694 (Div. 1)

Tutorial of Codeforces Round #694 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/29/2022 10:54:20 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Fast editorial!

Thanks for the fast and well explained editorial!!XD

The editorial is seriously fast. Really nice work

What a great problems with interesting solutions! I want more rounds like this

Really nice observation in D, thanks :)

where is div2 E?

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

1470D - Strange Housing

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."

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.

"...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.

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

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."

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?

That would be the minimum vertex cover.

More like a minimum independent dominating set.

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.

Note that: black and white are not symmetric!

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

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.

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.

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

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.

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

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.

Thank you I understand now!

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

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.

Such an amazing contest. Love problems

Spoiler... jhoot bol rha hai

1470A - Strange Birthday Party 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?

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

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)

"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?

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

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.

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.

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.

This helped me. Thanks!

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.

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.

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

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.

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

SpoilerTo 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).

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...)

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.

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.

amazing brother.

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)`

)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?

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

I think it should have been "a class of odd size" because, after 1st operation, we either have a class of integer "1" or classes of different integers with odd sizes.

Too fast

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

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

The input is quite large, you should insert

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

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.

where are the solution codes?

can anyone explain : (x*y) / gcd(x,y)

^{2}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)

^{2}] is perfect squareNote k = x*y => (k^2/gcd(x,y)^2) = (k/gcd(x,y))^2 and thats a perfect square

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

give me a counter-example

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.

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

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.

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.

.

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://codeforces.com/contest/1471/submission/103403583

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

I think its unfair that I got 0 after getting everything right in the first question only due to this issue... I feel codeforces should give partial marks on such questions based on number of test cases passed

Nvm it's not

Hope to become EXPERT now with ~800 rank.

nice try)

Yeah :(

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)$$$.

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 :'(

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.

D2D/D1B is very similar to this problem https://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://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:

FULL SOLUTION FOR YESTERDAY'S PROBLEM

PARTIAL SOLUTION FOR YESTERDAY'S PROBLEM

SOLUTION FOR THE ORIGINAL PROBLEM

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 :)

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.

Thanks, Dude will look into it :)

I implemented Solution 2 written in editorial of Div2B during contest and got TLE.(Time constraint was too strict for java).Later after contest I changed my Pair class variables to primitive from Object class and it passed the solution fml.

TLE ~~~~~ static class Pair{ Long first; Integer second; } ~~~~~

Accepted ~~~~~ static class Pair{ long first; int second; } ~~~~~

B was the good one!

What is Div2 F actually asking?

Can anyone Please explain me the approach of DIV2 D please

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

(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 :)

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

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 :).

Thanks mate!

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?

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.

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

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.

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.

Refer to this article for more info

That map consists of count of 'k'.

I looked at your solution and I understand now. Thanks a lot. I had gotten confused because of the wording in the editorial and everywhere else. I had gone through the geeksforgeeks article too yet I was confused about the 1 thing. But after looking at your solution, I understand that you were just referring to grouping them to 1 set instead of the actual value 1. Again thanks for the help.

Also the fact that you can say, k = 1 too. Yeah really confused me.

I'll try to write down what I understood for the problem Strange Definition,

2 numbers x and y are "adjacent" if (x * y) it'self is a perfect square, because It is well know that,

lcm(x, y) * gcd(x, y) = x * y

Now,

lcm(x,y) = (x * y) / gcd(x, y)

=> lcm(x, y) / gcd(x, y) = (x * y) / gcd(x, y) ^ 2

So, basically if the left side is a squared number, then right side is a squared number. So, surely (x * y) is also a squared number, as taking the square root of the right side will take away the exponent of gcd(x ,y) and only (x, y) will be left.

Now, we have proved that, (x * y) has to be squared for x, y to be "adjacent"..

Now, we can look at the fact that, all numbers that have each prime factor even no. of times are perfectly squared. So, those numbers are already adjacent to each other.

i.e. 16 = 2 * 2 * 2 * 2

We, can also observe that for numbers which have prime factors with odd power, we can just discard the primes that have even powers in them as factors and only work with the primes that have odd powers to make them adjacent to other numbers.

i.e. 6 = 2 * 3 150 = 2 * 3 * 5 * 5

If we multiply these 2 numbers, we get 2 * 2 * 3 * 3 * 5 * 5 , this has each prime factor even no. of times and it is a perfectly squared number.

So, in order to pair a number with 150, we just needed to check the primes which have odd powers i.e. 2 and 3, as the even powered primes don't make 2 numbers not perfectly squared after multiplication.

So, we can simply calculate a value k such that k = all primes that have odd powers multiplied together.

For 6, k = 6 For 150, k = 6

So, we can group numbers with same k together as "adjacent numbers" because if 2 numbers are multiplied in these same groups (i.e. 6 and 150) they form a perfectly squared number (x * y had to be perfectly squared for them to be adjacent)

Now, If a group of adjacent numbers has even elements then what happens? i.e. a group with same k = 6, {6, 294, 3750, 150} This group has even number of elements (4 elements)

Okay, these are adjacent, after 1 second the numbers multiply with each other and become another group but now all of these elements are perfectly squared. after 1 second, {992250000, 992250000, 992250000, 992250000}

Okay, shouldn't they be grouping with the numbers that had primes with even powers (1, 16 and so on if they are present in our test case) as these numbers are adjacent to those??

Yes, we group them together to make a large set which consists of these newly obtained perfectly squared numbers and the old ones if we had any.

So, what if this group didn't have even elements, i.e if this group was {6, 294, 150} Then, they would be adjacent, and after the multiplication, {264600, 264600, 264600}

They are adjacent to themselves but they aren't perfectly squared. Why? well in each of them 6 = 2 * 3 150 = 2 * 3 * 5 * 5 294 = 2 * 3 * 7 * 7

When we multiplied 264600 = 2 * 2 * 2 * 3 * 3 * 3 * 5 * 5 * 7 * 7

So these prime powers again became odd. So, for this group after 1 second and infinitely many seconds, the group size will remain the same. Only merging happens if the group size was even and we had other numbers which were perfectly squared (i.e. 1, 16 and so on) in our test case and those merged groups in the subsequent seconds keep forming groups of the same size too but only their values increase because when perfectly squared numbers multiply among each other, all the prime powers should stay even. i.e. if we multiply 4, 16, 25 we get, 2 * 2 * 2 * 2 * 2 * 2 * 5 * 5, which is a perfectly squared number and the powers are even.

So, for our queries, if query = 0 sec, we print the largest adjacent number group as we did not do any merges. if query >= 1 sec, we print the largest adjacent number group after potential merges.

Submission link: https://codeforces.com/contest/1471/submission/103869598

Very nice explanation

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?

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.

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

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

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

thanks for Fast editorial!

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 :)

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

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

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

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.

Thank you very much! When I posted the comment, I thought that the approach you suggested was inefficient, but I just realized that it's only $$$O(log(n))$$$, so I guess it's doable. Thanks again :).

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

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.

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

I sent you another message.

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. : )

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?

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

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

The statement says "round it

up" which means that we find the nearest integer that isbiggerthan it.(it's just the same as the function`ceil()`

) And $$$\lceil \rceil$$$ also means that.ohh, got it. Thankyou!!

This is my first time participating in a contest after a really long break. I feel dumb when my submission for Problem A get WA 103451162 because of int overflow, I just needed to change the var into long long 103499657 and it got accepted TT

103500380. Can someone give me a hint why I got TLE on my submission for Problem 1470A-Strange Birthday Party? The complexity of my code is O(nLogn) since I sort the array k (guest number), and then iterate through the guest O(n). Cmiiw.

can plz someone explain this testcase of problem A Div 2 10 999999999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000'

What should be ans and why?

The min a/c to me should be ceil(sum/k) and max is sum(ceil(a[i]/k)) so max should be 20 and min 11 right??

can someone explain B 1471B - Strange List ? I am not able to understand from editorial .

Can anyone tell me, what is wrong with this solution for problem

Strange List? 103415511VIDEO TUTORIAL FOR DIVISION 2 PROBLEM B AND C Link of problem B :https://www.youtube.com/watch?v=e7N8N1GlSOc Link of problem C : https://www.youtube.com/watch?v=rj1A1N7yVkM HOPE YOU GUYS WILL ENJOY THE VIDEO !!!

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

Can anyone elaborate on this?

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

Nothing wrong with these numbers.

why is Strange Birthday Party has time complexity m(logn)? It should be n(logn) cause we sorting the guests array.

I dont know why my code is showing time limit exceeded at test case 10.

https://codeforces.com/contest/1471/submission/103524378

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?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.

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.How is this guy legendary grandmaster?

This is

the New Year giftfrom Codeforces. You can read this article to get more information.By the way, I am also using that.

Great contest d is really a nice one div2

Can you explain ,cannot understand the editorial?

Great editorial! Can anyone please tell what is p in the 1470B- Strange Definition problem?

Got it! p stands for any prime number.

PROBLEM DIV2D/ DIV 1B

Does anyone see why this code gets WA3?

103550283

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

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

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

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

Thank you

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

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.

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

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

I don't even understand the 1st tutorial. can someone explain me that....

you are rounding the value up which means that you gain from 0 to 0.9999... from it, when you sum all of the numbers you perform only one rounding (so you get the minimum value), however if you round every single one you will get this "bonus" n times where n is how many numbers there are (and you get the maximum value)

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

if anyone is facing any difficulty in understanding Div2 Prob D. Kindly refer to the link below. https://www.youtube.com/watch?v=x0TCsPjI0YM

Feedbacks are highly appreciated

thanks bhai

can any1 pls help why this submission for problem D is giving TLE ?? :( submission link : https://codeforces.com/contest/1471/submission/103565030

if anyone is facing any difficulty in understanding Div2 Prob D. Kindly refer to the link below. https://www.youtube.com/watch?v=x0TCsPjI0YM

Feedbacks are highly appreciated.

check this bro!

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

Check this blog.

Because, you are using

`endl`

instead of`'\n'`

.`endl`

does`'\n'`

, and then`cout.flush()`

. Because of that, you are getting TLE.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$$$."

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.

can someone explain problem C question.

Hi everyone.

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

wrong output format Expected integer, but "1e+010" foundHow to handle this? Someone, please tell...

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.

For qn 1470B — Strange defination , I am getting a WA in test #3 for 11092 number as '2' expected '1' found.

I am unable to find any mistakes in my code , even after cross-checking with the editorial.

https://codeforces.com/contest/1471/submission/103651400

here is my submission.

Any help is appreciated.

peace.

I wrote a comment above. You can look at this if you want.

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

I looked at your submission, I think the issue is with your loop primes[i] * primes[i] <= n.

Thanks,

oopsi , that one got me.

anyone knows why it shows that error? 103656147

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

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

I didn't quite understand what question D is asking. Here are the things I understood : 1) Houses are nodes in which we can have a teacher or a student. 2) A passage is described as an edge between two houses. 3) An open passage should have only Teachers living in two houses connecting it. What I didn't understand : 1) " All passages between two houses ... " — Here, does all passages mean all the possible paths from one node to other or just the one edge which connects the two nodes (if it is present)? 2) " Teachers should not live in houses, directly connected by a passage " — What exactly does this mean? Which kind of passage (open/close)? What does the term "directly connected by a passage" mean?

Yes I have the same doubt, does passage imply an "edge" or "the whole path" between a pair of vertices? If it is an "edge", I think the writer should've not used "directly" in the third point. It gives an impression that a passage is "the whole path"

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

I think when you are making a new pair, your second parameter should be x times larger than the current second parameter. You just put x everywhere but when you divide with x second time the second parameter should be x^2.

I successfully passed all the tests, thanks for your answer!

1471D: Let alphax be the maximum possible integer such that p^alphax divides x, and alphay be the maximum possible integer such that p^alphay divides y. Then x⋅y is perfect square if and only if αx+αy is even

Can some one explain how it work?

12 * 3 = 36

12 = 2^2 * 3 | αx = 2

3 = 3^1 | αy = 1

αx+αy = 2+1 = 3 — NOT EVEN!!

Hi, I think you should be thinking about it like this,

36 = 3 * 3 * 2 * 2

12 = 3 * 2 * 2

As the powers of 2 in both numbers is even just ignore them as if they existed they wouldn't cause issues with the number being perfectly squared if we multiplied 36 * 12

Now, ignoring those 2s,

36 = 3 * 3 12 = 3 If we multiplied we would get 3 * 3 * 3, this would never lead to a perfectly squared number as the power of 3 would be odd.

So, for x and y, we just want 2 numbers that have primes consisting only even powers or they have primes with odd powers but both numbers should have the same primes in this case (for the odd exponent to become even for forming a perfect square number). i.e. 36 = 3 * 2 * 2 27 = 3 * 3 * 3 36 * 27 = 3 * 2 * 2 * 3 * 3 * 3 = 3 even no. of times, 2 even no. of times

I wrote a comment above regarding this problem, you can look at it if you want, https://codeforces.com/blog/entry/86464?#comment-746403

Many thanks. I figured out and solved this beautiful task. I just removed all the squares from all the numbers.

For the Problem A , I am getting wrong answer on test case 4 .... here is my submission Your text to link here...

In Strange housing, In the case of two neighboring white-colored nodes, isn't that condition is violated? Like if the graph is a cycle of 5 nodes in the form of a pentagon then however you put colors two neighboring white nodes will appear?

With reference to the problem named strange list I have passed all the cases but the last case is showing memory limit exceed ,kindly guide me to pass the same.

How would one go about implementing a DP solution to Div2C / Div1A ??

Can someone prove or disprove the following claim about Div1C:

After exactly $$$n$$$ questions, the table looks exactly the same as in the beginning?

To be honest, I did not try many examples, but it really seems intuitive, though I cannot prove it. It's easy to prove that the table is periodic since it is finite and the sum of numbers is invariant, and by arguments given in the solution, the period is always larger than $$$\frac{n}{2}$$$. I also proved that the period is always smaller than $$$k^{\frac{n}{2}}$$$, but it's still far away from the solution.

Can someone tell me what does p(alhpa) stand for in div1_B(Strange Definition)? I'm really confused.

Can anyone tell me the dp solution + explanation of problem 1470A : Strange Birthday Party