Codenation Interview Question — Help Needed

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя kstheking

Codenation Interview Question — Help Needed

Автор kstheking, история, 4 года назад, По-английски

So we had an Interview Question at Codenation, This is the question Question Image. I understand that we can do the update node and sum of values through segment trees but what I can't understand is how to find the aith beautiful number, can someone help me out please! Also the constraints of X in the question are below 10^5

#segment-trees, #trees

kstheking
4 года назад
51

Комментарии (47)

Показать архивные | Написать комментарий?

Dsxv

4 года назад, # |

+37

Hi!

A simple bfs should be enough.

Here's a code for creating series whose sum of square of digits <= x.

The remaining is just classical euler tour and update using segment tree.

I'll leave the complexity analysis to you.

Thanks!

→ Ответить

vagi

4 года назад, # ^ |

← Rev. 2 →

Dsxv, could you please clear this for me.

q.push({(cur*10 + i)%mod , sum + i*i}) ;

Won't taking mod here change the number itself. It'll yield the wrong number when used further, right?

For instance, for x=1, we get the first 15 numbers as this:

Output for x=1

→ Ответить

Dsxv

4 года назад, # ^ |

Hi!

The deciding parameter for the series is actually the second number i.e, sum + i*i.

As far as the numbers in series are concerned, notice that the question is asking us to take mod of sum of all the values (fi) in the subtree.

Where the values (fi) in the subtree are nothing but the elements of our series.

Now,
property of modulus addition:(A+B+C...) % mod = (A%mod + B%mod ...) % mod
so, taking mod of A, B ... beforehand doesn't affect our answer.

Feel free to ask anything if you still have any doubt.

Thanks!

→ Ответить

vagi

4 года назад, # ^ |

Yup, The deciding parameter for the series is actually the second number i.e, sum + i*i.

I get it now. Thanks.

→ Ответить

kstheking

4 года назад, # ^ |

Hi, I have a little doubt, since we are beginning with 1, wouldn't this code leave out numbers which begin with 2, 3 etc.

→ Ответить

Dsxv

4 года назад, # ^ |

Yes, Updated. Thanks for pointing out!

→ Ответить

Umnik

4 года назад, # ^ |

Your logic won't work for x = 5, you push {1, 1} and then push {10*1 + i, 1 + i*i}, but the number {2, 4} also satisfies the constraints.....how will your algo detect that??

→ Ответить

Dsxv

4 года назад, # ^ |

Updated. Thanks!

→ Ответить

650iq

4 года назад, # ^ |

← Rev. 2 →

Hi bro can you pls suggest some beginner level problems involving euler tours or similar concepts? would be really helpful

→ Ответить

Dsxv

4 года назад, # ^ |

Hi!

I suggest you to read LCA and learn the idea behind it as well as solve the questions mentioned at the bottom (First one is literally just template check).

Thanks!

→ Ответить

_pastor_

4 года назад, # ^ |

why a segment tree is required?

→ Ответить

Dsxv

4 года назад, # ^ |

← Rev. 2 →

It's required for finding the sum all nodes of subtree as well as updating the nodes.

Edit : please read my comment below for more info

→ Ответить

HG_90

4 года назад, # ^ |

How to update using segment tree, it is not given in the question that the tree is binary tree , how exactly will the indexing of segment tree will work????????

→ Ответить

Dsxv

4 года назад, # ^ |

Hi!
We can't apply segment tree directly onto the tree for solving this problem. First we have to flatten the tree using Euler tour. After this we know the in and out time of every node.

We know that all nodes in the subtree of (say X) also lie between the range (in and out of X) so we can just get sum of this subarray using segment tree and divide this by 2.
for updating an element we just update the element at it's in and outindexes

→ Ответить

faker_faker

4 года назад, # ^ |

I think flattening the tree into an array of size n is more "natural". There, you only increase t when you enter a new node, so you still have t_in and t_out but you only need to update once and sum doesn't over-count.

→ Ответить

orange_trie

4 года назад, # |

← Rev. 2 →

how did you solve 2nd question? question 2 laser tag

i thought of dp recurrence donno if its correct tho as hackerrank was very slow during the test(my test was completed before knowing the status of submission).

Spoiler

dp[i] represents the number of games needed for i people. at last check if dp[i] <= 2*x

→ Ответить

one_last_chance

