When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

IgorI's blog

By IgorI, history, 3 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +232
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +57 Vote: I do not like it

Fast editorial!

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Thanks for the fast and well explained editorial!!XD

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

The editorial is seriously fast. Really nice work

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Really nice observation in D, thanks :)

»
3 years ago, # |
Rev. 5   Vote: I like it +5 Vote: I do not like it

where is div2 E?

UPD: Now available

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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?

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              That would be the minimum vertex cover.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                More like a minimum independent dominating set.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Note that: black and white are not symmetric!

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            Rev. 2   Vote: I like it +5 Vote: I do not like it

            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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Such an amazing contest. Love problems

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
              Rev. 2   Vote: I like it +3 Vote: I do not like it

              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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like 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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

where are the solution codes?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 square

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        give me a counter-example

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it -8 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    .

»
3 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Capture

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

Nvm it's not

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to become EXPERT now with ~800 rank.

»
3 years ago, # |
Rev. 3   Vote: I like it +44 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 8   Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B was the good one!

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

What is Div2 F actually asking?

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone Please explain me the approach of DIV2 D please

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +13 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    Nothing wrong with these numbers.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

How is this guy legendary grandmaster?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

103550283

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like it

    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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 4   Vote: I like it +16 Vote: I do not like it

      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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
3 years ago, # |
Rev. 5   Vote: I like it +3 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone knows why it shows that error? 103656147

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div1 B ,I am implementing the same logic as editorial but getting tle here is submission link 160036330

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How interesting problem 1470B — Strange Definition is!