mohammedehab2002's blog

By mohammedehab2002, 5 years ago, In English

1174A - Ehab Fails to Be Thanos

If all elements in the array are equal, there's no solution. Otherwise, sort the array. The sum of the second half will indeed be greater than that of the first half.

Another solution is to see if they already have different sums. If they do, print the array as it is. Otherwise, find any pair of different elements from different halves and swap them.

Code link: https://pastebin.com/FDXTuDdZ

1174B - Ehab Is an Odd Person

Notice that you can only swap 2 elements if they have different parities. If all elements in the array have the same parity, you can't do any swaps, and the answer will just be like the input. Otherwise, let's prove you can actually swap any pair of elements. Assume you want to swap 2 elements, $$$a$$$ and $$$b$$$, and they have the same parity. There must be a third element $$$c$$$ that has a different parity. Without loss of generality, assume the array is $$$[a,b,c]$$$. You'll do the following swaps:

  • Swap $$$a$$$ and $$$c$$$: $$$[c,b,a]$$$.
  • Swap $$$b$$$ and $$$c$$$: $$$[b,c,a]$$$.
  • Swap $$$a$$$ and $$$c$$$: $$$[b,a,c]$$$.

In other words, you'll use $$$c$$$ as an intermediate element to swap $$$a$$$ and $$$b$$$, and it'll return to its original position afterwards! Since you can swap any pair of elements, you can always sort the array, which is the lexicographically smallest permutation.

Code link: https://pastebin.com/xhqGXLiu

Time complexity: $$$O(nlog(n))$$$.

1174C - Ehab and a Special Coloring Problem

Let's call the maximum value in the array $$$max$$$. Let the number of primes less than or equal to $$$n$$$ be called $$$p$$$. Then, $$$max \ge p$$$. That's true because a distinct number must be assigned to each prime, since all primes are coprime to each other. Now if we can construct an answer wherein $$$max=p$$$, it'll be optimal. Let's first assign a distinct number to each prime. Then, assign to every composite number the same number as any of its prime divisors. This works because for any pair of numbers $$$(i,j)$$$, $$$i$$$ is given the same number of a divisor and so is $$$j$$$, so if they're coprime (don't share a divisor), they can't be given the same number!

Code link: https://pastebin.com/tDbgtnC8

Time complexity: $$$O(nlog(n))$$$.

1174D - Ehab and the Expected XOR Problem

The main idea is to build the prefix-xor of the array, not the array itself, then build the array from it. Let the prefix-xor array be called $$$b$$$. Now, $$$a_l \oplus a_{l+1} \dots \oplus a_r=b_{l-1} \oplus b_{r}$$$. Thus, the problem becomes: construct an array such that no pair of numbers has bitwise-xor sum equal to 0 or $$$x$$$, and its length should be maximal. Notice that "no pair of numbers has bitwise-xor sum equal to 0" simply means "you can't use the same number twice". If $$$x \ge 2^n$$$, no pair of numbers less than $$$2^n$$$ will have bitwise-xor sum equal to $$$x$$$, so you can just use all the numbers from 1 to $$$2^n-1$$$ in any order. Otherwise, you can think of the numbers forming pairs, where each pair consists of 2 numbers with bitwise-xor sum equal to $$$x$$$. From any pair, if you add one number to the array, you can't add the other. However, the pairs are independent from each other: your choice in one pair doesn't affect any other pair. Thus, you can just choose either number in any pair and add them in any order you want. After you construct $$$b$$$, you can construct $$$a$$$ using the formula: $$$a_i=b_i \oplus b_{i-1}$$$.

Code link: https://pastebin.com/0gCLC0BP

Time complexity: $$$O(2^n)$$$.

1174E - Ehab and the Expected GCD Problem

Let's call the permutations from the statement good. For starters, we'll try to find some characteristics of good permutations. Let's call the first element in a good permutation $$$s$$$. Then, $$$s$$$ must have the maximal possible number of prime divisors. Also, every time the $$$gcd$$$ changes as you move along prefixes, you must drop only one prime divisor from it. That way, we guarantee we have as many distinct $$$gcd$$$s as possible. Now, there are 2 important observations concerning $$$s$$$:

Observation #1: $$$s=2^x*3^y$$$ for some $$$x$$$ and $$$y$$$. In other words, only $$$2$$$ and $$$3$$$ can divide $$$s$$$. That's because if $$$s$$$ has some prime divisor $$$p$$$, you can divide it by $$$p$$$ and multiply it by $$$4$$$. That way, you'll have more prime divisors.

Observation #2: $$$y \le 1$$$. That's because if $$$s=2^x*3^y$$$, and $$$y \ge 2$$$, you can instead replace it with $$$2^{x+3}*3^{y-2}$$$ (divide it by $$$9$$$ and multiply it by $$$8$$$), and you'll have more prime divisors.

