Codeforces Round 275 (Div. 2)

Problem A:
483A - Counterexample

Lots of ways to find a counterexample, easiest is to give 3 consecutive numbers starting with an even number.

Problem B:
483B - Friends and Presents

This problem is solvable using binary search. First notice that the number of elements in [1 .. v] that is divisible by a prime p is \( \lfloor \frac{v}{p} \rfloor \), and the number of elements divisible by both p and q is \( \lfloor \frac{v}{pq} \rfloor \). We are not interested in those which are divisible by both, since we can't give it to either person. Hence we can group the elements in [1 .. v] into 3 categories: those which are divisible by p only, those divisible by p only, and those not divisible by either p or q (or both). We can give all that is divisible by q to the first person, and give the ones divisible by p to the second person. Then what remains is to check whether we can distribute the rest which are not divisible by p or q such that it satisfies them both. If so, we can search for a lower value v, otherwise we have to increase v.



Problem C:
483C - Diverse Permutation

This problem is actually easier than problem B. Firstly notice that from 1 to N, if we write the sequence in an alternating order, we can get any value of K from 1 to N-1. Then the rest of the problem is just about constructing this sequence.

Problem D:
483D - Interesting Array

This problem is solvable using segment tree. Initially all N numbers are 0. Then for each query i, we only turn on the bits on elements l[i] to r[i] for all bits that is ON in q[i]. This is because the AND of the bits can only be 1 if all the bits are 1. Then finally we check for congruency once we have all the necessary bits turned on.
I used segment tree during the contest, but it gets a TLE since my implementation had quite a huge constant term. Here is a less slow implementation.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
using namespace std;

int N, M;
int a[100003][33];
int q[100003][33];
int l[100003];
int r[100003];
int segtree[400003][33];
int lazy[400003][33];

void build(int tree, int p, int L, int R) {
    if(L > R) return;
    if(L == R) {
        segtree[p][tree] = a[L][tree];
        return;
    }
    int mid = (L+R)/2;
    build(tree, p*2, L, mid);
    build(tree, p*2+1, mid+1, R);
    segtree[p][tree] = segtree[2*p][tree] & segtree[2*p+1][tree];
}

int query(int tree, int p, int L, int R, int M, int N) {
    if(R < M || N < L) return -1;
    if(lazy[p][tree]) {
        return 1;
    }
    if(M <= L && R <= N) return segtree[p][tree];
    int mid = (L+R)/2;
    int left = query(tree, 2*p, L, mid, M, N);
    int right = query(tree, 2*p+1, mid+1, R, M, N);
    if(left == -1) return right;
    if(right == -1) return left;
    return left & right;
}

void lazy_update(int tree, int p, int L, int R, int M, int N) {
    //printf("%d %d %d %d\n", L, R, M, N);
    if(R < M || N < L) return;
    if(lazy[p][tree]) {
        return;
    }
    if(M <= L && R <= N) {
        lazy[p][tree] = 1;
        return;
    }
    int mid = (L+R)/2;
    lazy_update(tree, 2*p, L, mid, M, N);
    lazy_update(tree, 2*p+1, mid+1, R, M, N);
}

void init(int tree){
    build(tree, 1, 0, N-1);
}

int qqq[100003];
int res[100003];
int fintree[400003];

void build2(int p, int L, int R) {
    if(L>R) return;
    if(L==R){
        fintree[p] = res[L];
        return;
    }
    int mid = (L+R)/2;
    build2(p*2, L, mid);
    build2(p*2 + 1, mid+1, R);
    fintree[p] = fintree[2*p] & fintree[2*p+1];
}

int query2(int p, int L, int R, int M, int N){
    if(R < M || L > N) return -1;
    if(M<=L && R<=N) {
        return fintree[p];
    }
    int mid = (L+R)/2;
    int left = query2(2*p, L, mid, M, N);
    int right = query2(2*p+1, mid+1, R, M, N);
    if(left == -1) return right;
    if(right == -1) return left;
    return left & right;
}

int main(){

    cin >> N >> M;
    int qq;
    for(int i=0;i<M;++i){
        scanf("%d %d %d", &l[i], &r[i], &qqq[i]);
        qq = qqq[i];
        for(int j=0;j<30;++j){
            q[i][j] = qq%2;
            qq /= 2;
        }
        --l[i];
        --r[i];
    }
    for(int i=0;i<30;++i){
        init(i);
    }
    for(int i=0;i<M;++i){
        for(int j=0;j<30;++j){
            if(q[i][j] == 1) {
                lazy_update(j, 1, 0, N-1, l[i], r[i]);
            }
        }
    }
    for(int i=0;i<N;++i){
        res[i] = 0;
        for(int j=29;j>=0;--j){
            res[i] *= 2;
            res[i] += query(j, 1, 0, N-1, i, i);
        }
    }
    
    build2(1, 0, N-1);
    
    bool ok = true;
    for(int i=0;i<M;++i){
        if(query2(1, 0, N-1, l[i], r[i]) != qqq[i]) {
            ok = false;
            break;
        }
    }
    if(ok){
        printf("YES\n");
        for(int i=0;i<N;++i){
            if(i!= 0) printf(" ");
            printf("%d", res[i]);
        }
        printf("\n");
    } else {
        printf("NO\n");
    }
    return 0;
}

Problem E haven't try yet. UPDATED: Just finished after 5 hours of staring at the monitor :O Problem E