TCS 2020 MOCKVITA

130 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define lld long long int

lld gcd(lld a, lld b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t;
    cin>>t;
    //t=1;
    while(t--)
    {
        int n;
        cin>>n;
        int arr[n+1];
        for(int i=1;i<=n;i++)
        cin>>arr[i];

        set <lld> v;
        for(int i=1;i<=n;i++)
        {
            int val=arr[i],cnt=1,j=i;
            while(val!=i)
            {
                val=arr[arr[j]];
                cnt++;
                j=arr[j];
            }
            v.insert(cnt);
        }
        lld ans=*v.begin();

        for(auto it=v.begin();it!=v.end();it++)
        {
            lld as=*it;
            ans = (((as * ans)) / (gcd(as, ans)));
        }
        cout<<ans<<"\n";
    }
}

This gave me TLE. Any reason. (Question E)

131

I guess because of this while loop.You can simply use Disjoint Set Union, instead of finding “cnt” for each element.

132

In worst case it will be O(n^2). So, this should be accepted

133

Test Cases 1 <= t <= 10 and 1 <= n <= 1e4. O(t * n * n) will be a TLE then.

134

A. Swayamwar

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

int main() {
    int n; cin >> n;
    string s1, s2; cin >> s1 >> s2;
    int m=0, r=0;
    for(char c:s2) {
        if(c == 'm') m++;
        else r++;
    }
    for(char c:s1) {
        if(c == 'm') {
            if(m) m--;
            else break;
        } else {
            if(r) r--;
            else break;
        }
    }
    cout << m+r;
    return 0;
}

B. Digit Pairs

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

int main() {
    int n; cin >> n;
    int temp, small, large, num;
    unordered_map<int, int> odd, even;
    for(int i=0; i<n; i++) {
        cin >> temp;
        small=10, large=0;
        while(temp > 0) {
            small = min(small, temp%10);
            large = max(large, temp%10);
            temp /= 10;
        }
        num = large*11 + small*7;
        if(num > 99) num = num%100;
        num /= 10;
        if(i & 1) odd[num]++;
        else even[num]++;
    }
    int ans = 0;
    int pairs[10] = {0};
    for(auto x:odd) pairs[x.first] += min(x.second-1, 2);
    for(auto x:even) pairs[x.first] += min(x.second-1, 2);
    for(int x:pairs) ans += min(2, x);
    cout << ans;
    return 0;
}

C. Dole Out Cadbury

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

int main() {
    int p,q,r,s; cin>>p>>q>>r>>s;
    int ans = 0;
    for(int i=p; i<=q; i++) {
        for(int j=r; j<=s; j++) {
            int a = max(i, j), b = min(i, j);
            while(a>0 && b>0) {
                swap(a, b);
                int x = b / a;
                ans += x;
                b -= a*x;
            }
        }
    }
    cout << ans;
    return 0;
}

D. Petrol Pump

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

int subset(vector<int> &arr, int s) {
    int n = arr.size();
    bool dp[n+1][s+1];
    for(int i=0; i<=s; i++) dp[0][i] = false;
    for(int i=0; i<=n; i++) dp[i][0] = true;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=s; j++) {
            dp[i][j] = dp[i-1][j];
            if(arr[i-1] <= j) dp[i][j] = dp[i][j] || dp[i-1][j-arr[i-1]];
        }
    }
    int i=s;
    for(; i>=0; i--) {
        if(dp[n][i]) break;
    }
    return i;
}

int main() {
    vector<int> arr;
    int sum=0;
    string inp, t;
    getline(cin, inp);
    stringstream ss(inp);
    while(ss >> t) {
        int n = stoi(t);
        arr.push_back(n);
        sum += n;
    }
    int ans = subset(arr, sum/2);
    cout << max(ans, sum-ans);
    return 0;
}

E. Grooving Monkeys

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

int Find(int i, int *Parent) {
    if(Parent[i] != i) Parent[i] = Find(Parent[i], Parent);
    return Parent[i];
}

void Union(int i, int temp, int *Rank, int *Parent) {
    int x = Find(i, Parent);
    int y = Find(temp, Parent);
    if(Rank[x] < Rank[y]) Parent[x] = Parent[y];
    else if(Rank[x] > Rank[y]) Parent[y] = Parent[x];
    else {
        Parent[y] = Parent[x];
        Rank[x]++;
    }
}

signed main() {
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        int temp;
        int Rank[n], Parent[n];
        for(int i=0; i<n; i++) Rank[i] = 0;
        for(int i=0; i<n; i++) Parent[i] = i;
        for(int i=1; i<=n; i++) {
            cin >> temp;
            Union(i-1, temp-1, Rank, Parent);
        }
      	for(int i=0; i<n; i++) Find(i, Parent);
        unordered_map<int, int> freq;
        for(int p:Parent) freq[p]++;
        unordered_set<int> s;
        for(auto x:freq) s.insert(x.second);
        vector<int> v;
        for(int x:s) v.push_back(x);
        int l=v[0];
        for(int i=1; i<(int)v.size(); i++) {
            l = (v[i]*l) / (__gcd(v[i], l));
        }
        cout << l << endl;
    }
    return 0;
}

F. Death Battle

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

int ncr[105][105];

void fill_ncr() {
    for(int n=1; n<105; n++) {ncr[n][1] = n; ncr[n][0] = 1;}
    for(int n=2; n<105; n++) {
        for(int r=2; r<105; r++) {
            ncr[n][r] = ncr[n-1][r-1] + ncr[n-1][r];
        }
    }
}