Now, we can create $$$dp[i][x][y]$$$, the number of ways to fill a good permutation up to index $$$i$$$ such that its $$$gcd$$$ is $$$2^x*3^y$$$. Let $$$f(x,y)=\lfloor \frac{n}{2^x*3^y} \rfloor$$$. It means the number of multiples of $$$2^x*3^y$$$ less than or equal to $$$n$$$. Here are the transitions:

If your permutation is filled until index $$$i$$$ and its $$$gcd$$$ is $$$2^x*3^y$$$, you can do one of the following $$$3$$$ things upon choosing $$$p_{i+1}$$$:

  • Add a multiple of $$$2^x*3^y$$$. That way, the $$$gcd$$$ won't change. There are $$$f(x,y)$$$ numbers you can add, but you already added $$$i$$$ of them, so: $$$dp[i+1][x][y]=dp[i+1][x][y]+dp[i][x][y]*(f(x,y)-i)$$$.

  • Reduce $$$x$$$ by $$$1$$$. To do that, you can add a multiple of $$$2^{x-1}*3^y$$$ that isn't a multiple of $$$2^x*3^y$$$, so: $$$dp[i+1][x-1][y]=dp[i+1][x-1][y]+dp[i][x][y]*(f(x-1,y)-f(x,y))$$$.

  • Reduce $$$y$$$ by $$$1$$$. To do that, you can add a multiple of $$$2^x*3^{y-1}$$$ that isn't a multiple of $$$2^x*3^y$$$, so: $$$dp[i+1][x][y-1]=dp[i+1][x][y-1]+dp[i][x][y]*(f(x,y-1)-f(x,y))$$$.

As for the base case, let $$$x=\lfloor log_2(n) \rfloor$$$. You can always start with $$$2^x$$$, so $$$dp[1][x][0]=1$$$. Also, if $$$2^{x-1}*3 \le n$$$, you can start with it, so $$$dp[1][x-1][1]=1$$$. The answer is $$$dp[n][0][0]$$$.

Code link: https://pastebin.com/N8FRN9sA

Time complexity: $$$O(nlog(n))$$$.

1174F - Ehab and the Big Finale

Let $$$dep_a$$$ be the depth of node $$$a$$$ and $$$sz_a$$$ be the size of the subtree of node $$$a$$$. First, we'll query the distance between node 1 and node $$$x$$$ to know $$$dep_x$$$. The idea in the problem is to maintain a "search scope", some nodes such that $$$x$$$ is one of them, and to try to narrow it down with queries. From this point, I'll describe two solutions:

HLD solution:

Assume that your search scope is the subtree of some node $$$u$$$ (initially, $$$u$$$=1). How can we narrow it down efficiently? I'll pause here to add some definitions. The heavy child of a node $$$a$$$ is the child that has the maximal subtree size. The heavy path of node $$$a$$$ is the path that starts with node $$$a$$$ and every time moves to the heavy child of the current node. Now back to our algorithm. Let's get the heavy path of node $$$u$$$. Assume its other endpoint is node $$$v$$$. We know that a prefix of this path contains ancestors of node $$$x$$$. Let the deepest node in the path that is an ancestor of node $$$x$$$ be node $$$y$$$ (the last node in this prefix). I'll now add a drawing to help you visualize the situation.

So, recapping, $$$u$$$ is the root of your search scope, $$$v$$$ is the endpoint of the heavy path starting from $$$u$$$, $$$x$$$ is the hidden node, and $$$y$$$ the last ancestor of $$$x$$$ in the heavy path. Notice that $$$y$$$ is $$$lca(x,v)$$$. Now, we know that $$$dist(x,v)=dep_x+dep_v-2*dep_y$$$. Since we know $$$dep_x$$$, and we know $$$dep_v$$$, we can query $$$dist(x,v)$$$ to find $$$dep_y$$$. Since all nodes in the path have different depths, that means we know $$$y$$$ itself!

Another way to find y

Now, if $$$dep_x=dep_y$$$, $$$x=y$$$, so we found the answer. Otherwise, we know, by definition, that $$$y$$$ is an ancestor of $$$x$$$, so it's safe to use the second query type. Let the answer be node $$$l$$$. We can repeat the algorithm with $$$u=l$$$! How long will this algorithm take? Note that $$$l$$$ can't be the heavy child of $$$y$$$ (because $$$y$$$ is the last ancestor of $$$x$$$ in the heavy path), so $$$sz_l \le \lfloor\frac{sz_y}{2} \rfloor$$$, since it's well-known that only the heavy child can break that condition. So with only 2 queries, we managed to cut down at least half of our search scope! So this algorithm does no more than $$$34$$$ queries (actually $$$32$$$ under these constraints, but that's just a small technicality).

Code link: https://pastebin.com/CM8QwdUf

Centroid decomposition solution:

