Tutorials are written by corresponding problem authors. I'm just assembling all those tutorials in one place.
Problem Author: raida_ash, Tester: khairat
It is a simple ad-hoc problem. We can solve it in 
. Simply iterate over all the bottles and add the amount of liquid spilled to the answer.
Problem Author's Solution#include <bits/stdc++.h>
using namespace std;
main()
{
//freopen("in1.txt","r",stdin);
//freopen("out1.txt","w",stdout);
int n,m,c[100005],t;
long long int ans;
scanf("%d",&t);
while(t--)
{
ans = 0;
scanf("%d %d",&n,&m);
for (int i=0; i<n; i++)
{
scanf("%d",&c[i]);
ans += ceil((double)((c[i]*1.0)/m))*m - c[i];
}
printf("%lld\n",ans);
}
return 0;
}
Problem Author: Tanzir5, Tester: s_h_shahin, shapnil092
The number of kittens is N initially and rate of increase in the number of kittens is R% per year. Let's divide R by 100 and then we can use the formula of compound interest here to get that after X years, the number of kittens will be:
N × (1 + R)X
Now we can do a binary search over X to find out which is the lowest value of X that satisfies the following equation:
N × (1 + R)X ≥ P ( Where P is the required number of kittens given as input )
So the time complexity is 
. Now if you take the highest end of your binary search range too large, then you will get TLE as you can see the range you take has direct effect on the complexity. You can do some calculation to find that answer can never be more than around 5000 for the given constraints.
Another way to solve the problem would be to use a direct formula. From the above formula, we can come to this:
N × (1 + R)X ≥ P
So now we can get the minimum value of X from this formula. But you have to be careful with the calculations and take care of the cases specially where P ≤ N i.e. the answer is 0.
Problem Author's Solution#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
double N, R, P;
#define D(x) cerr << #x " = " << x << endl
inline double bigMod(double a, int n)
{
double x = a, ret = 1;
while(n)
{
int currentBit = n&1;
if(currentBit)
ret *= x;
x*=x;
n = n>>1;
}
return ret;
}
inline bool ok(int x)
{
double total = N*bigMod(1+R, x);
// double total = N*pow(1+R, x);
if(total >= P)
return true;
else
return false;
}
inline int solve()
{
int lo = 0, hi = 5000, mid;
while(lo < hi)
{
mid = (lo+hi)/2;
if(ok(mid))
hi = mid;
else
lo = mid+1;
}
return lo;
}
int main()
{
// freopen("input_subtask_2.txt", "r", stdin);
// freopen("output_subtask_2.txt", "w", stdout);
// freopen("input_subtask_1.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// cout << 5e5 * log2(5000) * log2(5000) /1e8 << endl;
// cout << 5e5 * 3000 /1e8 << endl;
int i, j, cs, t;
assert(scanf("%d",&t) == 1);
assert(1 <= t);
assert(t <= 250000);
for(cs = 1; cs<=t; cs++)
{
assert(scanf("%lf %lf %lf",&N,&R,&P) == 3);
assert(1 <= N);
assert(N <= 1000000000);
assert(1 <= R);
assert(R <= 100);
assert(1 <= P);
assert(P <= 10000000000000000000ULL);
R/=100;
// solve();
printf("Case %d: %d\n",cs,solve());
}
}
Problem Author: nafisiham, Tester: De_La_Grandi_Mephstophls
The problem setter’s and the alternate writer’s solution are nearly same, and it is not the best but an easy way to solve this problem.
The naïve solution is to keep calculating GCD of every set of numbers that can be taken and keep dividing the elements of the sets by those GCDs until, there remain some co-prime numbers. The answer is their product. Actually, we are trying to divide every number with whatever common divisor it shares with any other number.
So, for every prime divisor, its remaining exponent will be the absolute difference between its highest and second highest exponent in any number. For subtasks 2 and 3 a fairly small array of primes sufficed.
For subtask 1, naïve approach was taken using Euclidean algorithm.
Problem Author's Solution#include <bits/stdc++.h>
using namespace std;
#define mod 1000000001
int pi[1011] = {0}, in[100005] = {0};
int powp(int n, int p)
{
int x = 0;
while(n%p == 0)
{
n/=p;
x++;
}
return x;
}
unsigned long long gcd(unsigned long long a, unsigned long long b)
{
if (a == 0)
return b;
return gcd(b%a, a);
}
void siv(int n)
{
bool prime[n+1];
memset(prime, true, sizeof(prime));
for (int p=2; p*p<=n; p++)
{
if (prime[p] == true)
{
for (int i = p*2; i<=n; i += p)
prime[i] = false;
}
}
int x = 1;
for(int k = 2; k <= n; k++)
{
if(prime[k] == true)
{
pi[x] = k;
x++;
}
}
}
int main()
{
// freopen("input_file_subtask_3.txt", "r", stdin);
// freopen("output_file_subtask_3.txt", "w", stdout);
unsigned long long x, y, z, ans = 1;
int n;
cin >> n;
if(n == 1)
{
cin >> x;
cout << x % mod << "\n";
return 0;
}
else if(n == 2)
{
cin >> x >> y;
unsigned long long gx;
gx = gcd(x, y); x /= gx; y /= gx;
cout << ((x % mod) * (y % mod)) % mod << "\n";
return 0;
}
else if(n == 3)
{
cin >> x >> y >> z;
unsigned long long g, gxy, gyz, gzx;
g = gcd(gcd(x, y), z);
x/=g; y/=g; z/=g;
//cout << g << "\n";
gxy = gcd(x, y); /*cout << gxy << "\n";*/ x/=gxy; y/=gxy; /*printf("%u %u %u\n", x, y, z);*/
gyz = gcd(y, z); /*cout << gyz << "\n";*/ y/=gyz; z/=gyz; /*printf("%u %u %u\n", x, y, z);*/
gzx = gcd(z, x); /*cout << gzx << "\n";*/ x/=gzx; z/=gzx; /*printf("%u %u %u\n", x, y, z);*/
cout << ((((x % mod) * (y % mod)) % mod) * (z % mod)) % mod << "\n";
return 0;
}
else
{
for(int i = 0; i < n; i++) cin >> in[i];
siv(8012);
sort(in, in+n);
for(int z = 1; z < 1010; z++)
{
int pw = 0, mx = 0, dif = 0;
for(int y = 0; y < n; y++)
{
pw = powp(in[y], pi[z]);
in[y] /= pow(pi[z], pw);
if(pw >= mx){dif = pw - mx; mx = pw;}
}
for(int q = 1; q <= dif; q++) {ans = (ans*pi[z])%mod;}
}
sort(in, in+n);
for(int r = 0; r < n; r++) if(in[r] != in[r+1] && in[r] != in[r-1]) ans = (ans * in[r]) % mod;
cout << ans << "\n";
return 0;
}
}
Tester's Solution#include <bits/stdc++.h>
#define CLR(o) memset(o, 0x00, sizeof o)
#define CLR1(o) memset(o, -1, sizeof o)
#define takei(a) scanf("%d", &a)
#define takell(a) scanf("%lld", &a)
#define takellu(a) scanf("%llu", &a)
#define sf scanf
#define pb push_back
#define mp make_pair
#define ppp system("pause")
#define ok cout << "OKA" <<endl;
#define pf printf
#define NL printf("\n")
#define PI 2*acos(0)
#define all(o) o.begin(), o.end()
#define csi pf("Case %d: ", ++keis)
#define csii pf("Case %d:\n", ++keis)
#define _(o) pf("%d\n", o)
#define ll long long
#define ull unsigned long long
#define exx 2.7182818284590452353602875
#define xx first
#define yy second
///Helper
using namespace std;
template <class T> T MAX(T a, T b)
{
return a>b?a:b;
}
template <class T> T MIN(T a, T b)
{
return a<b?a:b;
}
template <class T1> void __(T1 p)
{
cout << p << endl;
}
template <class T1> void deb(T1 p)
{
cout << "Debugging: " << p << endl;
}
template <class T1, class T2> void deb(T1 p, T2 q)
{
cout << "Debugging: " << p << "\t" << q << endl;
}
template <class T1, class T2, class T3> void deb(T1 p, T2 q, T3 r)
{
cout << "Debugging: " << p << "\t " << q << "\t " << r << endl;
}
template <class T1, class T2, class T3, class T4> void deb(T1 p, T2 q, T3 r, T4 s)
{
cout << "Debugging: " << p << "\t " << q << "\t " << r << "\t " << s << endl;
}
long long int POOW(long long b, long long p)
{
if(p==0) return 1;
return b*POOW(b, p-1);
}
//int SET(int mask, int pos){return mask singlebar (1<<pos);}
//bool CHK(int mask, int pos){return (1&(mask>>pos));}
const int xx[] = {0, 0, 1, -1, -1, 1, -1, 1};
const int yy[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int kx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
const int ky[] = {1, 2, 2, 1, -1, -2, -2, -1}; // KX-> Knight moves xx-> diagonal -> 8 horizontal/vertical->4
#define LT (1<<31)-1
#define MX
#define MOD 1000000001
//#define MY INT_MIN
ll FAST_EXP(ll base, ll power) /*base^power%MOD*/ {ll res=1ll;while(power){if(power&1)res=(res*base)%MOD;base=(base*base)%MOD;power>>=1;}return res%MOD;}
ll ar[100005];
vector <ll> pr;
vector < pair <ll, ll> > ans;
int n;
#define SIZE 73211336
bool prime[SIZE];
void SEIEVE()
{
long long i, j, lim = sqrt(SIZE) + 1;
for(i=2; i<=lim ; i++)
{
if(prime[i]==0)
{
pr.pb(i);
for(j=i*i; j<=lim; j+=i)
{
prime[j] = 1;
}
}
}
return;
}
int main()
{
//ios_base::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
// freopen("input_file_subtask_2.txt","r",stdin);
//freopen("000.txt","r",stdin);
//freopen("output.txt", "w", stdout);
//clock_t ooo = clock();
#endif
/// MAIN
int i, t, j, k, l, keis(0);
ll c, d, x, y, a, b;
// char pp[100];
// fgets(pp, 100, stdin);
t = 1;
SEIEVE();
// deb(pr.size(), pr[pr.size()-1]);
vector <ll> temp;
// takei(t);
while(t--)
{
takei(n);
ans.clear();
for(i=0; i<n; i++)
{
takell(ar[i]);
}
ans.clear();
if(n==1)
{
pf("%lld\n", ar[0]%MOD);
}
else if(n==2)
{
a = __gcd(ar[0], ar[1]);
b = ar[0]/a;
c = ar[1]/a;
pf("%lld\n", ((b%MOD)*(c%MOD))%MOD);
}
else if(n==3)
{
a = __gcd(ar[0], ar[1]);
b = ar[0]/a;
c = ar[1]/a;
if(ar[2]%a==0)
d = ar[2]/a;
else
d = ar[2];
a = __gcd(c, d);
c = c/a;
d = d/a;
if(b%a==0)
b = b/a;
a = __gcd(b, d);
b = b/a;
d = d/a;
if(c%a==0)
c = c/a;
pf("%lld\n", ((((b%MOD)*(c%MOD))%MOD)*(d%MOD))%MOD);
}
else
{
for(i=0; i<pr.size(); i++)
{
temp.clear();
for(j=0; j<n; j++)
{
a = 0;
while(ar[j]%pr[i]==0)
{
a++;
ar[j]/=pr[i];
}
if(a)
temp.pb(a);
}
if(!temp.size()) continue;
sort(all(temp));
if(temp.size()>1)
a = temp[temp.size()-2];
else
a = 0;
if(a>=temp[temp.size()-1]) ;
else ans.pb({pr[i], temp[temp.size()-1]-a});
}
a = 1ll;
for(i = 0; i<ans.size(); i++)
{
// deb(ans[i].xx, ans[i].yy);
a = a * FAST_EXP(ans[i].first, ans[i].second);
a%=MOD;
}
sort(ar, ar+n);
for(i=0; i<n; i++)
{
if(i==0 and ar[i]!=ar[i+1])
{
a = a*ar[i];
a%=MOD;
}
else if(i==n-1 and ar[i]!=ar[i-1])
{
a = a*ar[i];
a%=MOD;
}
else if(ar[i]!=ar[i-1] and ar[i]!=ar[i+1])
{
a = a*ar[i];
a%=MOD;
}
}
__(a);
}
}
/* Coding is FUN */
/// ENDD
#ifndef ONLINE_JUDGE
//pf("-------ENDS OF OUTPUT------\n\n");
//pf("Time Elapsed: %lu\n", (clock()-ooo));
#endif
return 0;
}
Problem Author: immuntasir, Tester: raida_ash
As noted, this is a normal nim game of n piles. In a normal Nim game, the player making the first move has a winning strategy if and only if the nim-sum of the sizes of the piles is nonzero. In this problem we want to know in how many ways the first player can move such that the second player gets a losing state. That means the first player wants to move such that the xor-sum becomes zero. Now note the properties of a xor operation.
Now, we can consider the piles in binary and get some rows and columns of 0s and 1s. The first player is only concerned with the number of bits which are 1 in the current xor-sum. Now note that, each 1 bits of the xor-sum are there because there were 1s in that position in odd number of piles. Now, we have to choose such piles where there is a 1 in the same position of the leftmost bit of xor-sum, and choose the bits in a way such that the number of 1s become zero for all column. So, the solution comes down to this: the number of winning moves are the number of 1’s in the leftmost column with an odd number of 1.
Problem Author's Solution#include <bits/stdc++.h>
using namespace std;
int ara[100010];
int highestOneBit(int i) {
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (((unsigned)i) >> 1);
}
int main () {
int T, n;
scanf("%d", &T);
assert(T<=1000);
for (int cs=1; cs<=T; cs++) {
scanf("%d", &n);
assert(n<=10000);
int xorsum = 0;
for (int i=0; i<n; i++) {
scanf("%d", &ara[i]);
assert(ara[i] <= 100000);
xorsum ^= ara[i];
}
int cnt = 0;
int pos = highestOneBit(xorsum);
for (int i=0; i<n; i++) {
if (pos & ara[i]) cnt++;
}
printf("Case %d: %d\n", cs, cnt);
}
return 0;
}
Problem Author: bertho_coder, Tester: prophet_ov_darkness
The answer is equal to the number of ways you can choose two different numbers from the given array. It can be done easily with the help of the frequency array of the given numbers. But if there is at least one number having frequency greater than 1, then you can swap any two numbers having the same value and get the initial given array. So, in that case, you need to add 1 to the answer.
Problem Author's Solution#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#define MAX 100000
typedef long long int LL;
int frq[MAX+5];
int main()
{
int i, t, v, n;
LL res;
bool flag;
scanf("%d", &t);
while(t--)
{
flag = false;
res = 0;
memset(frq, 0, sizeof(frq));
scanf("%d", &n);
for(i = 1; i <= n; i++){
scanf("%d", &v);
frq[v]++;
}
for(i = 1; i <= MAX; i++)
{
res += (LL) frq[i] * (n - frq[i]);
if(frq[i] > 1) flag = true;
}
printf("%lld\n", res/2 + flag);
}
return 0;
}
Tester's Solution#include <bits/stdc++.h>
#define rep(i,n) for(i=0; i<n; i++)
#define repl(i,n) for(i=1; i<=n; i++)
#define sz(x) (int) x.size()
#define pb push_back
#define all(x) x.begin(),x.end()
#define uu first
#define vv second
#define mem(x, y) memset(x, y, sizeof(x))
#define un(x) x.erase(unique(all(x)), x.end())
#define sdi(x) scanf("%d", &x)
#define sdii(x, y) scanf("%d %d", &x, &y)
#define sdiii(x, y, z) scanf("%d %d %d", &x, &y, &z)
#define sdl(x) scanf("%lld", &x)
#define sdll(x, y) scanf("%lld %lld", &x, &y)
#define sdlll(x, y, z) scanf("%lld %lld %lld", &x, &y, &z)
#define sds(x) scanf("%s", x)
#define pfi(x) printf("%d\n", x)
#define pfii(x, y) printf("%d %d\n", x, y)
#define pfiii(x, y, z) printf("%d %d %d\n", x, y, z)
#define pfl(x) printf("%lld\n", x)
#define pfll(x, y) printf("%lld %lld\n", x, y)
#define pflll(x, y, z) printf("%lld %lld %lld\n", x, y, z)
#define eps 1e-9
#define OK cerr << "ok\n"
#define DB(x) cerr << #x << " = " << x << endl
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair <int, int> pii;
inline int setBit(int N, int pos) { return N=N | (1<<pos); }
inline int resetBit(int N, int pos) { return N= N & ~(1<<pos); }
inline bool checkBit(int N, int pos) { return (bool)(N & (1<<pos)); }
//int kx[] = {+2, +1, -1, -2, -2, -1, +1, +2};
//int ky[] = {+1, +2, +2, +1, -1, -2, -2, -1}; //Knight Direction
//int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
//int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1}; //Four & Eight Direction
const int MAX = 100005;
int n, arr[MAX], freq[MAX];
inline LL solve() {
LL ret = 0;
int i;
if(*max_element(freq, freq+100001) > 1) ret = 1;
rep(i, n) {
freq[ arr[i] ]--;
ret += n-i-1;
ret -= freq[ arr[i] ];
}
return ret;
}
int main() {
// assert(freopen("in.txt","r",stdin));
// assert(freopen("out.txt","w",stdout));
int test, i;
sdi(test);
assert(1<=test && test<=5);
while(test--) {
sdi(n);
assert(2<=n && n<=100000);
rep(i, n) {
sdi(arr[i]);
assert(1<=arr[i] && arr[i]<=100000);
freq[ arr[i] ]++;
}
pfl(solve());
}
return 0;
}
Problem Author: shadowfax, Tester: MesbahTanvir
The naïve solution would be to sort the candies in descending order. Now we give a guest K candies from first K flavors where a1 > 0, a2 > 0, ..., ak > 0. Then we sort them again and do the same step until one of the a1, a2, ..., ak becomes 0. This method works for the smaller subtask but for bigger constraints of ai it fails to solve within time limit.
To solve for the larger constraints, we can accelerate the above algorithm. We sort them in descending order and subtract ak from a1, a2, ..., ak. This way we surely have given candies to ak number of guests. Now from the remaining sum of ak + 1, ..., an flavors, we can assign them in empty spots from a1, a2, ..., ak. This means that we could easily chose to give from these flavors when any of the a1, a2, ..., ak flavors gets less. We use binary search on answer to find the maximum such assignments.
Tester MesbahTanvir also used binary search on answer, but with a quite different approach. Let’s say we can satisfy X guests. Then we find how many candies we have in total so that we can give X guests. Now we just have to check if SUM / X ≥ K, to satisfy our condition.
Problem Author's Solution#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL a[1005];
bool check(LL mid, LL sum, int n, int k) {
for(int i = n-k; i < n; i++) {
if(a[i] >= mid) break;
if(sum < (mid-a[i])) return 0;
sum -= (mid-a[i]);
}
return 1;
}
LL bs(LL sum, int n, int k) {
LL low=0, high=sum, mid, ret=0;
while(low <= high) {
mid = (low+high)/2LL;
if(check(mid, sum, n, k)) {
low = mid+1;
ret = mid;
} else {
high = mid-1;
}
}
return ret;
}
LL solve(int n, int k) {
sort(a, a+n);
if(n == k) return a[0];
LL ret = a[n-k];
for(int i = n-k; i < n; i++)
a[i] -= ret;
LL sum = 0;
for(int i = 0; i < n-k; i++)
sum += a[i];
return ret+bs(sum, n, k);
}
int main() {
//freopen("halum_input_task2.txt","r",stdin);
//freopen("halum_output_task2.txt","w",stdout);
int cases, caseno=0, n, k;
scanf("%d", &cases);
while(cases--) {
scanf("%d %d", &n, &k);
assert(n >= 1 && n <= 1000 && k >= 1 && k <= n);
for(int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
assert(a[i] >= 0 && a[i] <= 1000000000);
}
printf("Case %d: %lld\n", ++caseno, solve(n, k));
}
return 0;
}
Tester's Solution#include <bits/stdc++.h>
#define MAX 101000
#define INF 100000000000000000LL
using namespace std;
long long n,a[MAX],k;
bool can(long long x)
{
long long sum=0;
for(int i=0;i<n;i++){
if(a[i]>x) sum+=x;
else sum+=a[i];
}
return ((sum/x)>=k);
}
long long solve()
{
long long s =1,e=INF,m=0,r=0;
while(s<=e){
m = (s+e+1)/2;
if(can(m)){
r = m;
s = m+1;
}
else e = m-1;
}
return r;
}
int main()
{
int tc , cn=0;
//freopen("halum_input_task1.txt","r",stdin);
//freopen("alter_halum_output_task1.txt","w",stdout);
scanf("%d",&tc);
while(tc--){
scanf("%lld %lld",&n,&k);
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
printf("Case %d: %lld\n",++cn,solve());
}
return 0;
}
Problem Author: Riddho, Tester: s_h_shahin
The first observation to be made here is that if any integer having a parity of X is XOR'ed with 220 - 1 (a number whose binary representation is 11111111111111111111), its parity will become 20 - X.
To handle the updates and queries, a segment tree can be used, each of who's nodes shall contain a bitmask, of 20 bits each. The Pth bit of the bitmask in any node shall be 1 if any of the integers in the interval represented by the node has a parity of P, and 0 otherwise.
Thus, during a range update, the new mask of a node can be created simply by reversing the previous mask (since the ith bit of the new mask will equal the (20 - i)th bit of the old mask).
For answering the query, if the parity of the given number v is P, we first query to find if any number with parity P exists in the given range. If not we find the highest parity Q < P that exists in the range, and the smallest parity R>P that exist in the same.
Case 1: If (P - Q) < (R - P) print the position of the leftmost number in the range with parity Q.
Case 2: If (P - Q) > (R - P) print the position of the leftmost number in the range with parity R.
Case 3: If (P - Q) = (R - P) find x, the position of the leftmost number in the range with parity Q, and y, the position of the leftmost number in the range with parity R, and print the minimum of x and y.
To find the position of the leftmost number with a certain parity p, in a given range, we can query through the segment tree in 
. If we are certain that at least one number with parity p exists in the range represented by a node, then obviously, either the left child or the right child contains a number with the parity p. Since we are looking for the leftmost position, if a number with parity p appears in the left interval (which we can find out using a 
segment tree query on the range specified by the left interval), we go to the left child, otherwise to the right. Once we reach a leaf of a tree, the array element represented by it is the answer to the query.
Time Complexity: 
Problem Author's Solution#include <bits/stdc++.h>
#define SIZE 1000105
#define callLeft s,mid,nd+nd
#define callRight mid+1,e,nd+nd+1
using namespace std;
int n, m;
int ara[SIZE];
int segTree[4*SIZE];
bool lazy[4*SIZE];
bool checkBit(int n, int pos){ return ((n&(1<<pos))!=0);}
int setBit(int n, int pos){ return (n|(1<<pos));}
void build(int s, int e, int nd){
lazy[nd]=0;
if(s==e){
segTree[nd]=setBit(0, __builtin_popcount(ara[s]));
return;
}
int mid=(s+e)>>1;
build(callLeft);
build(callRight);
segTree[nd]=(segTree[nd+nd] | segTree[nd+nd+1]);
}
void lazy_update(int s, int e, int nd){
if(lazy[nd]==true){
int newMask=0;
for(int i=0; i<=20; i++){
if(checkBit(segTree[nd], 20-i)) newMask=setBit(newMask, i);
}
segTree[nd]=newMask;
if(s!=e){
lazy[nd+nd]^=1;
lazy[nd+nd+1]^=1;
}
lazy[nd]=false;
}
}
void update(int s, int e, int nd, int l, int r){
lazy_update(s, e, nd);
if(s>r || e<l) return;
if(s>=l && e<=r){
lazy[nd]^=1;
lazy_update(s, e, nd);
return;
}
int mid=(s+e)>>1;
update(callLeft, l, r);
update(callRight, l, r);
segTree[nd]=(segTree[nd+nd] | segTree[nd+nd+1]);
}
int query2(int s, int e, int nd, int l, int r){
lazy_update(s, e, nd);
if(s>r || e<l) return 0;
if(s>=l && e<=r) return segTree[nd];
int mid=(s+e)>>1;
return (query2(callLeft, l, r) | query2(callRight, l, r));
}
int query(int s, int e, int nd, int l, int r, int pos){
lazy_update(s, e, nd);
if(s==e) return s;
int mid=(s+e)>>1;
if(l>mid){
return query(callRight, l, r, pos);
}
int val=query2(1, n, 1, l, mid);
if(checkBit(val, pos)){
return query(callLeft, l, r, pos);
}
return query(callRight, l, r, pos);
}
int process_query(int l, int r, int v){
int par=__builtin_popcount(v);
int d=0;
int q1, q2;
int d1, d2;
d1=d2=100;
for(int i=par; i>=0; i--){
if(checkBit(query2(1, n, 1, l, r), i)){
q1=query(1, n, 1, l, r, i);
d1=par-i;
break;
}
}
for(int i=par+1; i<=20; i++){
if(checkBit(query2(1, n, 1, l, r), i)){
q2=query(1, n, 1, l, r, i);
d2=i-par;
break;
}
}
if(d1==d2) return min(q1, q2);
if(d1<d2) return q1;
if(d2<d1) return q2;
}
int main()
{
int t, cs=0, l, r, val, type;
// freopen("in3.txt", "r", stdin);
// freopen("out3.txt", "w", stdout);
scanf("%d", &t);
assert(t>=1 && t<=5);
while(t--){
scanf("%d %d", &n, &m);
assert(n>=1 && n<=1000000);
assert(m>=1 && m<=100000);
for(int i=1; i<=n; i++){
scanf("%d", &ara[i]);
assert(ara[i]>=0 && ara[i]<(1<<20));
}
build(1, n, 1);
printf("Case %d:\n", ++cs);
for(int i=1; i<=m; i++){
scanf("%d", &type);
assert(type==1 || type==2);
if(type==1){
scanf("%d %d %d", &l, &r, &val);
assert(l>=1 && l<=r && r<=n);
assert(val>=0 && val<(1<<20));
printf("%d\n", process_query(l, r, val));
}
else{
scanf("%d %d", &l, &r);
assert(l>=1 && l<=r && r<=n);
update(1, n, 1, l, r);
}
}
}
return 0;
}
Tester's Solution#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sl(a) scanf("%I64d",&a)
#define sll(a,b) scanf("%I64d %I64d",&a,&b)
#define slll(a,b,c) scanf("%I64d %I64d %I64d",&a,&b,&c)
#define pb push_back
#define PII pair <int,int>
#define PLL pair <ll,ll>
#define mp make_pair
#define xx first
#define yy second
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define eps 1e-9
#define PI acos(-1.0)
#define MAX 1000010
#define MOD 1000000007
#define INF 2000000000
int setBit(int n,int pos){ return n = n | (1 << pos); } //sets the pos'th bit to 1
int resetBit(int n,int pos){ return n = n & ~(1 << pos); } //sets the pos'th bit to 0
bool checkBit(int n,int pos){ return (bool)(n & (1 << pos)); } //returns the pos'th bit
/******************************************************************************************/
int ara[MAX];
struct node{
int sum;
} tree[4*MAX];
int lazy[4*MAX];
node Merge(node a,node b){
node ret;
ret.sum = a.sum | b.sum;
return ret;
}
void lazyUpdate(int n,int st,int ed)
{
lazy[n] %= 2;
if(lazy[n]!=0){
int x = tree[n].sum;
for(int i=0;i<11;i++){
if(checkBit(x,i) && checkBit(x,20-i)){
}
else if(checkBit(x,i)){
x = resetBit(x,i);
x = setBit(x,20-i);
}
else if(checkBit(x,20-i)){
x = resetBit(x,20-i);
x = setBit(x,i);
}
}
tree[n].sum = x;
if(st!=ed){
lazy[2*n] += lazy[n];
lazy[2*n] %= 2;
lazy[2*n+1] += lazy[n];
lazy[2*n+1] %= 2;
}
lazy[n] = 0;
}
}
void build(int n,int st,int ed)
{
lazy[n] = 0;
if(st==ed){
tree[n].sum = ara[st];
return;
}
int mid = (st+ed)/2;
build(2*n,st,mid);
build(2*n+1,mid+1,ed);
tree[n] = Merge(tree[2*n],tree[2*n+1]);
}
void update(int n,int st,int ed,int i,int j)
{
lazyUpdate(n,st,ed);
if(st>j || ed<i) return;
if(st>=i && ed<=j){
lazy[n]++;
lazy[n] %= 2;
lazyUpdate(n,st,ed);
return;
}
int mid = (st+ed)/2;
update(2*n,st,mid,i,j);
update(2*n+1,mid+1,ed,i,j);
tree[n] = Merge(tree[2*n],tree[2*n+1]);
}
node query(int n,int st,int ed,int i,int j)
{
lazyUpdate(n,st,ed);
if(st>=i && ed<=j) return tree[n];
int mid = (st+ed)/2;
if(mid<i) return query(2*n+1,mid+1,ed,i,j);
else if(mid>=j) return query(2*n,st,mid,i,j);
else return Merge(query(2*n,st,mid,i,j),query(2*n+1,mid+1,ed,i,j));
}
int N;
int query2(int n,int st,int ed,int i,int j,int v)
{
if(st==ed) return st;
int mid = (st+ed)/2;
if(i>mid) return query2(2*n+1,mid+1,ed,i,j,v);
else{
int x = query(1,1,N,i,mid).sum;
if(checkBit(x,v) && mid>=i) return query2(2*n,st,mid,i,j,v);
else return query2(2*n+1,mid+1,ed,i,j,v);
}
}
int num[MAX];
int main()
{
// freopen("in3.txt","r",stdin);
// freopen("alter_out3.txt","w",stdout);
int t,T,n,m,i,type,l,r,v,j;
si(T);
assert(T>=1 && T<=5);
for(t=1;t<=T;t++){
printf("Case %d:\n",t);
sii(n,m);
N = n;
assert(n>=1 && n<=1000000 && m>=1 && m<=100000);
int x;
for(i=1;i<=n;i++){
si(num[i]);
assert(num[i]>=0 && num[i] <= ((1<<20)-1));
x = __builtin_popcount(num[i]);
ara[i] = setBit(0,x);
}
build(1,1,n);
int y,dif1,dif2,id1,id2;
for(i=1;i<=m;i++){
si(type);
assert(type>=1 && type<=2);
if(type==1){
siii(l,r,v);
assert(l>=1 && l<=n && r>=1 && r<=n && v >=0 && v <= ((1<<20)-1) && l<=r);
x = query(1,1,n,l,r).sum;
y = __builtin_popcount(v);
dif1 = dif2 = 30;
for(j=y;j<=20;j++){
if(checkBit(x,j)){
id1 = query2(1,1,n,l,r,j);
dif1 = abs(y-j);
break;
}
}
for(j=y-1;j>=0;j--){
if(checkBit(x,j)){
id2 = query2(1,1,n,l,r,j);
dif2 = abs(y-j);
break;
}
}
if(dif1==dif2) printf("%d\n",min(id1,id2));
else if(dif1<dif2) printf("%d\n",id1);
else printf("%d\n",id2);
}
else{
sii(l,r);
assert(l>=1 && l<=n && r>=1 && r<=n && l<=r);
update(1,1,n,l,r);
}
}
}
return 0;
}
Problem Author: prophet_ov_darkness, Tester: bertho_coder
Firstly let's check out an 
optimized brute force solution to this problem. Here we'll fix a subroot in linear time. Then from each of those subroots we'll run DFS in the corresponding subtree. For each edge in a subtree, we'll count the number of times it appears in all possible simple paths present in that subtree. Let's take an edge u - v, where u is the parent of v. Now the number of times this edge will appear in subtree rooted at node r will be S(v) × (S(r) - S(v)), where S(x) = size of subtree rooted at x. This count will have to be multiplied by the weight of edge u - v and added to the actual result. This part is pretty straight-forward. Think about it for a moment if it's still unclear.
Now let's optimize this solution into a linear one. For that we'll have to use dynamic programming. Let's say DP(x) = answer for subtree rooted at x. Suppose we are computing DP(x) now. Let y be a child of x and u - v an edge in the subtree of y, where u is the parent of v. Firstly we'll have to add DP(y) to DP(x). Secondly we'll have to add the impact edge x - y puts in DP(x). This part is discussed in the previous paragraph. Finally we'll have to count all those simple paths which start in the subtree of y and goes through node x and finishes in another part of the subtree of node x. Let, W(x) be the weight of the edge which leads node x to it's parent.
We know the impact node u - v puts while computing the answer of subtree rooted at y: S(v) × W(v) × (S(y) - S(u))
Impact of edge u - v in the answer of subtree rooted at node x: S(v) × W(v) × (S(x) - S(u))
The difference is: S(v) × W(v) × (S(x) - S(y))
So, we'll have to add 
with DP(x) to get the final answer.
Here, ST(x) = set of proper descendants of node x
Overall time complexity:
Problem Author's Solution#include <bits/stdc++.h>
#define rep(i,n) for(i=0; i<n; i++)
#define repl(i,n) for(i=1; i<=n; i++)
#define sz(x) (int) x.size()
#define pb push_back
#define all(x) x.begin(),x.end()
#define uu first
#define vv second
#define mem(x, y) memset(x, y, sizeof(x))
#define un(x) x.erase(unique(all(x)), x.end())
#define sdi(x) scanf("%d", &x)
#define sdii(x, y) scanf("%d %d", &x, &y)
#define sdiii(x, y, z) scanf("%d %d %d", &x, &y, &z)
#define sdl(x) scanf("%lld", &x)
#define sdll(x, y) scanf("%lld %lld", &x, &y)
#define sdlll(x, y, z) scanf("%lld %lld %lld", &x, &y, &z)
#define sds(x) scanf("%s", x)
#define pfi(x) printf("%d\n", x)
#define pfii(x, y) printf("%d %d\n", x, y)
#define pfiii(x, y, z) printf("%d %d %d\n", x, y, z)
#define pfl(x) printf("%lld\n", x)
#define pfll(x, y) printf("%lld %lld\n", x, y)
#define pflll(x, y, z) printf("%lld %lld %lld\n", x, y, z)
#define eps 1e-9
#define OK cerr << "ok\n"
#define DB(x) cerr << #x << " = " << x << endl
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair <int, int> pii;
inline int setBit(int N, int pos) { return N=N | (1<<pos); }
inline int resetBit(int N, int pos) { return N= N & ~(1<<pos); }
inline bool checkBit(int N, int pos) { return (bool)(N & (1<<pos)); }
//int kx[] = {+2, +1, -1, -2, -2, -1, +1, +2};
//int ky[] = {+1, +2, +2, +1, -1, -2, -2, -1}; //Knight Direction
//int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
//int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1}; //Four & Eight Direction
const int MAX = 100005;
const LL MOD = 1000000007;
int n;
vector < pair <int, LL> > graph[MAX];
LL wisi[MAX], dp[MAX], subtree[MAX];
void dfs(int u, int par=-1) {
subtree[u] = 1;
wisi[u] = 0;
for(auto v:graph[u]) {
if(v.uu != par) {
dfs(v.uu, u);
subtree[u] += subtree[v.uu];
wisi[u] += wisi[v.uu];
if(wisi[u] >= MOD) wisi[u] -= MOD;
wisi[u] += (v.vv*subtree[v.uu]) % MOD;
if(wisi[u] >= MOD) wisi[u] -= MOD;
}
}
}
void dfs1(int u, int par=-1) {
dp[u] = 0;
for(auto v:graph[u]) {
if(v.uu != par) {
dfs1(v.uu, u);
LL temp = v.vv*subtree[v.uu];
temp %= MOD;
temp *= (subtree[u]-subtree[v.uu]);
temp %= MOD;
dp[u] += temp;
if(dp[u] >= MOD) dp[u] -= MOD;
dp[u] += dp[v.uu];
if(dp[u] >= MOD) dp[u] -= MOD;
dp[u] += ((wisi[v.uu] * (subtree[u]-subtree[v.uu])) % MOD);
if(dp[u] >= MOD) dp[u] -= MOD;
}
}
}
int main() {
// assert(freopen("large_in.txt","r",stdin));
// assert(freopen("large_out.txt","w",stdout));
clock_t st = clock();
int test, kase=1, i, u, v;
LL w;
sdi(test);
while(test--) {
sdi(n);
rep(i, n) graph[i].clear();
rep(i, n-1) {
sdii(u, v);
sdl(w);
u--, v--;
graph[u].pb({ v, w });
graph[v].pb({ u, w });
}
dfs(0);
dfs1(0);
LL ans = 0;
rep(i, n) {
ans += dp[i];
if(ans >= MOD) ans -= MOD;
}
printf("Case %d: %lld\n", kase++, ans);
}
clock_t en = clock();
fprintf(stderr, "%.3f sec\n", (double)(en-st)/(double)CLOCKS_PER_SEC);
return 0;
}
Tester's Solution#include<bits/stdc++.h>
using namespace std;
#define D(x) cout << #x " = " << (x) << endl
#define uu first
#define cost second
#define MOD 1000000007
#define MAX 100000
typedef pair<int,int> pii;
typedef long long int LL;
vector< pii > edge[MAX+5];
LL lsum[MAX+5], cnt[MAX+5], dp[MAX+5], ans[MAX+5];
void dfs(int idx, int p)
{
LL c = 0;
lsum[idx] = ans[idx] = cnt[idx] = dp[idx] = 0;
for(auto x : edge[idx])
if(x.uu != p)
{
dfs(x.uu, idx);
c += (cnt[x.uu] + 1);
}
for(int i = 0; i < (int) edge[idx].size(); i++){
int x = edge[idx][i].uu;
int w = edge[idx][i].cost;
if(x == p) continue;
cnt[idx] = (cnt[idx] + cnt[x] + 1) % MOD;
int current = (lsum[x] + (w * (cnt[x] + 1)))% MOD;
lsum[idx] = (lsum[idx] + current) % MOD;
dp[idx] = (dp[idx] + (current * (c - (cnt[x] + 1) + 1)) % MOD) % MOD;
ans[idx] = (ans[idx] + ans[x]) % MOD;
}
ans[idx] = (ans[idx] + dp[idx]) % MOD;
}
int main()
{
// assert(freopen("large_in.txt", "r", stdin));
// assert(freopen("large_out_alter.txt", "w", stdout));
int t, cs, i, u, v, w, n;
scanf("%d", &t);
for(cs = 1; cs <= t; cs++){
scanf("%d", &n);
for(i = 1; i < n; i++)
{
scanf("%d %d %d", &u, &v, &w);
edge[u].push_back(make_pair(v, w));
edge[v].push_back(make_pair(u, w));
}
dfs(1, -1);
LL ttl = 0;
for(i = 1; i <= n; i++) ttl = (ttl + ans[i]) % MOD;
printf("Case %d: %d\n", cs, (int) ttl);
for(i = 1; i <= n; i++) edge[i].clear();
}
return 0;
}
In C for subtasks 2 and 3 another solution is make a list of all the prime divisor which occurs at least in two number then divide the elements of the array for every prime divisor until there two or more elements divided by that divisor.The answer is product of the array's elements.
Here is another solution for G problem and it works in N * log(N) * 20 + Q * log(N) * 20.
please explain why the result of this test case for problem D
1
4
5 1 4 5
is 3
101 001 100 101 You can to any of the following: 1. Remove all from the first pile. 2. Remove 3 from the 3rd pile. 3. Remove all from the 4th pile.
thank you
My linear straight-forward solution for D: ShaatChara
We know that if the first player can make xorsum of the array equal to zero then he wins. Let xorsum of the given array be
x. Observe that the only way to make the xorsum zero by taking out some non-zero stones frompile iis to reduce the value ofa[i]toa[i]^x. Hence we do cnt++ for all i's where a[i]^x is strictly lesser than a[i] since we need to take out at least one stone.In Problem C, Shouldn't the answer of [2,4,8] be 1 ?? My explanation — divide the whole array by 4 to get [2,1,2] and then divide the whole array by 2 to get [1,1,1]