So, after four years of non-participation on Codeforces, I recently did three contests in a row and managed to drop a whole color (in part because of being out of practice and in part because of not treating the contests seriously). In fact, I was never dedicated enough for competitive programming (in terms of time/effort/methodology), for a number of reasons, but here's one issue that I'd like to survey fellow competitive programmers about: what is your favorite contest format, and why? Below is my personal view. (This may have been discussed previously, but it's always nice to become acquainted with new/recent opinions).

• OI style (IOI & national olympiads): this is by far my personal favorite. First of all, I'm not a fan of team competitions since I like to have a quantifiable measure of my own performance. Furthermore, scoring does not depend on the time that is taken to solve a (sub)problem. This has several benefits. For one thing, it prevents irritating factors from playing a role, such as rushing to submit a solution (say, based on a greedy approach) without being sure about its correctness in order to score higher. The subtasks thing (with full feedback) is also quite a neat feature and means there is something for everyone (unlike Codeforces contest where it's not unlikely that most people only manage to do 0, 1 or 2 problems). This allows for a nice score distribution and is obviously more meaningful than ranking participants based on time. The absence of penalties for non-AC solutions is not something I'm particularly fond of.

• ACM-ICPC style: penalties are there, so that's a plus point. Time-based ranking is a minus. Feedback is also present. As said, no fan of team competitions. Since the number of problems on the problem set is usually high, the "something for everyone" part is also available (in a balanced problem set, at least).

• Codeforces/TopCoder: usually, there are only pretests during the rounds, and the balance of difficulty is not that great. Additionally, while I know that hacks/challenges add to the fun for some participants, I don't particularly enjoy them (granted, because I'm not good at them, but that's only a semi-reason; I believe that they, like time-based ranking, make the contests unnecessarily too competitive). In fact, I would advocate enabling contestants to opt to participate in "anonymous" mode; you could still participate, but your rating changes/color/submitted code would only be visible to you. Again, I'm aware that this is not "fun" for many competitive programmers, but it's just an option that would ensure that some users aren't too discouraged.

Dear fellow coders,

As we're approaching the end of 2015 (actually some parts of our beautiful blue planet have already entered 2016!), I'd like to take the opportunity to wish everyone of this great community a successful, healthy and happy 2016!

As one of my (many!) resolutions for the new year, I decided to rejoin Codeforces contests after not participating in any of them for more than 2 years.

I, Pancake, the first of my name, am going to try my best to become red at some point in 2016.

I invite everyone to set themselves a smiliar achievable feat. Please leave a comment with the color you intend to reach in 2016. And always keep in mind, that the open disclosure of resolutions is the best way to force yourself to adhere to them.

I hope we can get as many coders as possible who will accept the challenge and attempt to raise their potential in competitive programming contests in the coming year.

All the best,

a Pancake.

The seventh contest in the series will be held on

this Saturday, March 7, starting at 14:00 (GMT/UTC).

Check out your local times

Let us discuss the problems here when the contest is over!

Здравствуйте! меня зовут Pancake.я программист. я люблю Россию и математику.
пока, мои друзья!

Seriously though, I have just barely started learning the language, and one of my top reasons to learn it is that Codeforces is actually a Russian site, and Russia is dominating competitive programing today. I hope I can reach a level that is sufficient to participate in programming discussions in Russian on Codeforces!

I'm aware that they're already searchable using tags. However, some really interesting blog entries are lost in the noise, and it's getting harder over time to gather and organize them. Some people like me might just find it enjoyable to quickly explore the older topics that were submitted during a given time interval, and who knows, one might stumble upon an interesting technique or discussion. I don't think adding such a feature would hurt.

Some teams got problem I accepted by running a heuristic or a randomized method. Apparently test data didn't cover cases that would break those solutions.

I'm interested in knowing what methods people used on this problem other than the intended bipartite matching solution.

Most of us are big fans of Codeforces, which is apparently a Russian programming website. Through this website, we got to know more about algorithms, and in particular, we noticed the excellence of ex-USSR countries(particularly Russia,Ukraine and Belarus) at the field of algorithms.

Many of us are university or high school students, and most of us(at this age) have scientific, as well as social curiousity. We are curious about our countries, and about what is going on in the world. Since Ukrainian coders are very active here on Codeforces, I would like to ask them to clarify what is going on in their beautiful country. Although Codeforces is a programming website, not a political one, it is(in my opinion) still important to know others' points of view, especially if those others are people who share some sides of your personality(such as the passion for algorithms in this case).