As I said, assume we have a search scope. Let's get the centroid, $$$c$$$, of that search scope. If you don't know, the centroid is a node that, if removed, the tree will be broken down to components, and each component's size will be at most half the size of the original tree. Now, $$$c$$$ may and may not be an ancestor of $$$x$$$. How can we determine that? Let's query $$$dist(c,x)$$$. $$$c$$$ is an ancestor of $$$x$$$ if and only if $$$dep_c+dist(c,x)=dep_x$$$. Now, if $$$c$$$ is an ancestor of $$$x$$$, we can safely query the second node on the path between them. Let the answer be $$$s$$$, then its component will be the new search scope. What if $$$c$$$ isn't an ancestor of $$$x$$$? That means node $$$x$$$ can't be in the subtree of $$$c$$$, so it must be in the component of $$$c$$$'s parent. We'll make the component of $$$c$$$'s parent the new search scope! Every time, the size of our search scope is, at least, halved, so the solution does at most $$$36$$$ queries.

Code link: https://pastebin.com/hCNW5BfQ

  • Vote: I like it
  • +155
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have other approach for E, though editorial is well explained.

F i heard HLD first time, also don't know CD. what are they ?

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

    HLD — Heavy Light Decomposition CD — Centroid Decomposition

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

    I have submitted an O(n) solution for E using casework and simple counting principles. However, I think doing all the thinking required to get this solution functional is much harder than mindlessly typing a DP solution, so such an approach may not be so viable in contest unless O(nlogn) is too slow.

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

    I did E without dp. I made a list of possible gcd sequences that looked something like this: [(2^(k+1), …, 8, 4, 2, 1), (3 * 2^k, …, 12, 6, 3, 1), (3 * 2^k, …, 12, 6, 2, 1), …, (3 * 2^k, 2^k, …, 8, 4, 2, 1)] (i.e. progressing by 2 for each gcd, except for maybe once progressing by 3). Then for each gcd list: g, use combinatorics to count how many ways to place multiples of g[0], then multiples of g[1], ...

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

      Did you hardcode these lists in the code? Besides, there could be like 20 lists.

      Can you explain that for any given list, how to calculate the number of corresponding permutations ? erickjohnross

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

        No, I did not hardcode these lists, I had a loop that determined where the factor of 3 would be used. You can check out my submission: https://codeforces.com/contest/1174/submission/55937662

        For the combinatorics, suppose that for each element in the gcd list, we keep track of (e,f): how many numbers have that gcd as a factor (but not any larger gcd factors), and also how many slots we have to put them into (i.e. how many numbers have not been placed so far). We can then count how to place all the numbers starting from the largest gcd down to the smallest. For each gcd, one of the e numbers must be placed in the first available slot in order for that gcd to actually appear. There are e ways to choose which number this is. Then we can place the remaining e-1 numbers into any of the f-1 slots. There are (f-1)P(e-1) ways to do this, where nPk is the permutation function. So the total number of ways to place a gcd group is e * (f-1)P(e-1).

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

.

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

Lightning fast editorials! Love it!

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

    Anyone else got their problem B hacked? I didn't understand why my solution is wrong. My submission. Any help would be appreciated.

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

      If there are only even numbers you can’t sort.There must be at least one odd and one even number in such case you are able to swap everything you want.

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

Why u put exactly 36 queries, not round to 40?. The complexity of the search will be the same, but you save people from getting WA by one or two additional queries.

During the contest, I also came up with a solution using Centroid decomposition approach like in editorial, but I was scared to write it. Because the simple analysis gave me 37 queries. n = 2 ** 18, so we need 18 * 2 = 36 queries for the main approach and additional query for querying root to find the height of the node. Probably we need only 35, but I decided not to spend time to figure it and write another solution.

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

    I didnt got WA. But I always hate keeping exact queries. There should be a lose upperbound.
    Like in last Global round C we had $$$5*n$$$ instead of $$$4*n$$$. There should be something lose. Lose depends on author.
    But penalising for 1-2 extra queries without any reason imo is bad.

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

    I'm sorry, I didn't give it much thought. My solution does $$$34$$$ queries in simple analysis and $$$32$$$ in practice, so I thought $$$36$$$ isn't strict at all. The centroid decomposition solution is by the testers.

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

      It's your problem man, you don't have to sorry anyone. Some people like to do easy things which still make them feel like they are good

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

    I tried Centroid Decomposition after the competition and got AC, never heard of CD until I read the editorial, mine needed all 36 queries on test #16 and alot of the tests it passed with 35 queries. And I think at first I tried with getting first centroid from root and starting there and got WA, but then changed to starting from successor from root (i.e. "s 1" as first query) then proceed from that, then it passed, just barely. But I'm sure because I don't understand everything fully someone who knew what they were doing probably could have shaved a query or two off.

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