int pow(int x, int n) {
    int res = 1;
    while(n > 0) {
        if(n&1) {res = res*x; n--;}
        x=x*x; n=n/2;
    }
    return res;
}

void add(int &n1, int &d1, int n2, int d2) {
    n1 = (d2*n1 + d1*n2);
    d1 = (d1 * d2);
    int g = __gcd(n1, d1);
    n1 /= g; d1 /= g;
}

void mul(int &n1, int &d1, int n2, int d2) {
    n1 = (n1 * n2);
    d1 = (d1 * d2);
    int g = __gcd(n1, d1);
    n1 /= g; d1 /= g;
}

signed main() {
    fill_ncr();
    int t; cin >> t;
    while(t--) {
        int a,h,l1,l2,m,c; cin>>a>>h>>l1>>l2>>m>>c;
        int numerator = h - m*a;
        if(numerator <= 0) {cout<<"1/1\n"; continue;}
        if(numerator > m*c) {cout<<"RIP\n"; continue;}
        int p = ceil((float)numerator / c);
        int an=0, ad=1;
        for(; p<=m; p++) {
            int mn=1, md=1;
            mul(mn, md, ncr[m][p]*pow(l1, p), pow(l2, p));
            mul(mn, md, pow((l2-l1), (m-p)), pow(l2, (m-p)));
            add(an, ad, mn, md);
        }
        cout << an << "/" << ad << endl;
    }
    return 0;
}
3 Likes
135

But 1e9 can be done in 1 sec I guess?

136

I am not sure with the exact numbers, but I guess online judge’s can do up-to 1e6 in normal (or may be up-to 1e7 if there are only trivial operations inside loop or if compiler do some optimization on loops) or less from this if more complex operation are used ( like sqrt or doing arithmetic operations on really big numbers).

137

Dole Out Cadbary
My code

p = int(input())
q = int(input())
r = int(input())
s = int(input())
c = 0
for i in range(p, q+1):
    for j in range(r,s+1):
        a = [i,j]
        while(a[0] != 0):
            if(a[0] < a[1]):
                a[0], a[1] = a[1], a[0]
            a[0] = a[0]-a[1]
            c += 1
print(c)

I am getting TLE.
Please help

138

You are using three nested loops. Use recursion.

Here, to give you an idea how to use it :

ll ans = 0;

void recurse(ll x, ll y)
{
	if (x == y){
		ans++;
		return;
	}
	else if (x > y){
		if (y == 1){
			ans += x;
			return;
		}
		else{
			ans++;
			x = x - y;
			recurse(x, y);
		}
	}
	else if (y > x){
		if (x == 1){
			ans += y;
			return;
		}
		else{
			ans++;
			y = y - x;
			recurse(x, y);
		}
	}
}
139

Good work :slight_smile:. Clean code and good implementation for 5th.

140

Here is the solution of problem C in python3
P=int(input())
Q=int(input())
R=int(input())
S=int(input())
total=0
for i in range(P,Q+1):
for j in range(R,S+1):
a=max(i,j)
b=min(i,j)
while b!=1:
if a==b:
a=1
break
else:
d=a-b
a=max(d,b)
b=min(d,b)
total+=1
total+=a
print(total)

141

Hey, I used a 2D dp table. But I didn’t get to submit it due to login issues. This would work right?

int dp[1505][1505];
for (int i = 1; i <= 1500 ; i ++)
{
dp[1][i] = i;
dp[i][i] = 1;
}

for (int i = 1; i <= 1500 ; i ++)
dp[i][1] = i;

for (int i = 2 ; i <= 1500 ; i ++)
{
for (int j =2 ; j <= 1500 ; j ++)
{
if (i ==j )
continue;

    else if (i > j)
    dp[i][j] = 1 + dp[i - j][j];

    else
    dp[i][j] = 1 + dp[i][j-1];
}

}

142

Did you got AC??

143

Thanks sir @zappelectro, I am week in recursion right now :pensive: But your way is really good. I hope I will think like this soon.

144

Sir @zappelectro, I used recursion as you said, but still gets TLE,

code
Please tell me where I did wrong.

145

Sorry,What do you meant by AC ?

146

Accepted

147

//Try this c++14 code .Hope this will help you

#include <iostream>
#include <cmath>
using namespace std;
int pow(int b, int p)
{
    int result=1;
    for(int i=0;i<p;i++)
        result = result*b;
    return result;
}

int distance(int x, int y, int s)
{
    float time,d=pow(x,2)+pow(y,2);
    return time=sqrt(d)/s;
}

int main()
{
    int c,x,y,s,time;
    cout<<"enter number of cars passing through origin : ";
    cin>>c;
    int arr[c];
    for(int i=0;i<c;i++)
    {
        cout<<"Enter x : ";
        cin>>x;
        cout<<"Enter y : ";
        cin>>y;
        cout<<"Enter speed : ";
        cin>>s;
        arr[i]=distance(x,y,s);
    }
    int flag=0;
    for(int i=0;i<c;i++)
    {
        for(int j=i+1;j<c;j++)
        {
            if(arr[i]==arr[j])
                flag++;
        }
    }
    cout<<"\n"<<flag;
}
148

Just refer to this.

149

Can anyone send me the solution of 4th question of Mockvite 2 held on 17-18th july 2020
?