If this is violating Codeforces rules in anyway, please remove this blog entry.

This problem was used in Arab Collegiate Programming Contest ACPC 2013. Description and solution

A Turkish government scholarship program (called TÜBİTAK) awards scholarships for International Scientific Olympiads medalists (including the International Olympiad in Informatics IOI). The scholarship is only available for non-Turkish citizens.While being an IOI medalist is an important factor when applying for undergraduate studies, there are few scholarships programs that depend on IOI results in particular. I think some of you guys might be interested to check that out, so here's a neat summary of application information.

A new season of the interesting COCI contests is kicking off! The first contest is scheduled earlier than usual. It will be on next Saturday(September 28th) and there won't be any contest in October. Let's hope for a high problem quality similarly to previous years. Here's the e-mail sent to the ioi-announce mail list:

Croatian Open Competition in Informatics COCI 2013/2014 Internet online contest series

Over the next seven months we are planning to organize seven online contests as a warm-up for the 2014 season of high school programming competitions. Everyone is welcome to participate!

Each contest will be three hours long and will feature six tasks. The tasks will be of widely varying difficulty; we are hoping to have many beginner or up-and-coming contestants participate, as well as those more experienced.

The first contest will be held on Saturday, 28th September 2013, starting at 14:00 (GMT/UTC). Check out your local times at http://hsin.hr/coci/next_contest.html.

You may use Pascal, C/C++ or Java as your programming language of choice.

The two relevant websites are: http://hsin.hr/coci/ — information about the contest http://evaluator.hsin.hr/ — contest system

We hope that you will join us or encourage your students to do so!

This is the eighth year in a row that we are hosting the COCI series. You can find tasks (statements, test data and solutions) from the previous seven years at http://hsin.hr/coci/. That is over 300 original tasks for students to practice on!

Project Manager

I have recently learnt the O(NlogN) solution which solves the closest pair problem based on a divide-and-conquer approach. However , I still have a question about it . I assume all N points are unique.

In the case where the closest pair in the current sub-problem consists of one point to the left of the middle line , and another to the right of the middle line , we have to :

• list the points that satisfy abs(x - x_mid) < D : D is the shortest distance so far.
• sort these points with respect to their y-coordinates (in non-decreasing order)
• Loop on those points in order , for each point there is a constant number of points that exist within the 2D * D rectangle and any point outside of this rectangle can't improve the answer.

I know that within a 2D * D rectangles there can exist at most 6 points such that any pair of them is at least D units of distance apart. Hence , in the previous method , I think we should examine at most 5 neighbor points within that rectangle. However , many websites claim that the upper bound is 7 or 8. I can't get why. May someone explain the reason ? Also , I'm interested in a formal proof for the 6-points-claim. I only found intuitive ones but they aren't very convincing. Thanks.

EDIT : Never mind . It's now possible to submit solutions for grading. Here's my AC solution for task cave.

On the page for ICPC 2014 on the official website of ACM ICPC , it mentions that the place is "to be determined". But I'm curious to know if it is going to be hosted by Russia once more. This is what I could understand from this CodeForces Blog , using Google Translate. Please share with us what you know in this context.

Hello CodeForces Community. There's no doubt about the importance of having a good problems' analysis after programming contests. I am disappointed about the Rounds Tutorials (and I think many others are) because of the following reasons :

• They don't necessarily exist for some recent contests :-/

• If they existed , then in many cases I encountered the following situations :

1. Written partially or totally in Russian.

2. Written in ambiguous English.

3. Written "unofficially" , i.e some user who participated in the contest decided to share his ideas. This might be inconvenient because the methods he used can be different from the intended solutions which are generally more elegant.

4. Not complete. Solutions for some problems are missing with a promise of adding it "soon". This "soon" often turns into "never".

• If none of the previous problems occurred , then sometimes I feel that the tutorial is disappointing because it's not discussing any of the problems in enough depth. The writer merely sketches a few hints that aren't enough for someone seeking a full solution.

Please note that this isn't "another annoying complaint" about the website. I think CF is one of the best competitive programming platforms ever created , and I enjoy participating. While I think it does take a lot of effort in organizing a CF contest ( from creating the problems themselves , through testing and checking the problems' statements .. etc) , I think it should be somehow "obligatory" to have an "official" tutorial after each CF round. Take Round #174 by scott_wu (and others) as an example. It was wonderful to have an excellent tutorial just after the end of the round. I think if this is done , then it'd be a big plus for the awesome CodeForces website.