4 года назад, # ^ |

Just take ceil of log2(n). This will be your number of matches.

→ Ответить

kstheking

4 года назад, # ^ |

as one_last_chance mentioned, what we can do is first distribute them in teams of half, now consider one half and swap its half people to the other side,
now you have a quarter of people who have been together, swap half of them to the other side
By doing this log2(n) times you can generate configurations in which each person has fought with every other person

→ Ответить

sarkarasm

4 года назад, # ^ |

I implemented the same solution. It passed all tescases.

→ Ответить

orange_trie

4 года назад, # ^ |

← Rev. 2 →

actually mine also should work! as it is same taking ceil(log2(i))

but donno about the status of the submission though

if(i%2==1){dp[i] = 1 + dp[i/2 +1];}

else{dp[i] = 1 + dp[i/2];}

→ Ответить

gaurav5

4 года назад, # ^ |

Can u share the 3rd problem?

→ Ответить

orange_trie

4 года назад, # ^ |

sure! link for 3rd problem

→ Ответить

navneet.h

4 года назад, # ^ |

just sharing a similar question if wanna try

https://www.codechef.com/SEPT19A/problems/DOOFST

→ Ответить

_pastor_

4 года назад, # ^ |

it is correct

→ Ответить

shashwat_iiests

4 года назад, # |

Did anyone solve the xor one?

→ Ответить

orange_trie

4 года назад, # ^ |

i observed binomial coefficients pattern (pascal triangle) and solved using it.

Spoiler

→ Ответить

kstheking

4 года назад, # ^ |

I didn't know about Pascal Triangle, couldn't make sense of the pattern, thanks!

→ Ответить

orange_trie

4 года назад, # ^ |

the nth level is same as

nC1 , nC2 , nC3 , nC4 ... .. nCn

ncr is n!/((n-r)! * r!)

→ Ответить

tujhe_kyon_janna_hai

4 года назад, # ^ |

how do u solve tournament question.i solved in o(n2) using dp stilll some cases are not passing.

→ Ответить

Rudraksh

4 года назад, # ^ |

I knew about Pascal Triangle, still couldn't make sense of the pattern, thanks!

→ Ответить

shubhammitt

4 года назад, # ^ |

← Rev. 4 →

Lemme describe the question first for those who don't know.

Question

Constraints

Hint

Spoiler

Code

#include<bits/stdc++.h>
using namespace std;

// main Observation
vector<int> solve(vector<int> a, int p){
    // p should be power of 2
    vector<int> ans;

    int x = 0;
    for(int i = 0 ; i < p ; i++)
        x = x ^ a[i];

    ans.push_back(x);

    for(int i = p ; i < a.size() ; i++){
        x = x ^ a[i - p] ^ a[i];
        ans.push_back(x);
    }
    return ans;
}

// bruteforce soln
int bf(int n, int k, int m, vector<int> a){
	while(k--){
		for(int i = 1 ; i < n ; i++){
			a[i - 1] = a[i] ^ a[i - 1];
		}
		n--;
	}
	return a[m];

}

int main() {
	srand (time(NULL));

	int t;
	cin >> t;
	while(t--){
        
                // prepare input
		int n, k, m ;
		vector<int> a;

		#ifndef input
			n = rand() % 10000 + 2;
			k = rand() % (n - 1) + 1;
			// 0 to n - 1 -k
			m = rand() % (n - k);

			for(int i = 0 ; i < n ; i++)
				a.push_back(rand()%10000000);

		#else
			cin >> n >> k >> m;
			for(int i = 0 ; i < n ; i++){
				int x;
				cin >> x;
				a.push_back(x);
			}
		#endif

		// duplicate input
		int d_n = n, d_k = k, d_m = m;
		vector<int> d_a = a;


		// input preparation over 

		int bf_ans = bf(n, k, m, a);
		
		while(1){

	    	// calculate highest power of 2 less than k
	        int p = 2;
	        while(p * 2 < k) p *= 2;

	        if(p - 1 <= k and k > 1){
	            k -= (p - 1);
	            a = solve(a , p);
	            continue;
	        }

	        //bruteforce; at this point value of k would be 1-digit so bruteforce will work
	        n = a.size();

	        while(k--){
	            for(int i = 1 ; i < n ; i++)
	            a[i - 1] = a[i] ^ a[i - 1];

	           	n--;
	        }

	        break;
	    }

	    if(a[m] != bf_ans){
	    	cout<<"failed";
	    	break;
	    }
	    else
	    	cout<<"ok\n";
	}

	return 0;
}

