Search

vishyblog

December 2015

3.
Utkarsh and Ancestor Queries
Max. Marks 100

Utkarsh was playing with a rooted tree of N nodes. Each node is numbered from 1 to N. Assume 1 as the root. Each node i has two integers Ai an Bi associated with it.

You need to answer Q queries of 2 types
1 v x : update Av = x
2 v : Tell how many nodes p are there such that p is an ancestor of v and Ap ≤ Bv

Note: P is an ancestor of v if P = v or P is ancestor of parent of v.

Input:
First line contains two integers N and Q.
Following N-1 lines contains pair of integers a b denoting there is an edge between a and b.
Next line contains N integers denoting the Array A
Next line contains N integers denoting the Array B
Next Q lines describe Q queries.

Output:
For each query of type 2 output the required answer.

Constraints:
1 ≤ N ≤ 6104
1 ≤ Q ≤ 8
104
1 ≤ Ai, Bi, x ≤ 105

Sample Input

```10 10
2 1
3 1
4 3
5 1
6 3
7 6
8 6
9 2
10 8
4 2 2 2 4 2 1 4 2 1
3 5 3 2 5 3 3 2 3 2
2 3
1 9 5
1 6 4
1 3 2
2 6
1 8 5
1 6 2
1 7 3
2 9
2 1
```
Sample Output

```1
1
1
0
```

Roy and Alfi are playing a game with three 1000-sided dice. Each die has 1000 faces and all the faces are marked from 1 to 1000 on each die.

Alfi rolls all three dice together and sums up the score on all three dice. Total score of Alfi is denoted by A. Now it is Roy’s turn to roll them. Let us denote Roy’s score as R, which is sum of scores on all 3 dice.

You have to find the number of ways in which R ≥ A.

Input:
First line contains T – number of test cases.
Each of the next T lines contains a single integer A – total score of Alfi.

Output:
For each test case output the result in a new line.

Constraints:
1 ≤ T ≤ 10
3 ≤ A ≤ 3000

Sample Input

```3
3
4
3000
```
Sample Output

```1000000000
999999999
1

```
Explanation

For three 1000-sided dice, the sample space would consist of 1000000000 ways.
These ways are (1,1,1), (1,1,2), (1,2,1), (2,1,1), … , … , … , (1000,1000,1000).

Test #1:
Sum of three dices such that it is greater than equal to 3.
This is satisfied by all the ways in the sample space. So the answer is 1000000000.

Test #2:
Sum of three dices such that it is greater than equal to 4.
This is not satisfied by only way (1,1,1) out of 1000000000 ways. So the answer is 1000000000 – 1 = 999999999.

Test #3:
Sum of three dices such that it is greater than equal to 3000.
Only way that satisfied this is (1000,1000,1000). Hence the answer is 1.

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

#define ll long long int

int findWays(int m, int n, int x)
{

int table[n + 1][x + 1];
memset(table, 0, sizeof(table)); // Initialize all entries as 0

for (int j = 1; j <= m && j <= x; j++)
table[j] = 1;

for (int i = 2; i <= n; i++)
for (int j = 1; j <= x; j++)
for (int k = 1; k <= m && k < j; k++)
table[i][j] += table[i-1][j-k];

/* Uncomment these lines to see content of table
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= x; j++)
cout << table[i][j] << ” “;
cout << endl;
}*/
return table[n][x];
}
double solve(int m, int n, int x) //m : range; n , dices, x threshold.
{
if (x > m*n || x < n)
return 0;
vector<vector<int>> dp(2, vector<int>(m * n + 1));
for (int i = 0; i <= m * n; ++i)
dp[i] = min(i, m);
for (int i = 1; i < n; ++i)
{
fill(&dp[i%2], &dp[i%2][i], 0);
for (int j = i; j <= m * n; ++j)
dp[i%2][j] = dp[i%2][j – 1] + dp[(i – 1)%2 ][j – 1] – dp[(i – 1)%2 ][j – 1 – min(j – 1 , m)];
}
return double(dp[(n – 1)%2][m*n] – dp[(n-1)%2][x]) / dp[(n – 1)%2][m*n];
}

