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 ?

.

Lightning fast editorials! Love 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.

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

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] << ' ';
}

thanks for the lightning fast editorial :)

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

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

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

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.

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.

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

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.

Brilliant round!!!

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?

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;

}

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

In F random works fine!

https://codeforces.net/contest/1174/submission/55052166

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

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

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?

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?

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

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

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

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

fast and useful，thx！：）

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

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

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)

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.net/contest/1174/submission/55087589

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

} }

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

Is there O(n) solution for problem E?

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 ?

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

Ignore.

short questions , fast editorial , good explanation , great!

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.

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.

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

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

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.

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;
		}
	}
}

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?

[deleted]

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

Great F, need more like this in the future.