## Saturday, October 25, 2014

### 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