Kuldeep is a member of UDC. Ritam wants to learn dance from Kuldeep. Kuldeep gives Ritam a sequence of steps. He has to perform all the substrings of the steps. But he faces a problem where the substring of the string is an even number. Find out the number of step sequences where he faces problems. The substrings can have leading zeros. You have to solve the problem for “t” test cases.

First line of input consists of “t” denoting the number of test cases. Following “t” lines consist of a string containing digits between 0 and 9.

You have to output one number denoting the number of substrings which are even.

Constraints:

1 <= t <= 1e5

1 <= length of string <= 1e5

Sum of length of strings over all test cases does not exceed 1e5.

In this task you have to calculate the number of substrings which are even.A substring is a continuous subsequence of string for example (if s=“abcde” then “abc”,”cde”,”bcd” are substrings but “ac”,”acd” are not substrings of s).

As we know the even number has an even digit at last. So we have to traverse the string and if we found an even digit then all the substring which have that digit in the end will be considered in the answer ( for example let s=”123456” and we are at 5th position (zero based indexing) where the character is 6 then all 123456, 23456,3456,456,56,6 will be counted in the answer) hence if we are at position i (zero based indexing) from the start then there will be i+1 numbers which have s[i] digit at the end.

So we will get our answer by simply adding the (i+1) to our answer at every such position i where s[i] is a multiple of 2.So the answer to our example will be 2 + 4 + 6 = 12.

// code by Aniket Sukhija 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long

void solve(){
    string s; cin>>s;
    ll n = s.size();
    ll ans = 0;
    for(int i=0;i<n;i++){
        if(int(s[i] - '0')%2==0){
            ans += (i+1);
        }
    }
    cout<<ans<<endl;
    return;
}
 
