IgorI's blog

By IgorI, history, 12 days 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
  • +222
  • Vote: I do not like it

»
12 days ago, # |
  Vote: I like it +57 Vote: I do not like it

Fast editorial!

»
12 days ago, # |
  Vote: I like it +26 Vote: I do not like it

Thanks for the fast and well explained editorial!!XD

»
12 days ago, # |
  Vote: I like it +20 Vote: I do not like it

The editorial is seriously fast. Really nice work

»
12 days 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

»
12 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Really nice observation in D, thanks :)

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

where is div2 E?

UPD: Now available

»
12 days 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

»
12 days 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."

  • »
    »
    12 days 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.

    • »
      »
      »
      12 days 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.

      • »
        »
        »
        »
        12 days 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.

        • »
          »
          »
          »
          »
          12 days 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."

          • »
            »
            »
            »
            »
            »
            12 days 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?

            • »
              »
              »
              »
              »
              »
              »
              12 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              That would be the minimum vertex cover.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                More like a minimum independent dominating set.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 days 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.

  • »
    »
    12 days 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.

    • »
      »
      »
      12 days 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.

      • »
        »
        »
        »
        12 days 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.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 days 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.

    • »
      »
      »
      12 days 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

      • »
        »
        »
        »
        11 days 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.

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you I understand now!

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            10 days 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.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Such an amazing contest. Love problems

»
12 days 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?

  • »
    »
    12 days 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

  • »
    »
    12 days 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)

    • »
      »
      »
      12 days 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?

      • »
        »
        »
        »
        12 days 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

        • »
          »
          »
          »
          »
          12 days 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.

          • »
            »
            »
            »
            »
            »
            12 days 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.

            • »
              »
              »
              »
              »
              »
              »
              12 days 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.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This helped me. Thanks!

  • »
    »
    12 days 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.

    • »
      »
      »
      12 days 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.

»
12 days 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.

  • »
    »
    12 days 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.

    • »
      »
      »
      12 days 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

    • »
      »
      »
      12 days 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).

      • »
        »
        »
        »
        12 days 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...)

      • »
        »
        »
        »
        12 days 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.

        • »
          »
          »
          »
          »
          12 days 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.

        • »
          »
          »
          »
          »
          10 days 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))

»
12 days 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?

  • »
    »
    12 days 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.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
12 days ago, # |
  Vote: I like it -8 Vote: I do not like it

Too fast

»
12 days 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

  • »
    »
    12 days 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);

  • »
    »
    12 days 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.

    • »
      »
      »
      12 days 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.

»
12 days ago, # |
  Vote: I like it +4 Vote: I do not like it

where are the solution codes?

»
12 days 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

  • »
    »
    12 days 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

    • »
      »
      »
      12 days 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.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        give me a counter-example

        • »
          »
          »
          »
          »
          12 days 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.

          • »
            »
            »
            »
            »
            »
            12 days 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" .

            • »
              »
              »
              »
              »
              »
              »
              12 days 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.

  • »
    »
    12 days 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.

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

    .

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

Capture

»
12 days 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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      11 days ago, # ^ |
      Rev. 2   Vote: I like it -11 Vote: I do not like it

      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

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

Nvm it's not

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to become EXPERT now with ~800 rank.

»
12 days 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)$$$.

»
12 days 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 :'(

  • »
    »
    12 days 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.

»
12 days 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

  • »
    »
    12 days 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 :)

    • »
      »
      »
      12 days 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.

»
12 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like 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; } ~~~~~

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

B was the good one!

»
12 days ago, # |
  Vote: I like it +14 Vote: I do not like it

What is Div2 F actually asking?

»
12 days 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

  • »
    »
    12 days 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.

  • »
    »
    12 days 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 :)

    • »
      »
      »
      11 days 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?

      • »
        »
        »
        »
        11 days 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 :).

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks mate!

        • »
          »
          »
          »
          »
          11 days 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?

          • »
            »
            »
            »
            »
            »
            11 days 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.

          • »
            »
            »
            »
            »
            »
            11 days 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.

            • »
              »
              »
              »
              »
              »
              »
              11 days 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                10 days 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'.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

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

                  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

»
12 days 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?

  • »
    »
    12 days 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.

»
12 days 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.
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for Fast editorial!

»
12 days 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 :)

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
12 days 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

»
12 days 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

  • »
    »
    12 days 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.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
12 days 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

  • »
    »
    11 days 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.

    • »
      »
      »
      11 days 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

»
12 days 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. : )

»
12 days 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?

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

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

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        12 days 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.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days 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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

VIDEO 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 !!!

»
11 days 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?

  • »
    »
    11 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days 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?

  • »
    »
    11 days 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.

    • »
      »
      »
      11 days 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.

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

How is this guy legendary grandmaster?

  • »
    »
    11 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest d is really a nice one div2

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain ,cannot understand the editorial?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days 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

»
11 days 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?

  • »
    »
    11 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 days 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

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you

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

      MrGary 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

      • »
        »
        »
        »
        10 days 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.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        10 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
11 days 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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days 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

»
11 days 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$$$."

  • »
    »
    10 days 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.

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

can someone explain problem C question.

»
10 days 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...

  • »
    »
    10 days 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.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone knows why it shows that error? 103656147

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

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?

»
9 days 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

  • »
    »
    9 days 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.

»
9 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 days 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?