can somebody explain problem D? where are pairs? which pairs? what pairs? i just don't understand that part

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

    n<=18

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

      yeah, i made mistake, can you answer updated version of my question?

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

        The pair of numbers whose xor is x

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it
        Those pairs are the pairs of numbers whose xor is x;
        ex: 0 and (0 xor x) : because 0 xor (0 xor x) = x
            1 and (1 xor x) 
            2 and (2 xor x) ...
        You can not add both 2 numbers of 1 pair into the b array (prefix-xor array). Because if there are both numbers of 1 pair then there exists i and j in which: b[i] xor b[j] = x (b[i] and b[j] are in 1 pair)
        And b[i] xor b[j] = a[i+1] xor a[i+2] xor ... xor a[j] = x. (like in the editorial)
        a[i+1] xor a[i+2] xor ... xor a[j] = x is not allowed.
        So you have to choose only 1 number to add in a pair.
        P/s: Sorry for my bad english :>
        
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Got it!

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +2 Vote: I do not like it
            I think the logic behind using prefix-xor array is because the condition is "there is no non-empty subsegment with bitwise XOR equal to 0 or x". So I think when it comes to subsegment we should try using the prefix-... array as we can manage all the subsegments.
            ex:
            a[l]⊕a[l+1]⋯⊕a[r]=b[l−1]⊕b[r] // b is prefix-xor
            a[l]+a[l+1]+⋯+a[r]=b[r]-b[l-1] // b is prefix-sum
            ...
            And here the relation :
            a[l]⊕a[l+1]⋯⊕a[r]=b[l−1]⊕b[r]
            So we just need to build b for which there is no i,j such that b[i] xor b[j] = 0 or b[i] xor b[j] = x.
            And if there is no i,j like that, there is no subsegment against the condition 
            
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Lets say for n = 3 and x = 6, (2,4) make a pair whose xor is 6. So you are saying 4 and 2 cant be in one array because b[i] xor b[j] = x. Consider this array.

              [ 4 , 1 , 2]

              I dont think any prefix xor will be equal to 6. And I think this is a valid array. Can you explain this ? I am still in doubt.

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

                I think you have mistaken the array b (which is the prefix-xor array) and the array a we want to build as the answer. We use b to build a.

                So as your example : [4, 1, 2] is a not b. The condition of one number each pair in b must be satisfied so a can be built correctly. (a[i] = b[i] xor b[i-1] )

                Hope you will understand it

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

    n is 18 2^18 around 2e5 which pass in 1 sec

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

    why from 1 to 2^n — 1 ?

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

Why do not I have this code running on problem C?

#include <bits/stdc++.h>

using namespace std;

int n, i, j, k;

int prime[100000];

int main()
{
    cin >> n;

    for (i=2; i*i<=100000; i++)

        if (!prime[i])
        {
            k++;

            prime[i]=k;

            for (j=i*i; j<=100000; j+=i) prime[j]=k;
        }

    for (i=2; i<=n; i++) cout << prime[i] << ' ';
}
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    You haven't handled the primes greater than $$$\sqrt{100000}$$$.

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

      understand, it was a mistake, I copied the sieve and did not notice i * i in place of i

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

    In problem C its given that any pair (i,j) if its coprime than ai!=aj....then how 1 2 1 is satisfying this condition?? as 1 and 1 are coprime and also equal..i think i misuderstood the question pls help!

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

    You haven't the if(prime[j]) continue;

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

thanks for the lightning fast editorial :)

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

can somebody explain problem D? where are pairs? which pairs? what pairs? i just don't understand that part

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

In Question A how will you maintain the order while simply sorting and printing the array?

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

    The point is not to maintain the order, but to keep the same elements and rearrange them so the sum of the first half won't be equal to the second.

    By sorting them, you will definitely get array where the second half is greater than the first if all the elements are not the same. If they all have the same value you can't rearrange them to get diferent sums, so the answer will be (-1).

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

      but in question itself it is written You are allowed to not change the order.

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

        I understand, the wording of the description is not well written. Also, it is not written that when the output can have mutiple reorderings print any of them.

        So to answer your reply, the statement means that if the initial ordering have different sums then print the initial not reordered solution.

        Also, another remark is that it never says if the initial ordering will always have same sums.

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

        "You are allowed to not change the order."

        Is not the same as

        "You are not allowed to change the order."

        The first version simply means you can change the order if you'd like, but that is not required.

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

        I too got confused with the language and thought that the relative order must be maintained as it is .

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

Did anyone pass E with $$$N log ^2 N$$$ solution? Or it was intentionally eliminated?

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

My randomized solution to F (which imo has a very low probability of failure):

  • Use Query 1 on the Root Node (Node 1) to find the level of X. Take all the nodes at level X in a vector V (candidates of X)
  • Keep doing the following as long as size(V) > 1:

1) Randomly choose a node U from V and use Query 1 on it to find distance D of X from it.

2) The LCA of U and X must be at a distance of D/2 from U, so walk D/2 distance up from U.

3) Use Query 2 on the current node to find the subtree X belongs to, and discard all the candidate nodes that lie outside it.

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

    I had the same solution, but without the randomization. It failed on Test 99. But adding randomization made it pass. While it is kinda intuitive as to why it works, I really want to understand what is the exact difference it makes.

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