int main(){
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

You are participating in a game organized by seniors. What you need to do in this game is that you have to find some objects which are hidden all around the campus. For the sake of simplicity we assume that the campus is a simple straight line. Now you have been given “n” objects. Now you ask a particular guy Paras for help who decides to help you out. To make it more fun, he decides not to tell you all the answers correctly. You ask him about the item “m” and he answers the query as l, r, which means that the item is present between l’th and r’th position in the campus. You need to find out whether he lied or is telling the truth.

Input:

In the first line you have given n, the number of elements in the array 1<=n<=1e5.

In the next line you have given n elements of the array. Each element is unique and in the range [0,1e9].

In the next line you have given q ,number of queries which will be asked 1<=q<=1e5.

In the next q lines you have given l,r and m. (1<=l<=r<=n and m is in the range [0,1e9]

Output:

You have to print the answer of q queries in q lines where ith line has the answer of ith query.

In this task you have given an array (let the array be a) with distinct digits and you need to tell whether a particular number lies in (a[l],a[l+1],........,a[r-1],a[r]) or not.

So from problem it is clear that you have to store the position of a particular number but a vector is not feasible here because the range of numbers is 10^9 and we cannot allocate that much memory hence we are using std::map for hashing in this problem.Let suppose the position of the number is k then if both l and r is less than k (1....l………r….k…….n) or both l and r are greater than k (1….k…l….r…..n) then the answer is no otherwise the answer will always be yes because now the number lies between the lth and the rth index i.e. (1……l….k….r…….n) k lies between l and r.

//Code by Ritam
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define vi vector<int>
#define vll vector<ll>
#define tests int t; cin >> t; while(t--)
#define pb push_back
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n; cin >> n;
	map<ll, int> m;
	for(int i = 0; i < n; i++) {
		ll x; cin >> x;
		m[x] = i+1;
	}
	tests {
		int l, r; ll x; cin >> l >> r >> x;
		if(l <= m[x] && m[x] <= r) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

Best friends Suri and Kanishk always shared their snacks with each other. One day they had a fight because Kanishk asked for a party from Suri and they decided to eat whatever snacks they got all by themselves. But, the decision wasn’t simple. They had to play a game against each other to decide who gets the snack. If the game results in a draw, they share the snacks for that day. The game goes like this: You are their common friend and you give a number “n”, Kanishk and Suri guess the prime number just greater than or equal to “n”. Note that the answers from Kanishk and Suri might be the same. You have to tell who is the winner or say if the game resulted in a draw. There will be several test cases for each test.

Input

First line contains “t”, the number of test cases, 1 <= t <= 1e6. Then “t” lines follow.

Each line contains n, a, and b, 1 <= n <= a, b <= 1e7. It is guaranteed that a prime number greater than or equal to n exists within the range of the input. "a" and "b" denote guesses from Kanishk and Suri respectively.

Output

For each test, return whether Kanishk or Suri won the game or if it is a draw. Note that draw in this case means either both of them have answered the query correctly or both have answered it incorrectly.

In this problem you have n,a,b and you need to check whether a or b are the prime numbers which are just greater than n or not. Since the range of n is upto 1e7 so we cannot use brute force to calculate prime numbers. In order to solve this problem we will use sieve of eratosthenes.

Sieve of eratosthenes can find all the prime numbers upto n in just O(nlog(log(n))) time. Now in this question we need to first pre calculate the prime numbers till 1e7 then after that we will calculate the answer for every number till n. Suppose A= [a1,a2,p1,a3,a4,a5,p2] where ai as composite and pi as prime number so for a3,a4,a5and p2 the ans will be p2 and similarly for a1,a2 and p1 answer will be p1. To calculate the answer we will traverse the array from the last, if we found a prime number we will assign the ans of that number as the number itself else we will assign the ans of the next number to the present number.

for example in A if we traverse form the last the answer of p2 will be p2 now for a5 the answer will be p2 similarly for a4 the answer will be the answer of a5 and it goes on like that. One can also store the prime numbers that we found using Sieve in an array and later use binary search on that array to find a number just greater than or equal to n and use that result for the queries.

//Code by Ritam
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define vi vector<int>
#define vll vector<ll>
#define tests int t; cin >> t; while(t--)
#define pb push_back
using namespace std;

const ll N = 1e7+1;
vll sieve(N, 1), lp(N, -1);

void Sieve() {
	sieve[1] = sieve[0] = 0;
	for(ll i = 2; i*i <= N; i++)
		if(sieve[i])
			for(ll j = i*i; j < N; j += i)
				sieve[j] = 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	Sieve();
	for(ll i = N-2; i >= 1; i--) {
		if(sieve[i]) lp[i] = i;
		else lp[i] = lp[i+1];
	}
	tests {
		ll n, a, b; cin >> n >> a >> b;
		if(lp[n] == a && lp[n] == b) {
			cout << "DRAW\n";
		} else if(lp[n] != a && lp[n] != b) {
			cout << "DRAW\n";
		} else if(lp[n] == a) {
			cout << "KANISHK\n";
		} else {
			cout << "SURI\n";
		}
	}
	return 0;
}

Two friends Yash & Manan sitting in A10 building of IIT Mandi waiting for their CO class decided to play a simple game of math. A random number n is chosen by them. For the position of set odd bits in n Manan gets a score and for set even bits, Yash gets a score to find who wins the game for some given value of n. In case of a draw simply print "Draw".

set bit at index i indicates "1" is present at ith bit (LSB is the 1st bit and MSB is the last bit) odd bits refer to the bits at odd positions

Example in number 26 — (11010) 0,0,1 at 1st,3rd and 5th position respectively are the odd bits.

Input:

The first line of the input contains a single integer t (1<=t<=1e5), given the number of test cases.

The second line of the input contains only a single integer n (2<=n<=1e5).

Output:

Display the name of the person who wins the game.

Sample Input:

3

2

5

3

Sample Output:

Yash

Manan

Draw

This problem is based on bit manipulation. You can refer to this link to read what bit manipulation is. In the given problem you just need to add the set bits which are at the odd position of its binary representation from least significant bit to the score of Manan and add the set bits at even position to the score of Yash.

To get the least significant bit we will use (%2) now add the LSB to score of the player. We will maintain a pointer which tells whether the bit is at odd position or even position and according to that we will update the score of each player.After obtaining the LSB we will divide the number by 2 to get the next bit and also update the pointer.

Example: let number be 13, its binary representation is 1101.

step 1: 1 is added to Manan's Score, number is divided by 2 it becomes (110),pointer is updated to yash.

step 2: 0 is added to Yash's Score, number is divided by 2 it becomes (11), pointer is changed back to Manan.

step 3: 1 is added to Manan's Score, number is divided by 2 it becomes (1), pointer is changed to yash.

step 4: 1 is added to Yash's Score, number is divided by 2 it becomes 0 and so the Game Ends.

Score of Manan is 2 and Score of Yash is 1 so winner is Manan.

// code by Aniket Sukhija
#include<bits/stdc++.h>
using namespace std;
 
void solve(){
    int n; cin>>n;
    int oddbits = 0;
    int evenbits = 0;
    bool checker = true;
    while(n!=0){
        if(checker) oddbits += n%2;
        else evenbits += n%2;
        n/=2;
        checker = !checker;
    }
    if(oddbits>evenbits){
        cout<<"Manan"<<endl;
    } else if(oddbits<evenbits){
        cout<<"Yash"<<endl;
    } else cout<<"Draw"<<endl;
    return;
}
 
int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Aniket is in Village Square at 11 PM. As everyone knows it is mandatory on campus to reach your room by midnight. Now Aniket lives in a far away hostel B17 and he also has two friends one in B16 and one in B21, he wants to meet his friends before he goes to his room but due to lack of time, he can only visit one friend. Calculate the number of ways in which he can go back to his room after visiting only 1 of his two friends given the whole campus is a rectangular grid of size (m*n). Village Square is located at (0,0) and the hostel B17 is located at some position (m,n) the hostel B16 and B21 come in the way at (x1,y1) and (x2,y2) respectively.

Input:

The first line of the input contains two integers m and n. The second line of the input contains 4 integers x1,y1 & x2,y2.

Output:

Display the number of ways in which Aniket can reach back to his hostel Note- (You have to consider the shortest path)

In this task we need to calculate the number of ways in which Aniket reaches the (m,n) point of the grid (of size m*n) by passing through only one of the points (x1,y1) or (x2,y2) in the grid through the shortest path. So at first , we need to know how to calculate the shortest path in grid from one point to another .Suppose we have grid of size m*n and we need to go from (0,0) to (m,n) .Then, the shortest path contains exactly (m+n) steps where there should be m down steps and n right steps. Here the number of ways will be (m+n)Cm or (m+n)Cn. We treat it like suppose we have (m+n) right steps now we have to choose m positions which we can turn to down steps so that we have exactly m down and n right steps.

Now we have two cases -

In the first case one of the points lie inside the area of the other one that means if we reach first point by going right and down steps we can still reach the 2nd point so to handle this case let first assume we visit the (x2,y2) from (0,0) which lie between (0,0) and (x1,y1) and from (x2,y2) we will reach to (m,n).It will also consider all those paths which include the point (x1,y1) along its way from (x2,y2) to (m,n) hence we need to subtract all these ways. Now let assume that we visit (x1,y1) instead of (x2,y2). If we consider all paths which lead us to (x1,y1) from (0,0) then it also contain the paths which visit (x2,y2) hence we need to subtract all those paths and then consider the number of ways in which we can go to (m,n) from (x1,y1).

In the second case once we reach one of the point then we cannot visit the second point so here the ways will be number of ways from (0,0) to the first point with the number of ways to reach (m,n) from the first point and number of ways from (0,0) to the second point with the number of ways to reach (m,n) from the second point.

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

long long fact(long long x){
    long long ans = 1;
    for(int i=1;i<=x;i++){
        ans *=i;
    }
    return ans;
}

long long nCr(long n,long x){
    long long ans = fact(n)/(fact(x)*fact(n-x));
    return ans;
}

void solve(){
    long long m,n; cin>>m>>n;
    long long x1,y1,x2,y2; 
    cin>>x1>>y1>>x2>>y2;
    long long ans = 0;
    // we will use pnc to find the total number of possible ways.
    if(x1-x2>=0 && y1-y2>=0){ // when (x2,y2) point lies between (0,0) and (x1,y1)
        long long w1 = nCr(x2+y2,x2);
        long long w2 = nCr((x1+y1) -(x2+y2),x1-x2);
        long long w3 = nCr(m+n - (x1+y1),m-x1);
        long long w4 = nCr(x1+y1,x1);
        long long w5 = nCr(m+n,m);
        long long w6 = nCr(m+n- (x2+y2),m-x2);
        ans += (w1*(w6-(w2*w3)));
        ans += (w3*(w4-(w1*w2)));
    } else if(x1-x2<=0 && y1-y2<=0){ // when (x1,y1) point lies between (0,0) and (x2,y2)
        swap(x1,x2);
        swap(y1,y2);
        long long w1 = nCr(x2+y2,x2);
        long long w2 = nCr((x1+y1) -(x2+y2),x1-x2);
        long long w3 = nCr(m+n - (x1+y1),m-x1);
        long long w4 = nCr(x1+y1,x1);
        long long w5 = nCr(m+n,m);
        long long w6 = nCr(m+n- (x2+y2),m-x2);
        ans += w1*(w6-(w2*w3));
        ans += w3*(w4-(w1*w2));
    }
    else { // when (x1,y1) and (x2,y2) does not come in each other's path.
        ans += nCr(x1+y1,x1) * nCr(m+n - (x1+y1),m-x1);
        ans += nCr(x2+y2,x2) * nCr(m+n - (x2+y2),m-x2);
    }

    cout<<ans<<endl;
    return;
}
 
 
int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

Vaibhav was crying in the corner of his room because his rating had dropped again. He notes down his rating changes on Codeforces after every contest. He wants to find out the index of the first rating drop in the array of rating changes for every subarray of size k. He needs your help to do so because his eyes are all watery with tears.

Input:

The first line of the test case consists of two integers n,k(1<k<n<1e5).-> number of elements in array and size of subarray.

The second line consists of n integers seperated by a space.

Output:

Output consists of n-k+1 elements which are indexes of first negative element in the array for

that subarray of size k. (Use 1 based indexing) if no negative element is present in subarray output -1 for that subarray.

In this task you have given an array which have negative and positive integers and in every subarray of length k such as {a[l],a[l+1]....a[r]} where r-l+1=k you have to tell the index of first negative integer which occur in that subarray from l.

To understand this particular solution of the problem you should have some knowledge of queues .To traverse all the subarray in O(n) we will traverse the first subarray of length k and push all the index of negative integer in the queue which occur in that subarray then we will keep pointer at the first (l) and last (r) position of the subarray on adding 1 to both l and r we can move to the next subarray. So when ever we add 1 to l and r we just need to take care of v[l] and v[r+1] because the rest of the element are same in the subarray

for example in (v[0],v[1],[2],v[3],v[4]) if we take subarrays of length 3 then those array will be (v[0],v[1],v[2]),(v[1],v[2],v[3]) and (v[2],v[3],v[4]) here we can observe that in the first subarray (l,r) = (0,2) in the next subarray (l,r) = (1,3) and in the final subarray (l,r) = (2,4).

Hence We will print the top of queue if the queue is not empty for every subarray (-1 if it is empty) and while shifting l and r by 1 if v[l]<0 then we will pop the top from the queue because it is the first negative element which occur during the traverse of the array hence it is on the top and since the next subarrays does not contain this element so we delete it and if v[r+1]<0 then we will push the index it at the end of the queue so that we have all negative integer in the queue which is present in (v[l+1],v[l+1],v[l+2]......v[r+1]).

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

int32_t main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    queue<int> q;
    for (int i = 0; i < k; ++i) {
        if (v[i] < 0) q.push(i);
    }
    for (int l = 0, r = k - 1; r < n; ++l, ++r) {
        if (!q.empty()) {
            cout << q.front() + 1 << " ";
        } else {
            cout << -1 << " ";
        }
        if (v[l] < 0) q.pop();
        if (r + 1 < n && v[r + 1] < 0) q.push(r + 1);
    }
    cout << endl;
}

Khushboo gave 2 binary strings A and B to Rijul and gave the task to form a new binary string C from A and B. In every instance Rijul has 2 choices, to either pick a character from A or B and concatenate them in C. We have to minimize the inversions in the binary string C. An inversion in a binary string S is a pair of indices (i,j) such that i<j and Si = '1', Sj = '0'.

For example, the string S= "01010" contains 3 inversions : (2,3), (2,5), (4,5). As it's been a while since Rijul has participated in contests or practised problems, she isn’t able to solve the problem. Help her solve this.

Constraints:-

1 <= len(A) <= 1000

1 <= len(B) <= 1000

Input:

The first line of the test case contains string A and the second line contains the string B

Output:

output a single Integer i.e. the number of inversions in the final string after merging both the strings.

At first, let’s define when there will be an inversion if we have a binary string.So as we know, if a[i]>a[j] and i<j then there is an inversion. In binary string since we have just 0’s and 1’s so if we have a 1 before zero then for every zero after that one will contribute 1 inversion for example {0010001} so here the one at 3rd position have 3 zeros after it so it will contribute 3 inversion count.We can also take this in another way like number of ones before a zero will give the inversion count by that zero for example 0010001 here the zero at 4th position have one 1 before it so it will contribute 1 inversion count similarly zero at 5th and 6th position have one 1 before them so they will contribute 1 inversion count each. So at first we will pre calculate the number of ones which are at ith position or before the ith position in both of the strings. Now we can try to solve the problem using dynamic programming. We define an array dp such that dp[i][j] gives us the minimum inversion count if we take first i elements from the first string and first j elements from the 2nd string in string C. For transition we will make some cases like if we have only 0 as our choice to select from A and B string then we will take the minimum among those two cases

For example if we have to calculate dp[i][j] and we know its all previous state then if we choose the 0 which is at a[i] position then the inversion counts will be the number of 1’s in a before a[i-1] position plus the number of 1’s before b[j] position + dp[i-1][j] (which will tell us minimum inversion if we take i-1 element from string A and j elements from string B)

In second case when we have both one then dp[i][j]=min(dp[i-1][j],dp[i][j-1])

In the third case when we have zero in string A and 1 in string B then the transition will be minimum of when we choose the zero from string A but we already consider the first j element from the second string or when we choose one from the second string but we already choose first i element from the first string dp[i][j]=min(dp[i-1][j]+(number of one before i)+ number of one before j,dp[i][j-1]).

In the fourth case it is similar to the third one where we have 1 in A string and 0 in string B. The final answer will hence be dp[n-1][m-1] where n is the size of the first string and m is the size of the second string. This can solved both using a recursive approach as well as an iterative approach.

// Code by Ritam
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define vi vector<int>
#define vll vector<ll>
#define tests int t; cin >> t; while(t--)
#define pb push_back
using namespace std;

string s, t;
int n, m;
int dp[1005][1005];

int getAns(int i = 0, int j = 0, int ones = 0) {
	if(i == n && j == m) return 0;
	if(dp[i][j] != -1) return dp[i][j];
	int ansS = INT_MAX, ansT = INT_MAX;
	if(i < n) ansS = (s[i] == '0')*ones+getAns(i+1, j, ones+(s[i] == '1'));
	if(j < m) ansT = (t[j] == '0')*ones+getAns(i, j+1, ones+(t[j] == '1'));
	return dp[i][j] = min(ansS, ansT);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	memset(dp, -1, sizeof(dp));
	cin >> s >> t;
	n = s.length(); m = t.length();
	cout << getAns() << "\n";
	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ITER iterator
#define rep(i, s, e) for (int i = s; i < e; i++)
#define brep(i, s, e) for (int i = s; i > e; i--)
#define all(x) x.begin(), x.end()
#define mem(x, y) memset(x, y, sizeof(x))
#define ones __builtin_popcount
#define fast                          \
    std::ios::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
const int intmax = 2147483647;
const int intmin = -2147483648;
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * (b / gcd(a, b)))
const int mod = 1000000007;
const int mod2 = 998244353;
#define inf 1000000000000000000
#define check(n, pos) (n & (1 << pos))
#define sett(n, pos) (n | (1 << pos))
#define unset(n, pos) (n & ~(1 << pos))
#define add(a, b) (((a % mod) + (b % mod) + mod) % mod)
#define sub(a, b) (((a % mod) - (b % mod) + mod) % mod)
#define mul(a, b) (((a % mod) * (b % mod) + mod) % mod)
#define fd(n) fixed << setprecision(n)
int main()
{
    fast;
    int t = 1;
    while (t--)
    {
        string x, y;
        cin >> x >> y;
        int n = x.length();
        int m = y.length();
        vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, inf));
        ll pref1[n + 1][2];
        ll pref2[m + 1][2];
        for (int j = 0; j <= n; j++)
        {
            pref1[j][0] = 0;
            pref1[j][1] = 0;
        }
        for (int j = 0; j <= m; j++)
        {
            pref2[j][0] = 0;
            pref2[j][1] = 0;
        }
        ll cnt0 = 0;
        ll cnt1 = 0;
        for (int j = 1; j <= n; j++)
        {
            if (x[j - 1] == '1')
            {
                cnt1++;
            }
            else
            {
                cnt0++;
            }
            pref1[j][1] = cnt1;
            pref1[j][0] = cnt0;
        }
        cnt0 = 0;
        cnt1 = 0;
        for (int j = 1; j <= m; j++)
        {
            if (y[j - 1] == '1')
            {
                cnt1++;
            }
            else
            {
                cnt0++;
            }
            pref2[j][1] = cnt1;
            pref2[j][0] = cnt0;
        }
        dp[0][0] = 0;
        ll s = 0;
        for (int i = 1; i <= n; i++)
        {
            if (x[i - 1] == '0')
            {
                s += pref1[i][1];
            }
            dp[i][0] = s;
        }
        s = 0;
        for (int i = 1; i <= m; i++)
        {
            if (y[i - 1] == '0')
            {
                s += pref2[i][1];
            }
            dp[0][i] = s;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                ll val1 = 0;
                ll val2 = 0;
                if (x[i - 1] == '0')
                {
                    val1 = pref1[i - 1][1] + pref2[j][1];
                }
                if (y[j - 1] == '0')
                {
                    val2 = pref1[i][1] + pref2[j - 1][1];
                }
                dp[i][j] = min(dp[i - 1][j] + val1, dp[i][j - 1] + val2);
            }
        }
        cout << dp[n][m] << "\n";
    }
    return 0;
}