Coding is Fun

Problem Statement:

There are 3 types of letters available. They are A, B and C. You are given the frequencies of them. You have to make a word with all of them but have to maintain one condition that letter A and B will not be adjacent to each other. How many different words you can make maintaining the condition.

For example, if the frequencies of letter A, B and C are 1, 1 and 2, the answer will be 6. The words are ACCB, ACBC, CACB, BCAC, BCCA and CBCA.

Input

First line of input contains the number of test cases T (1<= T <= 100000). Next T lines describe the case. Each case contains three integers x, y and z where x denotes the frequency of A, y denotes the frequency of B and z denotes the frequency of C (0 <= x, y, z <= 100000 && min(x, y) < 3 && (x + y + z) ≥ 1).

Output

For each test case, output a single line contains “Case X: Y” without any quote where X denotes the number of test cases and Y denotes the answer of the problem. Answer could be very large so output the answer modulo 1000000007.

Sample Input / Output:

2
1 1 1
1 1 2

Case 1: 2

Case 2: 6

Solution:

First Hint is min(x, y) < 3

So, we can handle the cases of unique string by hand.

Here Is the code of Mine ( Solution Description will be updated Later ):

/*input
2
1 1 1
1 1 2
*/

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

#define mx 1000005
#define ll long long
#define MOD 1000000007
ll fact[mx], inv[mx];
ll nCr(int n, int r)
{
 return  1ll * (fact[n] * inv[r] % MOD) * inv[n-r] % MOD;
} 
ll bigmod(ll a, ll p)
{
 if(p==0) return 1;
 if(p&1) return a * bigmod(a, p-1) % MOD;
 ll mo = bigmod(a, p/2);
 return mo * mo % MOD;
}
ll val(int b, int c)
{
 return (1ll * (fact[b+c] * inv[b] % MOD) * inv[c]) % MOD; 
}
int fun0(int a, int b, int c)
{
 return val(b, c);
}
ll fun1(int a, int b, int c)
{
 int n = a + b + c;
 ll ans = 0;
 if(n >= 3){
  if(c >= 2) ans = (ans + 1ll * (n-3+1) * val(b, c-2) % MOD) % MOD;
  if(c >= 1) ans = (ans + 2ll * val(b, c-1) % MOD) % MOD;
 }
 return ans % MOD;
}

ll fun2(int a, int b, int c)
{
 int n = a + b + c;
 ll ans = 0;
 if(n >= 4){
  if(c >= 2) ans = (ans + 1ll * (n-4+1) * val(b, c-2) % MOD) % MOD;
  if(c >= 1) ans = (ans + 2ll * val(b, c-1) % MOD) % MOD;
  // hi
  if(c >= 2) ans = (ans + val(c-2, b)) % MOD;
 }
 if(n >= 5){
  if(c >= 3) ans = (ans + 1ll * (n-5+1) * val(b, c-3) % MOD) % MOD;
  if(c >= 2) ans = (ans + 2ll * val(b, c-2) % MOD) % MOD;
 }
 ll k = n-6+1;
 k = (k * (k+1) / 2 ) % MOD; 
 if(n >= 6){
  if(c >= 4) ans = (ans + k * val(b, c-4) % MOD) % MOD;
  if(c >= 3) ans = (ans + 2ll * (n-5+1) * val(b, c-3) % MOD) % MOD;
 }
 return ans;
}
int main()
{
 fact[0] = inv[0] = 1;
 for(int i = 1; i<mx; i++)
 {
  fact[i] = fact[i-1] * i % MOD;
  inv[i] = inv[i-1] * bigmod(i, MOD-2) % MOD;
 }
 // cout << nCr(5, 2) << endl;

 int t, tst = 1;
 scanf("%d", &t);
 while(t--)
 {
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  if(a > b) swap(a, b);
  ll ans = 0;
  if(a==0) ans = fun0(a, b, c);
  else if(a==1) ans = fun1(a, b, c);
  else ans = fun2(a, b, c);
  printf("Case %d: %lld\n", tst++, ans);
 }
 return 0;
}

**Happy Coding**

Problem Statement:

In the year 3333, earthly scientists discovered a massive star has blast in a nearby galaxy. Dangerous radiations from the explosion are going to hit planet earth very soon. In response, Planetary Protection Unit (PPU) has set-up N Radiation Absorbing Device (RAD) through-out the Earth surface and labeled them from 1 to N. Since, the radiations are coming from very far and also due to the continuous rotation of earth and various other factors, scientists could not calculate exactly from which direction the radiation will hit the planet and they also assume each radiation wave’s wavefront is a straight line of infinity length. The planet Earth is considered as a 2-D grid where, each RAD occupies positive integer coordinates. The first properly functioning RADs that are hit by a radiation wave absorb it.

