Hello codeforces community!

I would like to present you iOS application Harun and I released recently.

You can search and filter problems, import solved problems from Codeforces and add problems to a todo list. You can also check out upcoming contests from a contests calendar in the application which is powered by clist.by API and export upcoming contests you are interested in to your phone's calendar. Currently problem database consists of Codeforces and Codechef only, but we are planning to expand it later on.

P.S. Would you be interested in a feature which sends your phone a notification once when Codeforces system-test is over and another time when ratings are updated?

After Good bye 2014, we had 11 div1 contest till now and there was 16 div1 contest between Good bye 2013 Round 255(Happened in 12th July).

What do you think happened this year? Let's discuss this issue and find the reason behind it.

One idea comes to my mind, maybe Codeforces doesn't encourage div1 problem setters enough.

By the way correct me if I miscounted the numbers.

UPD: If we count nonstandard ones situation is 18 vs 20, which seems okay.

The team selection contest for IOI 2015 happened on the last weekend. It is an IOI style contest. There are two days and each day has 3 problems for 5 hours. Here are the short statements of the problems:

UPD: I have added problems of the second day too.

DAY 1

Problem 1

There is a rooted tree with N ≤ 10⁵ nodes and there are M ≤ 10⁵ queries. Initially, all the nodes have the value 0. There are two types of queries. First one gives you two nodes a and b. For every node lying on the path from a to b you need to increase all values of the nodes in its subtree. Notice that you might have increased one of the node's value several times. The Second one gives two nodes a and b as well, and asks you to calculate the sum of subtrees of all the nodes lying on the path from a to b. You need to print the answers for second queries at modulo 10009.

Problem 2

