1. The duration of the contest is 2.5 hours and there will be 6 problems for you to solve in increasing order of difficulty.
2. Make sure you’ve registered before taking part in the contest or else you will not be eligible for prizes
3. The final decision for judgment will be taken by the committee members. No arguments will be entertained. Plagiarism will not be tolerated. If we suspect anyone of doing so they will be immediately eliminated from the contest.
4. Only Indian Participants are eligible for prizes.

1. The duration of the contest is 2 hours and there will be 6 problems for you to solve in increasing order of difficulty.
2. The supported languages are :-
   a. Python
   b. Java
   c. C++
   
3. There will be a separate contest for each language. You can take part in multiple contests, but in that case you won't be eligible to receive prizes for any of them.
4. Make sure you’ve registered before taking part in the contest or else your score will not be considered on the leaderboard
5. The scoring system revolves around the length of your code. The shorter the code the more points you get as long as your code passes all the required test cases. Tabs, newlines and spaces don't contribute to character count.
6. You can submit solutions as many times as you'd like, there are no penalties for incorrect submissions. Only your best correct submission will be considered.
7. The final decision for judgement will be taken by the committee members. No arguments will be entertained. Plagiarism will not be tolerated. If we suspect anyone of doing so they will be immediately eliminated from the contest.
8. Only Indian Participants are eligible for prizes.

We need to remove minimum number of beads such that any two neighbouring beads have different colour. Problem boils down to counting number of consecutive pairs of same coloured beads.

E.g. RBBGRR Here, ‘BB’ and ‘RR’ pairs have same coloured beads. After removal of 1 bead from each of the 2 pairs, final string becomes ‘RBGR’.

E.g. RBBB Here, ‘BB’ ( R BB B ) and ‘BB’ ( RB BB ) pairs have same coloured beads. After removal of 1 bead from each of the 2 pairs, final string becomes ‘RB’.

E.g. RBGGBRRRGBBR Here, number of pairs of same coloured beads are 4
(RB GG BRRRGBBR,
RBGGB RR RGBBR,
RBGGBR RR GBBR,
RBGGBRRRG BB R)

After removal of 1 bead from each of the 4 pairs, final string becomes ‘RBGBRGBR’

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

int main() {
	int noOfBeads; cin >> noOfBeads;
	string beads; cin >> beads;
	int sameColouredPairs = 0;
	for (int i = 0; i < noOfBeads - 1; i++)
		if (beads[i] == beads[i + 1])
			sameColouredPairs++;
	// remove 1 bead from each same coloured pairs
	int finalNoOfBeads = noOfBeads - sameColouredPairs;
	cout << finalNoOfBeads << endl;
	return 0;
}

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int noOfBeads = Integer.parseInt(sc.nextLine());
        String beads = sc.nextLine();
        int sameColouredPairs = 0;
        for(int i=0; i<noOfBeads-1; i++){
          if(beads.charAt(i) == beads.charAt(i+1)){
            sameColouredPairs++;
          }
        }
        // remove 1 bead from each same coloured pairs
        int finalNoOfBeads = noOfBeads-sameColouredPairs;
        System.out.println(finalNoOfBeads);
    }
}

noOfBeads = int(input())
beads = str(input())
sameColouredPairs = 0
for i in range(noOfBeads-1):
    if beads[i] == beads[i+1]:
        sameColouredPairs += 1
# remove 1 bead from each same coloured pairs
finalNoOfBeads = noOfBeads-sameColouredPairs
print(finalNoOfBeads)

#include<iostream>
char p, c; int a;
int main() {
	while (std::cin >> c)
		if (c > 64)
			a += c != p, p = c;
	std::cout << a;
}

import java.util.*;
public class Solution {
    public static void main(String[] a) {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt(),x=1,i;
        char[] c=s.next().toCharArray();
        for(i=1;i<n;i++)
            if(c[i]!=c[i-1])
                x++;
        System.out.println(x);     
    }
}

x=input
x()
s=x()
z=a=0
for i in s:
    if i != z:
        a += 1
    z=i
print(a)

The solution for this problem requires us to find 4 players that play at each location and check if their cost is within the budget.

We can only print “no” when the sum of the minimums of each position is more than B.
When (Sum of Cheapest GK, mid, defender, forward > B ) we print “no”.