P.S. : I was not able to code it during the contest and just verified with bruteforce soln after the contest, so there might be some mistakes. I would appreciate if anyone points out any issue.

→ Ответить

tujhe_kyon_janna_hai

4 года назад, # ^ |

How did u do tournamnet questions??i used dp for that like:dp[2]=1,dp[1]=1;thenfor(i=3;i<=n;i++){int t=INT_MAX;for(j=1;j<i;j++){t=min(t,dp[j]+dp[i-j]+1);}}if(x>=(dp[n]+1)/2))"1";else "0";what is wrong in this

→ Ответить

shubhammitt

4 года назад, # ^ |

Could you please use good formatting?

→ Ответить

tujhe_kyon_janna_hai

4 года назад, # ^ |

← Rev. 2 →

88179101 plz see at this dp[1]=0

→ Ответить

Ragnar7

4 года назад, # ^ |

← Rev. 3 →

N was the total numbers of player . Assume N is a perfect power of 2. Divide them in teams of size N/2 and let them fight. Team A = N/2 Team B = N/2 players Now each player in Team A will fight against every player in Team B . Only the players of Team A & B haven't fight among themselves . So again divide them in two halves Team A ( N/2 ) -> Team C (N/4) Team D (N/4)

Team B ( N/2 ) -> Team E (N/4) Team F (N/4)

Team C & D & E & F will be of size N/4.

Now if you let fight between C & D and E & F then +2 will get added in answer . But is this the optimal ?

No , Because you can club Team C and E , Team D and F then let them fight . doing this +1 will get to the answer.

So basically what is the terminating condition ? when size is equal to 1

N -> N/2 -> N/4 — > N/8 -------------> 1 solve it to get the answer.

So ans is log(N) base 2 if it is a perfect power of 2. if not then log(N) base 2 + 1 ( for the remaining )

→ Ответить

tujhe_kyon_janna_hai

4 года назад, # ^ |

thnx.

→ Ответить

Umnik

4 года назад, # ^ |

Just brute force with help of bitsets.

→ Ответить

shippuden

4 года назад, # |

← Rev. 2 →

For Question 3
Simple/well known fact is that for any given number $$$x$$$ we know $$$xor(x,x)=0$$$,
so if we take xor of $$$x$$$ with itself an even number of times then $$$xor(x,x,x....)=0$$$,
but if we take xor of $$$x$$$ with itself odd times the result is $$$x$$$.

Notation Used- $$$xor(x,x,x...x)[k-times]=x^k$$$

Consider the simple array $$$a=1,2,3,4,5$$$

For observing the pattern assume $$$m=0$$$
So we will look only at the value $$$a[0]$$$
Performing the operation 1 time we get —
$$$a[0]=[1\cdot2]$$$
here $$$1\cdot2=xor(1,2)$$$ same notation is followed below
2nd time —
$$$a[0]=[1\cdot2^2\cdot3]$$$
3rd time —
$$$a[0]=[1\cdot2^3\cdot3^3\cdot4^1]$$$
4th time —
$$$a[0]=[1\cdot2^4\cdot3^6\cdot4^4\cdot5^1]$$$
5th time —
$$$a[0]=[1\cdot2^5\cdot 3^{10} \cdot4^{10}\cdot5^5\cdot6^1]$$$

Now observe the powers of $$$1,2,3,4,5,6$$$ which are respectively $$$1,5,10,10,5,1$$$ which helps us notice the pattern as we can now see that powers obtained after 5th time are nothing but

$$${5 \choose 0},{5 \choose 1},{5 \choose 2},{5 \choose 3},{5 \choose 4},{5 \choose 5}$$$

But how to find $$$4^{10}$$$ or $$$2^5$$$(xor-value) ? For finding the value we just need to know for any $$$k$$$, $$$i$$$ when $$${k \choose i}$$$ is even and when it is odd. or we just need to find $$${k \choose i} \% \space 2$$$ for doing this many methods are given on gfg you just need to select the appropriate method keeping in mind the time-complexity as here $$$k$$$ is the of the order of $$$10^5$$$. Some methods are given here, and here.