There are Q ≤ 2.10⁵ queries. Each of them is in one of the following formats: "PUSH x, v", "POP x". There is an empty tree in the beginning. "PUSH x, v" means add a new node to the tree with the last unused id(which is the number of PUSH'es so far plus one), and make its parent x, v denotes the value of the node. "POP x" means delete the node with id x from the tree. Every POP operation guarantees that x has no parent at the time of the operation. For each PUSH operation, you need to calculate the minimum value of the x's parents.

Problem 3

There are N ≤ 50 sticks. You need to create a square by choosing a subset of them.

Each of them has a lenght 1 ≤ a_i ≤ 50 and also .

DAY 2

Problem 1

There is a grid with N ≤ 10⁶ rows and M ≤ 10⁶ columns. There are C ≤ 25000 carrots. Input provides you x_i, y_i and v_i, which denotes row number of the ith carrot, column number of the ith carrot and taste value of the ith carrot. You are helping a rabbit to travel in the grid. There is an integer K given in the input. Our rabbit can jump K steps down or K steps right. The weird thing is if he jumps out of the grid he returns to the grid from the opposite side.

More formally if rabbit is on (x, y) then he can go to ((x + K) mod N, y) or (x, (y + K) mod M). Our rabbit can not jump more than T times. In the beginning, you will put the rabbit into any cell. And rabbit will travel in the grid freely. The problem asks you to calculate the maximum possible difference between highest value and lowest value of taste that our rabbit has eaten during the travel.

Problem 2 (Time limit for this problem was 5 seconds.)

There is a sequence of integers a_i ≤ 10⁵ with size N ≤ 10⁵. There are M ≤ 10⁵ queries. Each query gives to you two integers L and R, after then asks you to calculate the maximum value of the interval that belongs to [L, R].

More formally you will choose l and r where L ≤ l ≤ r ≤ R. Value of the interval [l, r] can be calculated with this pseudo code :

res = a[l]
last = a[l]
for i = l + 1 to r:
  if(last > a[i])
    for j = a[i] to last - 1:
      res = res ^ j;
  else
    for j = last + 1 to a[i]
      res = res ^ j.
  last = a[i]

"^" denotes xor. Res equals to the value of the [l, r] after the process.

Problem 3

There is a tree with N ≤ 10⁵ nodes and there are K ≤ 10 good digits. The problem asks you to calculate number of pairs of nodes that the distance between them consist of only good digits.

PS. First problem from the first day is one of my favorites. I would like to see your thoughts about problems as well. Feel free to ask any questions..

There is a string with length n ≤ 10⁴.

Let us denote f_i as number of occurrences of the i'th unique sub sequence.

We need to calculate . Sub sequence does not have to be consective.

I have no idea about the solution so far. So any help would be appreciated.

Here is the source of the problem : link

I've recently created a group named "Informatics Society for Turkish High Schools".

After couple of feedback from students who is attending International Turkish High Schools I decided to create a group for traning purposes.

We will take part in virtual contests and discuss problems together in Turkish and sometimes in English.

Also there will be algorithm lessons in Turkish.

Any student from International Turkish High Schools are welcome to join us!

If you have friends who is training informatics from Turkish Schools, please let them know this group's existence.

UPD1 : The only and necessary qualification in order to take part in the group is "knowing Turkish".

UPD2 : New algorithm translations has been added to the group

Many thanks to t0nyukuk, who come up with the idea of translating e-maxx.ru into Turkish, and other contributors.

You have a sequence of numbers named a. You need to perform 2 queries :

1. Add x to all elements lie in range [L, R]

2. Ask for gcd(a_L,a_L + 1...a_R)

It seems that official APIO website has gone. Is there any other sources i can find English statements, especially APIO 2011.

Thanks in advance.

Is there any website that contains CEOI problems?

There are some interactive problems which is hard to test locally.

statement

Problem is actually asks calculate number of partitons of n.

Is there anyone knows something better then O(n^2) approach?

UPD: Thank you for O(n sqrt(n)) solution fchirica , but i need proof too.

problem statement is here .

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <ctime>
#include <queue>
#include <map>
#include <list>
#include <fstream>
#include <iomanip>
#include <set>

#define For(i,a,b) for(int (i)=(a);(i)<=int(b);(i)++)
#define Ford(i,a,b) for(int (i)=(a);(i)>=int(b);(i)--)
#define Rep(i,a,b) for(int (i)=(a);(i)<int(b);(i)++)
#define foreach(it,x) for(__typeof(x.begin()) it = x.begin() ; it!=x.end() ; it++ )
#define fi first
#define se second
#define dbg(x) cerr<<#x<<":"<<(x)<<endl
#define dg(x) cerr<<#x<<":"<<(x)<<' '
#define fill(x,y) memset(x,y,sizeof x)
#define all(x) x.begin(),x.end()
#define bin(x) (1LL<<(x))
#define gcd __gcd
#define pb push_back 
 
using namespace std;
 
typedef long long Lint;
typedef pair<int,int> ii;
typedef pair<Lint,Lint> Lii;
typedef pair<int,ii> iii;
 
const int inf = 1e9+5;
const Lint Linf = 1e18+5;
 
template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
template<class T> inline T abs(T a){return a>0 ? a : -a;}
template<class T> inline T lcm(T a,T b){
	return a/gcd(a,b)*b;
}

int read(){
	int res = 0 ;
	int neg ;
	while(true){
		char ch = getchar();
		if((ch>='0' && ch<='9') || ch=='-'){
			if(ch=='-') neg = -1;
			else neg = 1 , res = ch-'0';
			break;
		}
	}
	while(true){
		char ch = getchar();
		if(ch>='0' && ch<='9') res*=10 , res+=ch-'0';
		else break;
	}
	return res*neg;
}
void print(int x){
	if(x==0){
		putchar('0');
		putchar('\n');
		return ;
	}
	static char buf[20];
	int nn = 0 ;
	if(x<0) putchar('-') , x*=-1;
	while(x){
		buf[++nn] = x%10+'0';
		x/=10;
	}
	Ford(i,nn,1) putchar(buf[i]);
	putchar('\n');

}

const int MAXN = 1010;

ii ar[MAXN];    
vector<ii> v[MAXN];
int A, B ,C;  

class fenwick{
public:	
	int *T;
	int n;
	vector<int> vals;
	map<int,int> name;
	void init(vector<ii> v){
		Rep(i,0,n)
			T[i] = 0; 
		vals.clear();
		name.clear();
		foreach(it,v){
			vals.pb(A*it->fi+B*it->se);
		}	
		sort(all(vals));	
		int p = 1 ; 
		Rep(i,0,vals.size()){
			if(i>0 && vals[i]!=vals[i-1]) p++;
			name[vals[i]] = p ; 
		}
	}
	fenwick(int _n=0){
		n = _n+5;
		T = new int[n];
	}
	void update(int x,int val){
		x = name[x];
		for(int i=x;i<n;i+=i&-i)
			T[i]+=val;
	}
	int get(int r){
		int idx = upper_bound(all(vals),r)-vals.begin();
		if(idx<0) return 0;
		if(upper_bound(all(vals),r)==vals.end()) idx--;
		r = name[vals[idx]];
		int res = 0 ;
		for(int i=r;i>0;i-=i&-i)	
			res+=T[i];
		return res;	 	
	}
};

bool cmp(const ii &a,const ii &b){
	return a.se < b.se ; 
}

int main(){
	
	freopen("tryout.in","r",stdin);
	freopen("tryout.out","w",stdout);
	
	int N = read() ; 
	A = read() , B = read() , C = read();
	
	For(i,1,N){
		ar[i].fi = read();
		ar[i].se = read();
	}
	
	sort(ar+1,ar+1+N);
	
	For(i,1,N){
		For(j,i,N)
			v[i].pb(ar[j]);
		sort(all(v[i]),cmp);
	}	
	
	fenwick F(N);
	
	int ans = 0 ; 

	For(i,1,N){
		int hmin = ar[i].fi;
		F.init(v[i]);
		Ford(j,(int)v[i].size()-1,0){
			int wmin = v[i][j].se;
			int cc = C + hmin * A + wmin * B ; 	
			F.update(A*v[i][j].fi+B*v[i][j].se,1);
			umax(ans,F.get(cc));
		}
	}
	
	print(ans);
	
	return 0;
}

WHY this code gets WA.?

UPD: i finded the bug. in get function idx must be like that int idx = upper_bound(all(vals),r)-vals.begin()-1;

#include <stdio.h>     
#include <string.h>     

int main(){
   
	int y = 7 , z = 8 ; 
	int *p;
	
	p = &y ; 
	
	*p = (++z)+(y++);
	
	printf("%d\n",*p);
   
	return 0;	
}

This program's output is 8 Anyone know how is this?

N<=10^4

//includes

using namespace std;

template inline T abs ( T a ){return a>0? a : -a;}

typedef pair<int,int> ii;

typedef long long Lint;

const int MAXN = 1e4+100;

const int inf = 1e9+5;

const Lint mod = 1e9+7;

int N;

int ar[MAXN];

Lint dn[2][MAXN];

void add(Lint &a,Lint b){ b%=mod; a = (a+b)%mod; if(a<0) a+=mod; }

int main(){

//~ freopen("f.in","r",stdin);
//~ freopen("f.out","w",stdout);

cin >> N ; 

For(i,1,N) scanf(" %d",ar+i);

if(ar[N]!=0 && ar[N]!=-1) return cout << 0 << endl, 0 ;
if(ar[N]==-1) ar[N]=0;

if(ar[1]!=0 && ar[1]!=-1) return cout << 0 << endl, 0 ;
if(ar[1]==-1) ar[1]=0;

dn[N&1][0] = 1LL;

for(int i=N-1;i>0;i--){

    memset(dn[i&1],0,sizeof dn[i&1]);

    if(ar[i]==-1){

        Rep(k,0,MAXN){
            if(k>0) add(dn[i&1][k],dn[(i+1)&1][k-1]);
            add(dn[i&1][k],dn[(i+1)&1][k]);
            if(k<MAXN) add(dn[i&1][k],dn[(i+1)&1][k+1]);
        }

    }else{

        int k = ar[i];

        if(k>0) add(dn[i&1][k],dn[(i+1)&1][k-1]);
        add(dn[i&1][k],dn[(i+1)&1][k]);
        if(k<MAXN) add(dn[i&1][k],dn[(i+1)&1][k+1]);

    }

}

cout << dn[1][0] << endl;

return 0;

}