We can create an array of size 4 to store the minimum cost for each position and then iterate over an array that stores the cost of the players and we can check to see if each player's cost is lesser than the minimum cost of a player in that position, thus we find all minimums in the cost array for each position.

We can simply total them and see if the sum is less than the budget given.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t; 
    for(int i = 0 ; i < t ; i++){
        int n , b; 
        cin >> n >> b;
        vector <int> cost(n) , m(4,100) , code(n);  
        for(int j = 0 ; j < n ; j++){
            cin >> cost[j];
        }
        for(int j = 0 ; j < n ; j++){
            cin >> code[j];
        }
        //assigning max values to m only because each of them will change  
        //when compared to a lower value from the cost vector or stay the same 
        //if the only cost for a certain position is 100
        for(int j = 0 ; j < n ; j++){
            if(m[code[j]] > cost[j] ){
                m[code[j]] = cost[j];
            }
        }
        if(m[0] + m[1] + m[2] + m[3] <= b){
            cout << "yes" << '\n';
        }else{
            cout << "no" << '\n';
        }
    }    
    return 0;
}

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static void main(String args[] ) throws Exception {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) 
        {
            int n=sc.nextInt();
            int b=sc.nextInt();
            int ar[]=new int[n];
            int p[]=new int[n];
            int mins[]={100,100,100,100};
            for(int i=0;i<n;i++)
            {
                ar[i]=sc.nextInt();
            
            }
            
            for(int i=0;i<n;i++)
            {
                p[i]=sc.nextInt();
            
            }
            
            
            for(int i=0;i<n;i++)
            {
                if(ar[i] < mins[p[i]]){
                    mins[p[i]] = ar[i];
                }
            }
            
            if(mins[0] + mins[1] + mins[2]+mins[3] <= b ){
                System.out.println("yes");
            }else{
                System.out.println("no");
            }
            
        }
    }
}

for i in range(int(input())):
    n, b = input().split(' ', 1)
    p = input().split()
    c = input().split()
    
    for x in range(int(n)):
        p[x] = int(p[x])
        c[x] = int(c[x])
    # f = []
    m = [100,100,100,100]
    for j in range(int(n)):
        # cj = c[j]
        if p[j] < m[c[j]]:
            m[c[j]] = p[j]

    if m[0] + m[1] + m[2] + m[3] <= int(b):
        print("yes")
    else:
        print("no")

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

int t, n, b, i, x;
int main()
{
    cin >> t;
    while(t--)
    {
        cin >> n >> b;
        vector<int> a(4, 1e8), p(n);
        for(int &x: p) cin >> x;
        i = 0;
        while(i < n)
            cin >> x, a[x] = min(a[x], p[i++]);
        for(int x: a) b -= x;
        cout << (b < 0 ? "no" : "yes");
    }
}

import java.util.*;
public class w
{
        public static void main(String args[])
        {
            Scanner y=new Scanner(System.in);
            int t = y.nextInt();
            while(t-->0)
            {
                int n = y.nextInt();
                int b = y.nextInt();
                int g,m,d,f,c,z;
                g = m = d = f = c = z = 101;
                int a [][] = new int[2][n];
                int i=0;
                for(; i<n; i++)
                    a[0][i] = y.nextInt();
                i=0;
                for(; i<n; i++)
                {
                    a[1][i] = y.nextInt();
                    c = a[1][i];
                    z = a[0][i];
                    if(c == 0 & z<g)
                        g = z;
                    if(c == 1 & z<m)
                        m = z;
                    if(c == 2 & z<d)
                        d = z;
                    if(c == 3 & z<f)
                        f = z;
                }
                String o;
                if(g+m+d+f<=b)
                    o="yes";
                else
                    o="no";
                System.out.println(o);
            }
        }      
}

f=lambda:[*map(int,input().split())]
for w in ' '*f()[0]:
    n,b=f()
    l=[b]*4
    for i,j in zip(f(),f()):
        l[j]=min(l[j],i)
    print('yneos'[sum(l)>b::2])

Let's visualize the distances on a number line. This problem can be solved using the following greedy claim:
Keep moving in one direction, reloading guns. It is optimal to switch to the opposite direction at most once.
Proof of claim:


