mohammedehab2002's blog

By mohammedehab2002, 13 days 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

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

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

    HLD — Heavy Light Decomposition CD — Centroid Decomposition

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

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

.

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

Lightning fast editorials! Love it!

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

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

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

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

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

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

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

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

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

    n<=18

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

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

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

        The pair of numbers whose xor is x

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

          Got it!

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

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

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

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

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

    why from 1 to 2^n — 1 ?

»
13 days 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] << ' ';
}
  • »
    »
    13 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

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

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

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

      i and j, not a[i] and a[j]

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

      In this example the set contains 2, 3 and 4. We need to check co-primes in pairs from this set. That is: (2,3) -> co-prime, (3,4) -> co-prime, (2,4) -> NOT co-prime

      Hence we assign the values 1 (for 2), 2 (for 3) and 1 (for 4) in this set. Notice that 2 and 3 are co-primes thus they have been assigned different values(1 and 2). Similarly 3 and 4 are co-primes hence their values differ. But 2 and 4 are not-co-primes. Hence we assigned the same value 1 to both.

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

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

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

thanks for the lightning fast editorial :)

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

I know two others have already posted thanks, but still, thank you for the fast tutorial

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

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

Poor Pretests for A and B,my java solution is giving TLE beacuse of sorting.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Brilliant round!!!

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

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

    I do not understand that part either

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

»
13 days 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;

}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        • »
          »
          »
          »
          »
          12 days 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 } }
          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            thanks @HynDuf great explanation

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

fast and useful,thx!:)

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

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

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

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

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

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

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

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

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

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

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

              but I'm talking about @v_kamani19 code

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

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

»
12 days 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]+" ");
  }

} }

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

Hello Everyone! in problem 1174A — Ehab Fails to Be Thanos Can anyone explain how can I write code for method 2 for "Otherwise, find any pair of different elements from different halves" since , according to me for every iterate for the first half of array check for second half till we find, if not then in the worst case I have to iterate to O(n^2) time. I know it will be in time 10^6, but still does any other method??

does any other method exist???

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

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

    Read it again ! "You are allowed to not change the order."

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

    //You are allowed to not change the order.

    do you mean this? I think that means we can choose not to change the order. It doesn't mean we cannot change the order.

    EDIT: oops... I came down to this comment so late...!!

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

Is there O(n) solution for problem E?

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

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

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

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

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

Ignore.

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

short questions , fast editorial , good explanation , great!

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

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

    How will you be finding the Minima can you explain that part?

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

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

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

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

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

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

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

why are we building prefix xor in Problem D

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

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

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

    For getting odd numbers as sum, there should be at least one odd as well as one even number in array. But your code is just checking if there are odd numbers as a result it will give "WA" verdict if there is not a single even number. Eg: 7 3 9 5 Here oddno.=4 but you can't do swapping here, because sum will be always even.

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

Can anyone help me in Problem D? I saw the ediori and tried to understand if for whole night and also searched for prefix-xor array, but wasn't able to deal with it, any link to resources or a useful explaination is more than enough.

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

Problem E is really hard. looks like author took it from some maths olympiad problem book.

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

C can be easily solved with a Sieve of Eratosthenes iterating through 2 to n as follows:

  1. Create an array of integers from 2 to n.
  2. Create a counter variable.
  3. From 2 to n, iterate through each index that has not been visited yet (denoted with the default array value of 0 (in java)). Every index that has not been visited yet will increment the counter variable by 1.
  4. Each time an index (i) is visited, change its value and all of its multiples that have not been visited to the counter variable.