Спойлер


int main()
{
    int parity[k + 1];

    //compute parity of (k)C(j)for j=0 to k

    int ans = 0;
    int j = 0;
    for (i = m; i <= k + m; i++)
    {
        //if (k)C(j) is odd then xor it with
        //answer othwerwise not
        if (parity[j] == 1)
            ans = ans ^ a[i];
        j++;
    }
}

→ Ответить

-is-this-fft-

4 года назад, # ^ |

+12

That's an interesting pattern. Why does this happen?

→ Ответить

shippuden

4 года назад, # ^ |

← Rev. 2 →

+15

(most of what is written below is based on this amazing video by kartik8800 I really recommend watching it link)
Really Long comment ahead —
We start off by looking at the really cool animation of pascal triangle on wikipedia, which offers us some satisfaction because something similar is happening there.
Note how in the above animation the value of one row is calculated on the basis of previous row, which itself is based on the recurrence relation

$$${n \choose r}={n-1 \choose r}+{n-1 \choose r-1}$$$

So for this particular question what we are essentially doing is sort of like pascal triangle.

Image

In the above example the value of a node is simply xor of the two nodes below it(like xor(1,2)=3). This makes sure that the size of the array is reduced by 1 after every step(as in our original question).
Indeed another way of stating the above visual operation can be - given an array at each step $$$a[i]=xor(a[i],a[i+1])$$$ is done for a particular $$$k$$$ number of times.

Let's now jump to a seemingly unrelated problem the famous dp problem.

The question is about how to count the number of shortest path in a grid from (0,0) to (m,n) if only moving to the up or right cell is allowed at each step.

This has a very short dp solution based on the recurrence - $$$f(m,n)=f(m,n-1)+f(m-1,n)$$$ where $$$f(m,0)=1$$$ and $$$f(0,n)=1$$$.
However the number of such paths can be directly proven to be $$${m+n \choose m}$$$.
A very nice combinatorial/intutive proof is given at brilliant and stackoverflow.

Jumping back to our question assume we have an array of size $$$k+1$$$ , since performing the operation each time reduces the size of our array by 1, so after $$$k$$$ such operations only one element will be left and we want to find that value.
For finding the value all we need to find is for each index $$$i$$$ in the original array ( that is $$$i=0,1,2...,k-1,k$$$) what is its contribution in the final array.

Image

Note that the number on top of each node is just it's index.
The image also shows at which positons the index=3 is contributing.
Now the real insight for linking the two problems is that the contribution of the index $$$i$$$ is nothing but the number of ways to reach the top element if we are only allowed to either move up-left or up-right(as shown in image)
The reason for that is based on the idea that each time the element goes up-left or up-right it contributes it's current value to that index, this is even more clear by looking at the recurrence relation.

Recurrence relation

So all that is left to calculate is to find the number of ways to reach the top-most element for the element at index $$$i$$$.
It is easy to observe now that it takes exactly $$$i$$$ up-left moves and exactly $$$k-i$$$ up-right moves for it to reach the top(for example the element at index 3 requires 3 up-left move and 4-3=1 up-right move).
So by the formula for number of such paths= $$${m+n \choose m}$$$. For our question the number of such paths is given by $$$m=i,n=k-i$$$.

$$${i+(k-i) \choose i}={k \choose i}$$$

Which explains the formula I got in my previous comment.

Additional question

Bonus

→ Ответить

yashbansal4953

4 года назад, # ^ |

That is a very neat and clever observation.

→ Ответить

kartik8800

4 года назад, # |

+22

Here is my O(N) solution to ZaurXOR: https://youtu.be/lccWXAd7enI
I think the solution is very easy to comprehend and does not use any pattern observation etc. I have used number of paths in a graph to evaluate the answer.
Basically I have developed a DP solution and optimized it using some very basic combinatorics!

→ Ответить

almorex11

4 года назад, # |

Hey... How do you get to know about these tests?? I missed Facebook HackerCup and now this. Can anyone please tell me how can I keep track of these interview tests or competitions? Plz, it would be a great help!!!

→ Ответить

Ragnar7

4 года назад, # ^ |

← Rev. 2 →

+13

use https://clist.by/ to know about ongoing contest. btw codenation test was only for college student for hiring and internship. Their college's training and placement cell float the test link.

→ Ответить