There is another approach for F. First query for the distance from root to node x to find the level of node x. The nodes in this level are our primary search scope. Now we will reduce the search scope by half using no more than 2 queries. Sort the nodes of search scope by their dfs starting time. Let u be the middle node of this order. Now we query for the distance from u to x. Using the distance we can find the LCA of u and x. Let the LCA be v. Now we query the 2nd type for this node v and the updated search scope is either the left or the right half of the initial search scope.

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

    How would you find the LCA of u and x using the distance? I saw your code and you've assumed that the LCA's at a distance of the distance between the 2 nodes/2 from the depth of our target node. How would you prove this? Also it isn't always guaranteed that the middle node of your dfs order will be at the same depth as your target node, right?

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

      Notice that all the candidates nodes are at the same level. We know the level after just first query.

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

        I'm confused as to why taking the midpoints of the dfs order would give a node with the same depth as a candidate node (if I've understood your solution correctly)

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

          We are considering nodes of that level only, then sort the nodes according to their dfs order.

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

    When I read your solution I started wondering why we can always reduce the search scope by at least half. I came up with the following argument: Assume that our search scope in some step is the ordered list s. Let s' denote our search scope after one iteration of your procedure (i.e. those 2 queries you proposed). Note that all the elements of s' have to appear consecutive in s. This is because s' contains exactly those nodes of s with ancestor a, where a is the response we get from the second query (i.e. a is the second node on a path from v to x). If the elements of s' were not consecutive in s then there would be some node p in s such that p is not in s' but p has ancestor a (Because we sorted after dfs starting time). Now assume for a contradiction that $$$2 \cdot |s'| > |s|$$$. Because the nodes in s' appear consecutive in s it follows that u is in s'. But then u would have ancestor a and thus $$$LCA(u, x) = a \neq v$$$. This is a contradiction.

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

Editorial code of D is wrong as it doesn't output right ans for second test case. 2 4

Expected output :- 3 1 3 1

Output by editorial code :- 2 3 1

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

    The whole segment is one of the subsegments.

    3 ^ 1 ^ 3 ^ 1 = 0

    EDIT: Sorry, in the first place, editorial's solution outputs 3 [1, 3, 1] ; expected answer.

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

      first no. is the size of array. its not 3 1 3 1 size of array 3 element:- 1 3 1

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

        My bad. Please check whether the code you run is certainly editorial's. (Or possibility like swapped with your solution.)

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

          I think that I have the correct code. For confirming that you can check it owm your own.

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

            ????
            hmm.. Inputs are also correct?

            Please simply run the code below. (wrote input data directly)

            code

            Or, to avoid depending on the environment, please check this https://wandbox.org/permlink/9PBeIfBz5Yjsqzl2

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

              According to the editorial, how it can be proved that this length is maximized. I mean is there any possibility to make new elements with the prefix[i-2], prefix[i-1] and prefix[i] or something like that.

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

    If we take full subset {3,1,3,1}, and the xor value of those elements would be zero. So your input is wrong.

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

I am one of the victims of test 99 in F, XD

But I don't get in which case my solution goes over the query limit. It's easy to follow the code (probably), else I'll clarify.

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

    Your solution is similar to mine (55049717)

    If someone can explain why does this approach fail, or perhaps give a hint on what is the tree like in test 99, I would really appreciate it.

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

      I think that the tree might be of the type as the example below:

      10 10

      1 2 2 3 3 4 1 5 5 6 6 7 5 8 8 9 8 10

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

      My solution is also the same. I tested my code with this case:

      200000
      1 2
      2 3
      3 4
      ...
      ...
      ...
      199999 200000

      and this gives RUNTIME ERROR while traversing through the DFS. Don't know what's the reason! :/

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

      I probably figured out, for a tree like this (of larger size) -

            / \
           / / \
          / / / \
         / / / / \
        / / / / / \
       / / / / / / \
      / / / / / / / \
      

      the number of queries in the worst case (when the rightmost leaf is the secret node) will go over 500, hitting the 'second type of query' for every node in the rightmost branch of the tree.

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

Brilliant round!!!

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

Problem E why the first number has to be 2^x*3^y? Any number in the form 2^x has more divisors than 2^x*3^y or not?

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

    I do not understand that part either

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

    Consider n = 12 here 2^3 and (2^2)*(3^1) both have maximum prime factors so we need to consider both.

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

Hey! Why is this code failing on problem A?

include"bits/stdc++.h"

using namespace std; int main(){ int n;

scanf("%d",&n);

int arr[2*n];
int sum=0,sumh=0;
int midele;
int ind=-1;
for(int i=0;i<2*n;i++){
    cin>>arr[i];
    sum=sum+arr[i];//calculating sum of array
    if(i<n)
       sumh=sumh+arr[i];//calculating sum of half array
    if(i==n-1)
       midele=arr[i];
    if(i>=n&&arr[i]!=midele)
       ind=i;//storing index of any number not middle element to swap later
}
if(sum%2!=0||sumh!=sum/2){
    for(int i=0;i<2*n;i++)
       cout<<arr[i]<<" ";
}
else if(sumh==sum/2&&ind!=-1){//that is if all the numbers are equal
    int temp=arr[n-1];
    arr[n-1]=arr[ind];
    arr[ind]=temp;
    for(int i=0;i<2*n;i++)
       cout<<arr[i]<<" ";
}
else if(sumh==sum/2&&ind==-1){
    cout<<"-1 ";
}
return 0;

}

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