Let O be the origin; A, B, C be 3 points such that A < O < B < C. Let i, j, k be the time taken to reach A, B, C respectively. Say that between A to C (inclusive), there are X guns.
Let t1 be the time required to reload X guns in total if we initially head right then switch left.
Let t2 be the time required to reload X guns in total if we initially head left then switch right.
Case 1: t1 < t2 ⇒ OC + CA < OA + AC
⇒ OC < OA
⇒ i < j
⇒ i < 2k + j
⇒ i + (i + j) < 2k + j + (i + j)
⇒ 2i + j < 2k + 2j + i
⇒ OC + CA < OB + BA + AC
⇒ Time taken when we switch direction once < Time taken when we switch direction more than once
∴ We proved that it is optimal to switch direction not more than once. Case 2 where t1 >= t2, we can prove the same similarly as case 1.

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

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> a, b;
    a.push_back(0);
    b.push_back(0);
    for(int i = 0; i < n; i++) {
        int x; cin >> x;
        if(x <= 0) {
            a.push_back(-x);
        } else {
            b.push_back(x);
        }
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int n1 = a.size();
    int n2 = b.size();

    int ans = INT_MAX;

    for(int i = 0; i < n1; i++) {
        int j = k - i;
        if(j >= 0 && j < n2) {
            ans = min(ans, a[i] * 2 + b[j]);
        }
    }

    for(int i = 0; i < n2; i++) {
        int j = k - i;
        if(j >= 0 && j < n1) {
            ans = min(ans, b[i] * 2 + a[j]);
        }
    }
    cout << ans << '\n';
}

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        long[] x=new long[n];
        for(int i=0; i<n; i++){
            x[i]=sc.nextLong();
        }
        long ans=Long.MAX_VALUE;
        for(int i=0; i<=n-k; i++){
            ans=Math.min(ans,Math.min(Math.abs(x[i]),Math.abs(x[i+k-1]))+x[i+k-1]-x[i]);
        }
        System.out.println(ans);
    }
}

n,k=map(int,raw_input().split())
x=map(int,raw_input().split())
res=float('inf')
for i in xrange(n-k+1):
 l=x[i]
 r=x[i+k-1]
 res=min(res,abs(l)+abs(r-l),abs(r)+abs(l-r))
print res

#include<bits/stdc++.h>
using namespace std;int n,m,x,y,i,p=1e9,a[1<<20],d,e;int main() {for(cin>>n>>m;i<n;++i)cin>>a[i],i>m-2?x=a[i-m+1],y=a[i],d=abs(x),e=abs(y),p=min(p,(x^y)<0?y-x+min(d,e):max(d,e)):0;cout<<p;}

import java.util.*;
public class S{
    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();int k=s.nextInt();int a[]=new int[n];
        int i=0;
        for(;i<n;i++)a[i]=s.nextInt();
            int u=a[k-1]-a[0];int b=u+Math.min(Math.abs(a[0]),Math.abs(a[k-1]));
        i=1;
        for(;i<=n-k;i++){
            u=u-(a[i]-a[i-1])+(a[i+k-1]-a[i+k-2]);b=Math.min(b, u+Math.min(Math.abs(a[i]),Math.abs(a[i+k-1])));}
        System.out.print(b);}}

n,x,*a=map(int,open(0).read().split())
t=x-1
print(min(a[i+t]-a[i]+min(abs(a[i]),abs(a[i+t]))for i in range(n-t)))

We can assume that A₁ <= A₂ <= ... <= A_N by sorting the input. Then for each i < j, |A_i — A_j| = A_j- A_i holds true.
For each i,
$$$\Sigma_{j=i+1}^N \lvert{A_i-A_j} \rvert = (\Sigma_{j=i+1}^N A_j) - (N-i)\cdot A_i $$$
and this can be calculated in a O(1) time each by calculating the cumulative sums beforehand also known as suffix sum in this case. Therefore, the problem can be solved in a total of O(NlogN) time.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) (v).begin(),(v).end()

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i=0; i<n; i++) cin >> arr[i];
    sort(all(arr));
    vector<int> suff_arr = arr;
    for(int i = n-2; i>=0; i--){
        suff_arr[i] += suff_arr[i+1];
    }
    int res = 0;
    for(int i = 0; i < n-1; i++){
        res += (suff_arr[i+1] - arr[i] * (n - i - 1));
    }
    cout << res << "\n";
    return 0;
}