Hello All.Recently I have been trying to study the Ford-Fulkerson method to compute a maximum network flow in depth , and I can't find out how to prove the following property: After finding an augmenting path in the residual network , the flow-in = flow-out rule will still hold for every node in the network (not including the source and the sink nodes) . Any help on this is appreciated.

Hello All . I have recently encountered the following problem : "Given is a permutation of the integers {1, 2, ..., N} where 1 <= N <= 50 . We are allowed to perform as many operations as we wish of the form : pick any subsequence consisting of exactly K consecutive elements , and reverse the order of these elements . What is the least number of operations needed to sort the permutation in increasing order?". Some contestants solved this problem using a mere BFS , and got it accepted . They say that it works because there's a reasonable limit on the states the original permutation can be converted to. Is that correct ? May someone help me find this bound ? Thanks.

My thoughts go to all the people of Boston and the USA , and anyone harmed by the terrorist attacks that happened there. I heard today that one police officer near MIT was killed by terrorists . I hope all the great programmers at MIT and Harvard are totally safe.

Hello all. Is anyone aware of problems where I can test a standard O(NlogN) 2-dimensional convex hull implementation , or some geometric problems that involve running the convex hull algorithm at some step ?

Hello all. Today , I participated in a contest with problems from the Croatian Olympiad in Informatics. The relevant contest environment is here. I had a perfect solution for the 3rd problem , and I was able to solve the first part ( finding the number of different values of the shortest path) of the first problem.My backtracking solution for the 2nd turned out to be buggy and scored 0. Since they take too long to publish the results along with codes and solutions on COCI , I'd appreciate if anyone who has participated ( specially those solving many tasks perfectly) can explain his algorithmic approaches for solving the problems.Thanks!

"Marhaba" to all the community of CodeForces! First of all , this blog entry has nothing to do with programming languages :-) It's rather about languages spoken by different nations. Recently , I have been well into the linguistic thing , and I thought it'd be cool if we share some pieces of information about languages we speak. Perhaps we can talk about :

1-Scientific Content (particularly algorithmic) in your mother tongue - is it widely available? 2-Difficulty of your mother language ( How would you rate its difficulty(to learn) for someone who is good at English?) 3-Literature ( any good novels that became international and were translated to English?) 4-Common Proverbs 5- Perhaps some good Jokes in your mother tongue :-)

I'd really appreciate your comment , so please if you have interesting information to share with us , do not hesitate !

N.B: the first word in this blog is the Arabic equivalent for "Hello"

Hello :) . I have encountered a nice ACM regional contest problemset ( Kanpur site , year 2010) , but I can neither find test data for that contest , nor use livearchive as it doesn't seem to have testcases ready , either. Can anyone help ? Thanks

Hello

The rules of the ICPC state that the winner of each regional contest qualifies for the world finals , and additional wildcards are given to other "high-ranking" teams.

I am curious to know :
under what criteria are wildcards given to a certain region ? Who decides on that , and when ? Does the number of wildcards awarded to a specific regional contest vary from year to year ?

thanks a lot.

My (perhaps over complicated) approach to solve the fourth problem was as follows. To order N meals : * let s be the sum of all the values of b[i] (1 <= i <= N) * one meal k must be served as the first meal , that would decrease s by b[k] then increase s by a[k] , hence it's optimal to choose k that minimizes a[k] - b[k] * s <--- s + a[k] - b[k]

Then , to choose the best N — 1 meals , we either have to : Remove meal m != k which maximizes b[m] ( s <--- s - b[m] ) , or Remove meal k , and replace it with meal j which minimizes a[j] - b[j] ( s <--- s + a[j] - b[j]) We repeat the process N — 1 times to find the required answers for k = 1 through N

I only managed to implement it using 2 STL sets , which seems to exceed the memory limit of 32 MB (My solution passes 3 / 5 of official testcases scoring 72 / 120 , and returns SIGABRT on the remaining two)

I'd appreciate it a lot if someone expalins the intended approaches of this problem , or suggest some improvements (if any) to implement the above method

#include <cstdio>
#include <set>
using namespace std;