mohammedehab2002 In the dp (PROBLEM E) where you are explaining the transitions, you said that "but you already added i" so you subtracted it from the product, Why not in the others transitions??

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

    In the first kind of transitions, we add a number that's a multiple of $$$2^x*3^y$$$. We used $$$i$$$ of them because the $$$gcd$$$ is $$$2^x*3^y$$$, so all already added numbers are of this kind. However, in the second kind of transitions, we add a number of the form $$$2^{x-1}*3^z$$$ (for some $$$z$$$). We never used any of these numbers since the power of $$$2$$$ in the $$$gcd$$$ is $$$x$$$.

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

nvm, I'm stupid, 36/2=18. :X

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

E can be solved in $$$O(n)$$$
Let $$$k=\lfloor \log_2 n \rfloor$$$, $$$dp0[i][j]$$$ be the number of "good sequence" with length $$$j$$$ and gcd $$$2^i$$$, $$$dp1[i][j]$$$ be the number of "good sequence" with length $$$j$$$ and gcd $$$2^{i-1}\cdot 3$$$.

For each $$$0 \le i \le k$$$, it's obvious that $$$1 \le j \le \frac{n}{2^i}$$$, so the total number of valid state is less than $$$n + \frac{n}{2} + \frac{n}{4} + \cdots + 1 = O(n)$$$.

Since each value of $$$dp$$$ can be calculated in $$$O(1)$$$, the time complexity is $$$O(n)$$$.

55054749

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

I tried reading the editorial for problem E, however I don’t understand why in the first observation we get more prime divisors if we divide by $$$p$$$ and multiply by 4?

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

    That's the case when p >= 5 , means we will only consider the numbers having 2 or 3 in its factorization

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

      In the editorial it is written prime divisors, but I think that they mean all divisors

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

        It is prime divisors only... If a number is n = 7*(2^x)*(3^y) then here 7 is a prime divisor which is greater than 3.. so we have better choice of n , n = 4 * (2^x) * (3^y) = (2^(x+2))*(3^y)

        Initially n had x+y+1 prime factors.. but we can have x+y+2..

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

          I didnt notice that you count same prime number more times, I understand it now, thanks

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

In Problem D-

There is no non-empty subsegment with bitwise XOR equal to 0 or x,

A sequence b is a subsegment of a sequence a if b can be obtained from a by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Construct an array such that no pair of numbers has bitwise-xor sum equal to 0 or x, and its length should be maximal

How this satisfies above criteria?

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

    I guess that by pair of numbers in the last definition they mean range of numbers between two indexes

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

    The array which is mentioned here is the prefix xor of answer array (and not the answer array) means , prefix[i] = a[1]^a[2]..^a[i]

    If the answer array has any subsegment from l to r which gives xor as 0 or x. Then in prefix array , prefix[l]^prefix[r-1] will give 0 or x. That's why it's said that no pair in prefix array gives 0 or x as their XOR.

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

Problem F can be done without HLD or Centroid decomposition.

code

The main idea is that: if $$$h[v]$$$, $$$h[x]$$$ — distances from the root to vertexes $$$v$$$ and $$$x$$$ and we ask query of the first type about $$$v$$$. We can find LCA for $$$v$$$ and $$$x$$$. Denote by $$$p$$$ the LCA. Now ask query of the second type about $$$p$$$. Denote by $$$u$$$ the answer. Now let's solve the problem for subtree of $$$u$$$.

If we write down all the leaves of the tree in dfs order $$$v_1, \dots, v_k$$$, and choose $$$v_{k/2}$$$ as v, we reduce our problem to problem at least twice less. So number of questions is not greater that $$$2logn$$$

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

In problem F I am getting wrong answer on test 99, can anyone help me? Here is the link to my code: https://codeforces.com/contest/1174/submission/55057721 Thanks!!

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

what should i modify in this code https://codeforces.com/contest/1174/submission/55049051 problem C can anyone help ?

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

    You assign 2 to numbers that are not even or prime but as an example 25 and 21 are not both but you assigned their value to 2 .they are coprime and can not be equal. You should assign each number and its multiples to the same number.

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