import java.util.*;
import java.io.PrintWriter;
 
class Main {
    public static void main(String[] Args) {
        var sc = new Scanner(System.in);
        var out = new PrintWriter(System.out);
        var N = Integer.parseInt(sc.next());
        var A = new long[N];
        for (var i = 0; i < N; i++) {
            A[i] = Long.parseLong(sc.next());
        }
        Arrays.sort(A);
 
        var sumA = new long[N + 1];
        sumA[N] = 0;
        for (var i = N - 1; i >= 0; i--) {
            sumA[i] = A[i] + sumA[i+1];
        }
 
        long diff = 0;
        for (var i = 0; i < N - 1; i++) {
            diff += sumA[i + 1] - (A[i] * (N - i - 1));
        }
        out.println(diff);
        out.flush();
    }
}

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
suma = sum(A)
for i in range(N-1):
    suma -= A[i]
    ans += abs(A[i]*(N-i-1) - (suma))
print(ans)

#include<bits/stdc++.h>
using namespace std;
int main()
{
        long n,b=0;
        cin>>n;
        long a[n],s=n-1,i=n;
        while(i--)
            cin >> a[i];
        
        sort(a,a+n);
        for(i=0;i<n;i++)
            b-=s*a[i],s-=2;
        cout << b;
    
}

import java.util.*;
public class Solution {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int i,n=s.nextInt();
        
        long a[]=new long[n],z=0;;
        for( i=0;i<n;i++)
            a[i]=s.nextInt();
        Arrays.sort(a);
        for( i=0;i<n;i++){
           z+=i*a[i]-(n-1-i)*a[i];
        }
        System.out.println(z);
    }
}

n,*s=map(int,open(0).read().split())
s.sort()
print(sum(s[i]*(2*i-n+1) for i in range(n)))

Can we use linearity of expectations?

Can we use Euler's Totient Function?

Let E(X) denote the expected value of random variable X.
Here, X denotes the amount of ammo that the faction takes away.
Let X_i be the value of ammo that member i wins.
Then, X = X₁ + X₂ + .. + X_n
Using linearity of expectations, we can say that
E(X) = E(X₁) + E(X₂) + .. + E(X_n)
So the problem can be solved by summing up the expected ammo won by individual members. Let's see how we can find the individual expectations.

Euler's totient function, also known as phi-function ϕ(n), counts the number of integers between 1 and n inclusive, which are coprime to n.
If i and j operate the machine, the probability that they win ammo is $$$\frac{ϕ(A_i·A_j)}{A_i·A_j}$$$

ϕ(i) can be calculated ∀ i ∈ [1,m] where m = max(A_i) in O(mloglog(m)) time. It can also be calculated in O(mlog(m)) which takes less characters of code to write, but takes more time (enough to pass in time limit though). The product A_i·A_j can be as large as 10¹², so we cannot calculate all ϕ(i) values upto 10¹². Hence we exploit the following property of phi function:
ϕ(a·b) = ϕ(a)·ϕ(b)· $$$\frac{gcd(a,b)}{ϕ(gcd(a,b))}$$$

It is now sufficient to calculate ϕ(i) ∀ i ∈ [1,m], as we can obtain ϕ(A_i·A_j) by plugging the computed values of ϕ(A_i), ϕ(A_j) and ϕ(gcd(A_i,A_j)) in the equation above. Final answer will be
∴ E(X) = ($$$\frac{ϕ(A_N·A_1)}{A_N·A_1}$$$ + $$$\Sigma_{i=1}^{N-1}$$$ $$$\frac{ϕ(A_i·A_{i+1})}{A_i·A_{i+1}}$$$)·K

We will find gcd of adjacent pairs N times, finding gcd(A,B) takes O(log(A·B)) time.
∴ Time complexity of solution will be O(mlog(log(m))+nlog(m)) or O(mlog(m)+nlog(m)) depending on the implementation of calculating phi function.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
 