const int MAXN = 500001;
int N;
int a[MAXN];
int b[MAXN];
long long res[MAXN];
long long bsum;
int a_idx;
set < pair < int , int > > ordered_by_b;
set < pair < int , int > > ordered_by_diff;
set < pair < int , int > >::iterator it1;
set < pair < int , int > >::iterator it2;
pair < int , int > p1;
pair < int , int > p2;

int main(){
	scanf("%d" , &N);
	if(N > 100000)
		goto FAIL;
	for(int n = 1 ; n <= N ; n++){
		scanf("%d %d" , &a[n] , &b[n]);
		bsum += b[n];
		ordered_by_b.insert(make_pair(-b[n] , n));
		ordered_by_diff.insert(make_pair(a[n] - b[n] , n));
	}

	it1 = ordered_by_diff.begin();
	p1 = *it1;
	res[N] = bsum + p1.first;
	a_idx = p1.second;

	long long CASE_I , CASE_II;

	for(int n = N - 1 ; n >= 1 ; n--){
		it1 = ordered_by_b.begin();
	        p1 = *it1;
		if(p1 == make_pair(-b[a_idx] , a_idx))
		    it1++;
		p1 = *it1;
		CASE_I = res[n + 1] + p1.first;
		 

		it2 = ordered_by_diff.begin();
		it2++;
		p2 = *it2;
		CASE_II= res[n + 1] - a[a_idx] + p2.first;

		if(CASE_I < CASE_II){
			res[n] = CASE_I;
			ordered_by_b.erase(p1);
			ordered_by_diff.erase(make_pair(a[p1.second] - b[p1.second] , p1.second));
		}
		else {
			res[n] = CASE_II;
			ordered_by_b.erase(make_pair(-b[a_idx] , a_idx));
			ordered_by_diff.erase(make_pair(a[a_idx] - b[a_idx] , a_idx));
			a_idx = p2.second;
		}
	}
	FAIL:
	for(int n = 1 ; n <= N ; n++)
		printf("%lld\n" , res[n]);
	return 0;
}

Hello I'm trying to solve problem SUPPER from SPOJ. I think a number x[n] is defined to be super if length of LIS[n] (longest increasing subsequence ending at x[n]) plus LDC[n] (length of longest decreasing subsequence ending at x[n] , when reading the input permutation in reverse) equals the length of longest increasing subsequence of the entire input permutation . Solution Complexity is O(N log N). I'm using Segment Tree , suppose node n covers interval [i .. j] , then tree[n] = max { LIS [ x [ i ] ] , LIS [ x [ i + 1 ] ] , ... , LIS [ x [ j ] ] }

I used an O(N^2) solution to compare my answers against. Thanks a lot in advance for any help.

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

const int MAXN = 100001;
int N;
int x[MAXN];
int LIS[MAXN];
int LDS[MAXN];
int lis[MAXN];
int lds[MAXN];
int tree[4 * MAXN];
int best;

int query(int node , int s , int e , int qs , int qe){
   if(s > qe || e < qs)
      return 0;
   if(s >= qs && e <= qe)
      return tree[node];
   return max(query(2 * node , s , (s+e)/2 , qs , qe) , query(2 * node + 1 , (s+e)/2+1, e , qs , qe));
}
void update(int node , int s , int e , int idx , int val){
   if(s == e && s == idx){
      tree[node] = val;
      return;
   }
   if(s > idx || e < idx)
      return;
   update(2 * node , s , (s+e)/2 , idx , val);
   update(2 * node + 1 , (s+e)/2 + 1 , e , idx , val);
   tree[node] = max(tree[2 * node] , tree[2 * node + 1]);
   return;
}