Can anyone explain me the solution of C?..thanks.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    As all the primes are coprime with each other so the indexes:
    2 3 4 5 6 7 8 9 10 11 12 13 ...
    / /   /   /   /    /     /  and so on => These numbers must have distinct a[]
    And to minimized all a[i] we have to start from 1:
    2 3 4 5 6 7 8 9 10 11 12 13 ...
    1 2   3   4        5     6
    That's for the primes. What about the remain numbers? Let's take number 4.
    To avoid having the same number with the numbers which is coprime with. (like 4 and 3 are coprime, 4 and 5, 4 and 7 ...), the only secure way is to assigning the same number as it first factor, in this case of 4, is 2.
    2 3 4 5 6 7 8 9 10 11 12 13 ...
    1 2 1 3 1 4 1 2 1  6  1  7
    Why it's true? Because the number we choose (here is 4) will never be coprimed with its factors (there gcd() would be always >=2) so we don't afraid that it will be against the condition
    P/s: sorry for my bad english :>
    
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Great explanation..now I understand it... Thanks

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

        Why always choose first divisor?? And in editorial it is given to choose only prime divisor but I think if we choose composite then it also works.? Correct me if I'm wrong..thanks

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it
          Because choosing the first divisor is easier to implement.
          you can use sieve of erathones to both identify primes and mark other numbers 
          
          And your next question, I think it will also work, but it's just harder to implement it.
          

          void sieve(int N) { fill(bs,bs+N+1,-1); long long tem=0; bs[0]=bs[1]=0; for (long long i=2;i<=N;i++) if (bs[i]==-1) // i is a prime { for (long long j=i*i;j<=N;j+=i) bs[j]=tem+1; // tem+1 will be assinged by bs[i] later bs[i]=++tem; // here } }
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            thanks @HynDuf great explanation

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

fast and useful,thx!:)

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

Actually problem F could be solved using binary search and binary lifting and binary search.

First just save the nodes according to their height(their distance from the root), and for each height, save the nodes according to dfs order. So query "d 1" will narrow the search down to the set of nodes which have the same height.

Let h[v] is the distance from the root to v. Obviously h[1] = 0.

Let dist[v] is the distance from the x (the hidden node) to v. Obviously dist[x] = 0.

Because in the set nodes are in dfs order, so let say x (the hidden node) is i-th node in the set, we have the following observations in the set:

a, From 1st->(i-1)-th node: dist[v] is non-increasing.

b, The i-th node is x and dist[x] = 0.

c, From (i+1)-th -> final node : dist[v] is non-decreasing.

<--Look like the upper envelope so we can perform binary search somehow in the set -->

Suppose we get into the range [l, r] in the set, let mid = (l+r)/2. Let the mid-th node in the set is v. Query dist[v] ("d {v}" obviously).

Obviously if(dist[v] == 0) the answer is x == v. We can see that we will always get to know x while performing binary search

Because h[v] = h[x] so dist[v] is even, and by binary lifting, we could find the u, the (dist[v]/2)-th parent of v, which is also of x. Then we query ("s {u}"), let say we get the node t, and obviously dist[t] = dist[v]/2 — 1. Again by binary lifting, we find z is the (dist[t])-th parent of v.

Because the nodes in any sets of same-height nodes are in dfs order, so if z is placed before t, so v is placed before x, and we move to the range [mid+1, r] to find x. Or else we move to [l, mid-1].

I think we can prove that no more that 35 queries could be used.

My submission : 55063713

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

can someone tell me why is my solution of B is failing: https://codeforces.com/contest/1174/submission/55029449

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

    initialise odds and even to 0 as it will work...

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