vector<ll> calc_ETF(int n) {
    vector<ll> phi(n+1);
    phi[0] = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
        phi[i] = i;
    for (int i = 2; i <= n; i++) {
        if (phi[i] == i) {
            for (int j = i; j <= n; j += i)
                phi[j] -= phi[j] / i;
        }
    }
    return phi;
}
 
void solve() {
    int n; ll k; cin >> n >> k;
    ll mx = 0;
    vector<ll> arr(n);
    for (auto& i: arr) {
        cin >> i;
        mx = max(mx, i);
    }
    vector<ll> phi = calc_ETF(mx);
    vector<ld> E(n+1);
    for (int i = 0; i < n; i++) {
        ll A = arr[i], B = arr[(i+1)%n];
        ll g = __gcd(A,B);
        ll num = (phi[A] * phi[B] * g) / phi[g];
        ld den = A * B;
        ld val = num / den;
        E[i] += val;
        E[(i+1)%n] += val;  
    }
    ld ans = 0;
    for (auto i: E) ans += i;
    ans *= k;
    cout << fixed << setprecision(6) << ans << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
 
public class Main {
    public static int gcd(int x, int y){
        return (y == 0) ? x : gcd(y, x % y);
    }
   
    public static void main (String[] args) throws java.lang.Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        int arr[] = new int[n];
        int mx = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            mx = Math.max(mx, arr[i]);
        }
        int phi[] = new int[mx+1];
        phi[1] = 1;
        for (int i = 2; i <= mx; i++)
            phi[i] = i;
        for (int i = 2; i <= mx; i++) {
            if (phi[i] == i) {
                for (int j = i; j <= mx; j += i)
                    phi[j] -= phi[j] / i;
            }
        }
        BigDecimal ans = new BigDecimal("0");
        for (int i = 0; i < n; i++) {
            int A = arr[i], B = arr[(i+1)%n];
            int g = gcd(A,B);
            long num = (( ((long)phi[A]) * ((long)phi[B]) * ((long)g))) / ((long)phi[g]);
            long den = A * B;
            BigDecimal d = new BigDecimal((double) ((double) num * 2l) / ((double) den));
            ans = ans.add(d);
        }
        ans = ans.multiply(new BigDecimal(k));
        System.out.print(String.format("%.6f", ans));
    }
}

import math
from decimal import Decimal
 
def calc_ETF(n):
    phi = [0] * (n+1)
    phi[0] = 0
    phi[1] = 1
    for i in range(2,n+1):
        phi[i] = i
    for i in range(2,n+1):
        if phi[i] == i:
            for j in range(i,n+1,i):
                phi[j] = phi[j] - phi[j]//i
    return phi
 
n ,k = map(int, input().split())
arr = list(map(int, input().split()))
 
mx = arr[0]
for i in arr:
    mx = max(mx, i)
 
 
phi = calc_ETF(mx)
ans = 0
for i in range(n):
    A = arr[i]
    B = arr[(i+1)%n]
    g = math.gcd(A,B)
    num = (phi[A] * phi[B] * g) // phi[g]
    den = A * B
    val = Decimal(num * 2) / Decimal(den)
    ans = ans + val
ans = ans * k
print ('%.6f'%ans)

#include<bits/stdc++.h>
using namespace std;long double ans;int main() {int N=1<<20,n,k,phi[N],a[N],x,y,d,i,j;iota(phi,phi+N,0);for(i=1;i<N;++i)for(j=i+i;j<N;j+=i)phi[j]-=phi[i];cin>>n>>k;for(i=0;i<n;++i)cin>>a[i];for(i=0;i<n;++i)x=a[i],y=a[(i+1)%n],d=gcd(x,y),ans+=(long double)phi[x]/x*phi[y]/y*d/phi[d];printf("%.9Lf",ans*2*k);}

Nobody :(

from decimal import *
n,k,*a=map(int,open(0).read().split())
m=4**10
p=[1]*m
s=[set()for i in' '*m]
for i in range(2,m):
    if p[i]:
        for j in range(i,m,i):
            p[j]=0
            s[j]|={i}
            
r=0
for x, y in zip(a, a[1:]+[a[0]]):
    z=m=Decimal(x*y)
    for i in s[x]|s[y]:
        z-=z//i
    r+=k*2*z/m
print(r)