int main()
{

ll n,a,r,sum=0;
cin>>n;
while(n–)
{
cin>>a;
if(a==3000)
{
cout<<1<<endl;
continue;
}
for(int i=0;i<a;i++)
{
sum+=findWays(1000,3,i);
}
cout<<solve(1000,3,a);
cout<<1000000000-sum<<endl;
}

return 0;
}

Shil and Hill Climbing
Max. Marks 100

Shil decided to go for hill climbing on this weekend, but he doesn’t have the map of all the hills. However he can make his own map.
There are N hills arranged on a line, each in the form of a vertical line segment with one endpoint on the ground. The hills are numbered with numbers from 1 to N from left to right. The i-th hill has height hi.

Beautiful set S is set of hills such that for any hi, hj present in set S , (hi * hj)%p != 1. Note that here i can be equal to j. Here p is any prime integer. To make the map, Shil needs maximum possible size of Beautiful Set.

Note that two sets are considered different if they contain atleast one point which is different. Two sets are considered same if they contain same points.

Input:
The first line of input contains two integers N, the number of hills and prime number p. The next N lines contains the height of the hills.

Output:
Print maximum possible size of Beautiful Set possible.

Constraints:
2 ≤ N ≤ 105
1 ≤ hi ≤ 1018
2 < p < 105
All the given hi are such that hi % p != 0

Sample Input

```5 5
2 3 4 22 33```
Sample Output

`2`
Explanation

The two possible Beautiful Sets are {2, 22} and {3, 33}. Here 4 can’t be in any beautiful set because (4 * 4) % 5 = 1. Also 2 and 3 can’t be in any beautiful set because (2 * 3) % 5 = 1. Also note that (2 * 22) % 5 != 1 and (3 * 33) % 5 != 1.

n,p=map(int,raw_input().split())
r=map(int,raw_input().split())
count=0
k=[]
for i in range(n):
if((r[i]*r[i])%p!=1):
k.append(r[i])
for i in range(len(k)):
for j in range(len(k)):
if((k[i]*k[j])%p!=1):
if(i!=j):
#print k[i],k[j]
count+=1
print count/2

I am getting very frustrated due to  recent failure don’t know how to deal with it,

first one,

applied GATE exam but i am not able to prepare for that on top of it pressure from aunts and uncle to crack it dont know what will happen.

second one,

not getting into good company,getting rejected by lots lots of companies previously i used to clear aptitude exm but now that also not happening lots of companies rejected me

let me list them accordingly,

1->thorougood

was not preppared with proper memory arragment in operating system,threads was not prepared.

2->morgenstanly

was not prepared with basic c++ concept – oops concept,function pointer,and database was not cleared.

3-> cisco

couldnt clear first round

4-> akamai

couldnt clear first round

5->unisis

they were worst they made us wait till late evening and rejected.

6->tesco

coudnt write because of unisis.

7->redbus

couldnt clear thier written test.

8->cisco

they took only selected persons with cgpa between  8.5-9 i was above it so missed it.

9 ->akamai testing

i coundlnt write it because i was stuck with pavit bus .these assholes couldnt reach to banglore at right time.

10->Direct i

i wrote it i cleared it with 3rd rank . but they never came back again to take interwiew.Dont know y they did it like that.(still waiting for them).

11->knowlarity

i knew how to code but thier compiler was too much fucked up that it coudlnt display the output for the code we wrote.

it was for consultant job so i was not interested (now regreting it).

13->juniper

i wrote it cleared it but just because of 1mark they were planning to give me testing job so I rejected it.

14->SAP labs

my dream company wrote it properly but due to negligency of placement department the labs which CSE people were seated were not considered for evaluation.( was depressed)

15->oracle

their paper was so lengthy that i wasnt able to read them in one sitting somehow i wrote it but couldnt clear it.

16->Microsoft GTSE

cleared first round in group discussion was not selected due to lack of interest.I was in an urge of crying….

17->yahoo

was not prepared well and lost this one also….

18->huewie

cleared 1st round,cleared second round ,but in third round was rejected because i didnt knew much about pointers…dead by now

19->SAPLABS

again they came today now i did well hoping to clear this.too much desparate to get this.please god save me………please please

still lots to come hope i dont loose hope.