Can someone please explain me what is the use of the ex[arr[i]%2]=1; in line 13 of [this] solution of problem B (https://pastebin.com/xhqGXLiu)

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

    there are two flags if ex[0] is true that means at least one even number is present if ex[1] is true that means at least one odd number is present

    for all odd numbers num%2 = 1 and even numbers num%2 = 0

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

      but these variable may contain garbage value... it will work I compile it..

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

        variables in global scope have default values. ex. false for booleans, and 0 for numbers.

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

          yes u r write but in this case variable is not global so we should initialise it with 0 to avoid garbage value... correct me if I'm wrong.

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

            I thought we were talking about ex, which is global. If we weren’t, then that’s my mistake.

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

              but I'm talking about @v_kamani19 code

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

      Okay... if all numbers are either even or odd then we can't swap any. This flag ensures that at least one even or one odd is present. Isn't it? Thanks!

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

Dou you guys have any idea about what is causing TLE at case 12 in Problem F? I tryed cheking the number of queries, Fast IO, wrong centroid, but i couldn`t find it. This is my code: https://codeforces.com/contest/1174/submission/55087589

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

Can anybody tell me why i'm getting TLE for problem-B for this java code---

import java.util.*; import java.io.*;

public class HelloCodiva { public static void main(String[] args) throws Exception {

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(br.readLine());
String[] str=br.readLine().split(" ");
int[] arr=new int[n];
int c1=0;
for(int i=0;i<n;i++){
  arr[i]=Integer.parseInt(str[i]);
  if(arr[i]%2==1){
    c1++;
  }
}

if(c1!=0 && c1!=n){
  Arrays.sort(arr);
}

for(int i=0;i<n;i++){
    System.out.print(arr[i]+" ");
  }

} }

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

    Is array.sort O(NlogN) ?

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

      Thanks, i just found that for object type java uses merge sort whereas for primitive types it uses quick sort, whose worst case is N2.

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

in problem 1, the last line says , we cannot change the order!!! how can we apply sorting then???

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

Is there O(n) solution for problem E?

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

Can someone please explain me why do we need to take prefix xor's for problem D ? For eg. if we take case of x>=2^n, we can take the array as 1,2,3,..,2^n-1. We cannot have xor equal to 0 or x for the sequence. Then what is the need of taking prefix xor for each ? What am I missing ?

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

    But when you take 3 first elements, then xor of this subsegment is equal to 0. If I good understood your thinking of course. :)

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

What do you mean by You are allowed to not change the order in problem A???

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

    If the initial order is good, You are allowed to not change the order and just print it as an answer.

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

Ignore.

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

short questions , fast editorial , good explanation , great!

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

For F here is the solution I thought of. Find the level of x(say r) by quering distance from 1. Now considering the distances of all the nodes(ordered in the order of dfs traversal) at level r from x we have an array of size atmost O(n) in which there exists exactly 1 minima(the distance decrease to 0, then increase) which we can find in O(logn). Is there something I am missing because I am not even using queries of the second type.

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

Can someone explain what is the prefix-xor concept for problem D. I had a hard time trying to understand the editorial. Couldn't get that.

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

    Let's call an array A and you want to find the xor in a range from l to r. To do that, you can calculate an array P (prefix-xor) as follow:

    $$$P[i]=A[0] \oplus A[1] \oplus ... A[i] $$$

    Now

    $$$P[r] \oplus P[l-1]$$$

    answers the query To solve problem D, find P instead of A.

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

Why are we searching using the heaviest path rather than the longest path?

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

Just a lil observation on E

Then, s must have the maximal possible number of prime divisors.

I think it's more accurate to say the sum of the powers on the priime divisors of s should be maximal. That way we have more powers to drop at every step. For examples it would be more optimal to take 180 that has 3 prime divisors(2, 3, 5) than to take 210 that has 4 prime divisors(2, 3, 5, 7).

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

    I believe this is more of a clarification than an observation. The editorial meant what you just stated.

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

I wonder if problem E has a combinatorial solution. Because I reviewed some AC codes, and I saw other approaches ,but I could not understand them.

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

C can be solved in $$$O(n)$$$ by just using the way we sieve prime in $$$O(n)$$$

All you need is to add two lines to the original code

int n; 
int ans[maxn];//answer of the question
int vis[maxn];
int prime[maxn];
int cnt=0;
void sieve(int n){
	vis[0]=vis[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			prime[++cnt]=i;
			ans[i]=cnt;
		}
		for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
			vis[i*prime[j]]=1;
			ans[i*prime[j]]=j;
			if(i%prime[j]==0) break;
		}
	}
}
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't find a test for maximum queries of my solution of F.

The idea is to keep the amount of possible vertices (i.e. places on the depth we find by first query) in a subtree of root. On every step we want to ask no more than 2 queries (it's provable we'll ask exactly one on the last step, so the max sum is 36), and change the tree (move the root or cut a part) in the way, that amount of possible vertices is at least 2 times smaller.

Let's look at the root: there're $$$W$$$ possible vertices. If it has no children with at least $$$W / 2$$$ possible vertices, then we perform an s-query and continue. Otherwise, we find first vertex $$$v$$$, which children all have possible vertices value less than $$$W / 2$$$ and perform a d-query for it. After that we know if $$$x$$$ is placed in the subtree of $$$v$$$ or not. If not we remove the whole subtree, otherwise perform an s-query from $$$v$$$.

The submission: 55134088

The most amount of queries in the system tests is 18.

I wonder if it's possible to construct a test with worse result or maybe it's provable that maximum queries if less than 36. Can anyone help?

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

[deleted]

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

Need help in E.
Why $$$f([3, 1, 2]) = 2$$$(what does $$$g_i$$$ mean?)

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

    G[i] — gcd of the prefix of size i of the permutation, or gcd(p1,p2,p3,...,pi)

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

      sorry, i don't understand.
      for $$$[3, 1, 2]$$$
      $$$g[1] = gcd(3) = 1$$$
      $$$g[2] = gcd(3, 1) = 1$$$
      $$$g[3] = gcd(3, 1, 2) = 1$$$
      why $$$f([3,1,2])=2$$$

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

        gcd(3) = 3, not 1 greatest common divisor of a single number is the number itself. so it will be g[1] = gcd(3) = 3 g[2] = gcd(3,1) = 1 g[3]= gcd(3,1,2)=1 We have 2 distinct gcd. Another example: for [4,2,1,3] g[1] = 4 g[2]= gcd(4,2) = 2 g[3]= gcd(4,2,1) = 1 g[4] = gcd(4,2,1,3) = 1 So we have 3 distinct gcd.

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

        Sorry for the weird format in which the comment came out.

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

          oh, the thing I missed is greatest common divisor of a single number is the number itself.
          thank you :)

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

Great F, need more like this in the future.