int main(){
   scanf("%d" , &N);
   for(int n = 1 ; n <= N ; n++)
      scanf("%d" , &x[n]);
   for(int n = 1 ; n <= N ; n++){
      LIS[n] = 1 + query(1 , 1 , N , 1 , x[n] - 1);
      update(1 , 1 , N , x[n] , LIS[n]);
      best = max(best , LIS[n]);
   }
   memset(tree , 0 , sizeof(tree));
   for(int n = N ; n >= 1 ; n--){
      LDS[n] = 1 + query(1 , 1 , N , x[n] + 1 , N);
      update(1 , 1 , N , x[n] , LDS[n]);
   }
   vector < int > res;
   for(int n = 1 ; n <= N ; n++){
	  // printf("%d %d\n" , LIS[n],LDS[n]);
      if(LIS[n] + LDS[n] - 1 == best)
         res.push_back(x[n]);
   }

   
   /*
   for(int n = 1 ; n <= N ; n++){
       lis[n] = 1;
	   for(int h = 1 ; h < n ; h++)
		   if(x[n] > x[h])
			   lis[n] = max(lis[n] , lis[h] + 1);
   }
   for(int n = N ; n >= 1 ; n--){
       lds[n] = 1;
	   for(int h = N  ; h > n ; h--)
		   if(x[n] < x[h])
		     lds[n] = max(lds[n] , lds[h] + 1);
   }
   printf("\n\n");
   for(int n =  1 ; n <= N ; n++)
	   printf("%d %d\n" , lis[n] , lds[n]);
   
  */

   sort(res.begin() , res.end());
   printf("%d\n" , res.size());
   for(int i = 0 ; i < (int)(res.size()) - 1 ; i++)
      printf("%d " , res[i]);
   printf("%d\n" , res.back());
   return 0;
}

Example test case :

Input : 
25
19 6 7 11 5 9 8 18 14 4 23 1 13 10 25 2 16 3 12 15 21 17 20 22 24 

Output (by both O(N log N) and O(N^2) solutions): 
11
6 7 8 9 10 12 15 17 20 22 24

Hello :)

I'm trying to solve the KGSS problem on SPOJ . I implemented a segment tree data structure , and wrote a simple brute force to test my answers against. However , I keep getting WA. For any interval represented by a segment tree node , res[node] is the sum of highest two integers on that interval , and f[node] is the largest integer on that interval. Can anyone help ? Thanks a lot.

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 400004;
int N , Q;
int res[MAXN];
int f[MAXN];
int x[MAXN];

struct qstruct { 
	int a;
	int b;
	qstruct(int u , int v){
		a = u;
		b = v;
	}
};

void update(int node , int s , int e , int qs , int qe , int val){
	if(s > qe || e < qs)
		return;
	if(s >= qs && e <= qe){
		f[node] = val;
		return;
	}
	update(2 * node , s , (s + e)/2 , qs , qe , val);
	update(2 * node + 1 , (s + e)/2 + 1 , e , qs , qe , val);
	f[node] = max(f[2 * node] , f[2 * node + 1]);
	res[node] = max(max(res[2 * node] , res[2 * node + 1]) , f[2 * node] + f[2 * node + 1]);
	return;
}
qstruct query(int node , int s , int e , int qs , int qe){
	if(s > qe || e < qs)
		return qstruct(0 , 0);
	if(s >= qs && e <= qe)
		return qstruct(res[node] , f[node]);
	qstruct q1 = query(2 * node , s , (s+e)/2 , qs , qe);
	qstruct q2 = query(2 * node + 1 , (s+e)/2+1 , e , qs , qe);
	qstruct q = qstruct(max(max(q1.a , q2.a) , q1.b + q2.b) , max(q1.b , q2.b));
	return q;
}
void build_segment_tree(int node , int s , int e){
	if(s == e){
		f[node] = x[s];
		return;
	}
	build_segment_tree(2 * node , s , (s + e) / 2);
	build_segment_tree(2 * node + 1 , (s + e ) / 2 + 1 , e);
	res[node] = max(max(res[2 * node] , res[2 * node + 1]) , f[2 * node] + f[2 * node + 1]);
	f[node] = max(f[2 * node] , f[2 * node + 1]);
	return;
}
int main(){
	ios::sync_with_stdio(false);
	scanf("%d" , &N);
	for(int n = 1 ; n <= N ; n++)
		scanf("%d" , &x[n]);
	build_segment_tree(1 , 1 , N);

	scanf("%d" , &Q);
	for(int q = 1 ; q <= Q ; q++){
		char qtype; 
		int u , v;
		cin >> qtype;
		if(qtype == 'U'){
			int idx , val;
			scanf("%d %d" , &idx , &val);x[idx]=val;
			update(1 , 1 , N , idx , idx , val);
		}
		else {
			int u , v;
			scanf("%d %d" , &u , &v);
			printf("%d\n" , query(1 , 1 , N , u , v).a);
			//int ans = 0;
			//for(int i = u ; i < v ; i++)
				//for(int j = i + 1  ; j<=v;j++)
					//ans=max(ans,x[i]+x[j]);
			//printf("BRUTE FORCE :%d\n",ans);
		}
	}
	return 0;
}