Codeforces Round #694 Editorial

4 года назад, # |

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

→ Ответить

4 года назад, # |

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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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?

→ Ответить

bhushanbaby

4 года назад, # ^ |

That would be the minimum vertex cover.

→ Ответить

mtw

4 года назад, # ^ |

More like a minimum independent dominating set.

→ Ответить

clyring

4 года назад, # ^ |

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

→ Ответить

izlyforever

4 года назад, # ^ |

Note that: black and white are not symmetric!

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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

a1000

4 года назад, # |

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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

a1000

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

Letscode_sundar

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

the_bilbo

4 года назад, # |

Such an amazing contest. Love problems

→ Ответить

VVD4

3 года назад, # ^ |

Spoiler

→ Ответить

4 года назад, # |

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?

→ Ответить

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

Legend_of_Azkaban

4 года назад, # ^ |

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.

→ Ответить

4 года назад, # ^ |

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

→ Ответить

rananjay23

4 года назад, # ^ |

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.

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

sergei_popov

4 года назад, # |

+20

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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

sergei_popov

4 года назад, # ^ |

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.

→ Ответить

GoatTamer

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

amurto

4 года назад, # ^ |

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

→ Ответить

GoatTamer

4 года назад, # ^ |

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.

→ Ответить

alwyn

4 года назад, # ^ |

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

→ Ответить

Mokut

4 года назад, # |

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?

→ Ответить

Mangooste

4 года назад, # ^ |

+11

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

→ Ответить

ram2012k

4 года назад, # |

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

→ Ответить

timreizin

4 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

Mangooste

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

WizardMan

4 года назад, # |

where are the solution codes?

→ Ответить

chandanagrawal23

4 года назад, # |

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

→ Ответить

4 года назад, # ^ |

-6

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

→ Ответить

4 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

4 года назад, # ^ |

give me a counter-example

→ Ответить

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

-8

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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

karary

4 года назад, # ^ |

← Rev. 2 →

→ Ответить

Dan4Life

4 года назад, # |

← Rev. 2 →

→ Ответить

jiggly_puff

4 года назад, # |

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

→ Ответить

rahulmysuru7

4 года назад, # ^ |

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

→ Ответить

Lolboyyyy

4 года назад, # |

← Rev. 2 →

-11

Nvm it's not

→ Ответить

pratikraut0000

4 года назад, # |

Hope to become EXPERT now with ~800 rank.

→ Ответить

1024mb

4 года назад, # ^ |

nice try)

→ Ответить

pratikraut0000

4 года назад, # ^ |

Yeah :(

→ Ответить

Rafbill

4 года назад, # |

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

→ Ответить

john.pl

4 года назад, # |

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

FULL SOLUTION FOR YESTERDAY'S PROBLEM

4 года назад, # |

← Rev. 8 →

+11

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

→ Ответить

_mentalist_

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

_mentalist_

4 года назад, # ^ |

Thanks, Dude will look into it :)

→ Ответить

ItsEZ

4 года назад, # |

B was the good one!

→ Ответить

_xOrZ

4 года назад, # |

+14

What is Div2 F actually asking?

→ Ответить

DiSTRuCtO

4 года назад, # |

← Rev. 2 →

Can anyone Please explain me the approach of DIV2 D please

→ Ответить

s_aaron

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

jpratik15

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

AbdullaNurFaisal

4 года назад, # ^ |

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?

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

4 года назад, # ^ |

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

→ Ответить

AbdullaNurFaisal

4 года назад, # ^ |

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.

→ Ответить

Refer to this article for more info

4 года назад, # ^ |

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

→ Ответить

strawhatdragon

4 года назад, # |

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?

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

4 года назад, # |

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

→ Ответить

toniskrijelj

3 года назад, # ^ |

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

→ Ответить

3 года назад, # ^ |

← Rev. 2 →

+13

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

→ Ответить

4 года назад, # |

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

→ Ответить

wargang

4 года назад, # ^ |

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

→ Ответить

92anurag

4 года назад, # |

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

→ Ответить

Othmane

4 года назад, # |

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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

PurpleCrayon

4 года назад, # |

← 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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

Harshit_90

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

I sent you another message.

→ Ответить

HackerMonk

4 года назад, # |

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

→ Ответить

ankan2526

4 года назад, # |

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

ankan2526

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

ankan2526

4 года назад, # ^ |

ohh, got it. Thankyou!!

→ Ответить

uttaran_das

4 года назад, # |

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

→ Ответить

denkora

4 года назад, # |

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

→ Ответить

4 года назад, # ^ |

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

Nothing wrong with these numbers.

→ Ответить

believebelieve

4 года назад, # |

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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

believebelieve

4 года назад, # ^ |

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.

→ Ответить

harpaljadeja

4 года назад, # |

← Rev. 3 →

How is this guy legendary grandmaster?

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

Mokut

4 года назад, # |

← Rev. 3 →

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

103550283

→ Ответить

khaufnak

4 года назад, # |

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

→ Ответить

khaufnak

4 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

Gary2005

4 года назад, # |

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

→ Ответить

codephilic

4 года назад, # ^ |

← 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

→ Ответить

Gary2005

4 года назад, # ^ |

Thank you

→ Ответить

rananjay23

4 года назад, # ^ |

← 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

→ Ответить

codephilic

4 года назад, # ^ |

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.

→ Ответить

rananjay23

4 года назад, # ^ |

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

→ Ответить

Gary2005

4 года назад, # ^ |

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

→ Ответить

PurpleCrayon

4 года назад, # |

+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

→ Ответить

sirius

4 года назад, # |

← 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

→ Ответить

ShubhamAvasthi

4 года назад, # ^ |

Check this blog.

→ Ответить

sunhero

4 года назад, # ^ |

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

→ Ответить

ShubhamAvasthi

4 года назад, # |

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

→ Ответить

ShubhamAvasthi

4 года назад, # ^ |

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

→ Ответить

Sam_Hack_King

4 года назад, # |

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

xherbq

4 года назад, # |

anyone knows why it shows that error? 103656147

→ Ответить

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

4 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

born_in_autumn

4 года назад, # |

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

→ Ответить