Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Tutorials are written by corresponding problem authors. I'm just assembling all those tutorials in one place.

101353A - Charm Is Not Always Enough

Problem Author: raida_ash, Tester: khairat

It is a simple ad-hoc problem. We can solve it in $\text{[math]}$ . 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;
}

101353B - Max and Alexis Plan to Conquer the World

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 $\text{[math]}$ . 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

$\text{[math]}$

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());
    }
}

101353C - Being Common is Too Mainstream

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;
}

101353D - ShaatChara

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.

$\text{[math]}$
$\text{[math]}$
$\text{[math]}$

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;
}

101353E - Just One Swap

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;
}

101353F - Halum and Candies

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 a₁ > 0, a₂ > 0, ..., a_k > 0. Then we sort them again and do the same step until one of the a₁, a₂, ..., a_k becomes 0. This method works for the smaller subtask but for bigger constraints of a_i 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 a_k from a₁, a₂, ..., a_k. This way we surely have given candies to a_k number of guests. Now from the remaining sum of a_k + 1, ..., a_n flavors, we can assign them in empty spots from a₁, a₂, ..., a_k. This means that we could easily chose to give from these flavors when any of the a₁, a₂, ..., a_k 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;
}

101353G - XOR 'em all

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 2²⁰ - 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 P^th 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 i^th 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 $\text{[math]}$ . 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 $\text{[math]}$ 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: $\text{[math]}$

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;
}

101353H - Simple Path

Problem Author: prophet_ov_darkness, Tester: bertho_coder

Firstly let's check out an $\text{[math]}$ 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 $\text{[math]}$ with DP(x) to get the final answer.

Here, ST(x) = set of proper descendants of node x

Overall time complexity: $\text{[math]}$

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;
}

Full text and comments »