Your uncle, the chief of the PPU has noticed that there are some RADs which are not necessary at all, that is – either they are malfunctioning or they will never get hit by any radiation wave from any direction. And he decided to disable them to save power (RADs require a lot of energy). Being the chief, he has access to the Status Key of the RADs and their 2D coordinates.

A Status Key is a binary string of length N containing 0s and 1s only. If the X’th character of the string is a 0, it denotes that the RAD labeled X is malfunctioning or 1 otherwise.

Consider the following example – Status Key = 1101

Earth surface is represented as a 2-D plane and the labeled circles are RADs.

The radiation wave is entering in a direction parallel to Y-axis. In this scenario, first properly functioning RADs to be hit by the wave are 1 and 2. So, the RADs that need to be disabled are labeled 3 and 4..

Because you are the most talented programmer your uncle has ever seen, he hired you to make a program for PPU that will find out the RADs that are required to be disabled. Provided, the radiation may come from any direction and will always originate from outside the grid. Also, each RAD has different coordinates.

Input

First line of input contains a single integer N (3 <= N <= 1000000) denoting the number of RADs. Second line contains a binary string S of N characters denoting the Status Key. Then follows N lines, i’th of the next lines contains two positive integers Xi and Yi (0 <= Xi, Yi <= 2000) denoting the coordinates of RAD labeled i.

Output

In a single line, print the labels (separated by space) of the RADs that are to be disabled in ascending order. If no such RADs are found, print -1.

Samples Input :

10 1110111100

1 1

2 1

9 1

4 4

5 9

2 2

8 2

5 8

5 5

3 3

Sample Output:

4 6 7 8 9 10

Big Problem Statement Haah!

Short description :
You have n points. Some are active and others are inactive. There are flow of rays from every direction. If a ray passes throw a point than the ray will be received by the point only if the point is active and the ray will not farther traverse. Now you have to find the points which never can receive a ray.
So this is like a rubber band and pin problem. So this lead us to Convex hull.
If you don't know it read it from https://en.wikipedia.org/wiki/Convex_hull .
So find the convex hull with the coolinear points added (without active points).

Then the answer will be the index numbers of not used points in the convex hull.

The following code gives the desired answer:

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

struct point{
 int x;
 int y;
 point(){};
 point(int x, int y) : x(x), y(y) {}
 bool operator < (const point &p) const{
  return x<p.x || (x==p.x && y < p.y);
 }
};

int cross(point O, point A, point B)
{
 return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

vector<point> convex_hull(vector<point> P)
{
 int n = P.size(), k = 0;
 vector<point> H(2*n);
 sort(P.begin(), P.end());
 for(int i = 0; i<n; i++)
 {
  while( k>=2 && cross(H[k-2], H[k-1], P[i]) < 0) k--;
  H[k++] = P[i];
 }

 for(int i = n-2, t = k+1; i>=0; i--)
 {
  while(k>=t && cross(H[k-2], H[k-1], P[i]) < 0) k--;
  H[k++] = P[i];
 }
 H.resize(k-1);
 return H;
}
char st[1000007];
int main()
{
 int n;
 scanf("%d", &n);
 scanf("%s", st);
 vector<point> vt;
 map<point, int> mp;
 for(int i = 1; i<=n; i++)
 {
  point x;
  scanf("%d %d", &x.x, &x.y);
  if(st[i-1]=='1'){
   vt.push_back(x);
  }
  mp[x] = i;
 }
 auto hull = convex_hull(vt);
 for(auto x : hull)
  mp[x] = 0;
 vector<int> ans;
 for(auto x : mp)
 {
  if(x.second) ans.push_back(x.second);
 }
 sort(ans.begin(), ans.end());
 if(ans.empty()) printf("-1\n");
 else{
  printf("%d", ans[0]);
  for(int i = 1; i<ans.size(); i++)
   printf(" %d", ans[i]);
  printf("\n");
 }
 return 0;
}

**Happy_Coding**

Coding is Fun

Friday, December 15, 2017

Comilla University CSE Fiesta 2017 - D. Unique String

Input

Output

Comilla University CSE Fiesta 2017 - G - RAD!

Input

Output

Samples Input :

10

1110111100

1 1

2 1

9 1

4 4

5 9

2 2

8 2

5 8

5 5

3 3

4 6 7 8 9 10

Comilla University CSE Fiesta 2017 - D. Unique String

Search This Blog