Зла на себя не хватает! Вместо того, чтобы искать кратчайший путь через добавленную вершину между ВСЕМИ вершинами, я искал между добавленными на предыдущих итерациях. Так и не отдебагал за полчаса :(

UPD: Речь идет о задаче Div 2 D.

В div2 B ведь можно написать динамику "просмотрели первые к символов, количество способов построить состояние...", где есть 4 варианта состояний — "не сравнимы", "первая строго больше", "вторая строго больше", "пока что равны"?

В div1 C я написал динамику "число способов за k переправ оставить на первом берегу a людей первого типа и b людей второго типа". Это дает нам сложность k*n^4 с очень маленькой константой.

Upd. вроде бы доказал, что у меня баги друг с другом перекрываются, так что вопрос по поводу слабых тестов отпал.

Спасибо за интересные задачи и оперативный разбор.

Оперативно. Спасибо за хороший разбор)

where's english toturial??!!

Айй,я решал А и С так же как и сказано,правда у меня в А было вместо С<=(n+1)/2 с/2+c%2.

Ну а с С более интересно,писал так,чтобы было N+M+K,но тл на 11 тесте. Не могу понять в чём проблема...

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <stdio.h>
#include <math.h>
#include <fstream>
#include <algorithm>
#include <time.h>
//#include <cstdio>

using namespace std;

int main(){
	int n,m,k;
	cin>>n>>m>>k;
	int p[10001];
	for(int i=1;i<=n;i++){
		cin>>p[i];
	}
	int l[10001],r[10001],d[10001];
	for(int i=1;i<=m;i++){
		cin>>l[i]>>r[i]>>d[i];
	}
	int op[10001];
	int oc[10001];
	for(int i=1;i<=n;i++){
		op[i]=0;
		oc[i]=0;
	}
	int x,y;
	for(int i=1;i<=k;i++){
		cin>>x>>y;
		oc[x]++;
		if(y<m){
			oc[y+1]--;
		}
	}
	
	int occ=0;
	for(int i=1;i<=m;i++){
		occ+=oc[i];
		d[i]*=occ;
		op[l[i]]+=d[i];
		if(r[i]<n){
			op[r[i]+1]-=d[i];
		}
	}
	int opc=0;
	for(int i=1;i<=n;i++){
		opc+=op[i];
		cout<<p[i]+opc<<" ";
	}
	return 0;
}

please, someone translate it to english.

296A — Yaroslav and Permutations

Note that after applying the operations of the exchange, we can get any permutation of numbers. Not difficult to understand that the answer is "YES", if you can place a single number that it would not stand in the neighboring cells. Thus, if a some number is meeted C times, it must fulfill the condition C <= (n + 1) / 2.

296B — Yaroslav and Two Strings

We solve the inverse problem: count the number of ways to make a comparable pair. To start count the number of ways to make the first line is less than equal to the second. This number equals the number of ways to do this for each item individually as they are position independent. Let's count the same amount, but when the second string is less than, equal to the first. And similarly to count the number of ways to make the two strings equal. For each symbol values ​​can be regarded as the simple cycle. Now we take the value of 10 to the number of question marks in the input file, and subtract the resulting response to the inverse problem, it will be the answer.

295A — Greg and Array

In order to add the value of d in the interval [x, y] is enough to have the array and put the values ​​b b [x] + = d b [y + 1] — = d Then in a single pass through the array easily reduced all numbers. We apply this method twice: first to query, and then to operations (knowing how many times we run it).

295B — Greg and Graph

To solve this problem you need a good understanding of the principle of Floyd algorithm. General view of the Floyd algorithm: for (k = 1; k <= n; k ++) for (i = 1; i <= n; i ++) for (j = 1; j <= n; j ++) a [i] [j] = min (a [i] [j], a [i] [k] + a [k] [j]); That is, at every step of the way we try to skip through the top K. We will not remove the top, and add (going from the end). We will try to skip the path between all nodes through a new on every step. Thus we get a solution that works for cubic time.

295C — Greg and Friends

Note that at each step we are interested in only the position of the boat (number coast) and the amount of weight people and 50 100 on each shore. What does the number of people on one side is completely determined by the other. To find the minimum number of crossings will use wave algorithm based on this condition. To find the number of ways to add just the sum of all transitions in the state during the transition will carry all the way from one state to another by multiplying the number of ways to choose the people who need to go from one state to another.

295D — Greg and Caves

We use dynamic programming: dp [i] [j] — how many ways there are to construct a figure that in row i will be exactly j columns occupied by black cells and all that is between them. This figure should not decrease (in other words, we take only the upper part of the figure). How to make the transition? Note that dp [i] [j] = 1 + dp [i-1] [2] * (j-2 + 1) + ... + dp [i-1] [l] * (j-l + 1) + ... + dp [i-1] [j]. We write it: dp [i] [j] = 1 + dp [i-1] [2] * j + ... + dp [i-1] [l] * j + ... + dp [i-1] [ j] * j — dp [i-1] [2] * 1 — dp [i-1] [3] * 2 — ... — dp [i-1] [j] * (j-1). It is clear that if make partial amount, the value of the data count becomes very simple. How to find a complete answer: we will sort out the maximum number of suitable t (indicated in the subject). Now, the only difference is that the next line should contain strictly fewer columns. That is, we have a similar transition from -1 term. Also note that fixing the "foundation", we have to multiply the number of ways at a number of ways to place it on the plane, that is the basis of the width of j we can supply (m-j + 1) ways.

295E — Yaroslav and Points

Learn to solve the problem of finding the sum of the distances between points. If you paint, what happens when you add one point, we get the formula: x_i * (2 * i-n) Where x_i — sorted coordinates, and n is the total number of points. Let us learn to know the answers to the two segments of the points to know the answer to their associations. It is clear that for the calculation of such information need only add two reply and adding the sum of the first plurality of coordinates multiplied by a number and and add the amount of the second set of coordinates multiplied by a possibly different number. Thus knowing the answers for some segments of the overall response. We use the root decomposition or Treap storage of such segments. It is not difficult to understand that insertion and deletion is done quickly enough for these structures. For example, for the root decomposition is possible each time to just cut and paste the point in the desired lengths, and if the set was contain long stretches or many pieces, just reconstruct it again. Asymptotics of the solution does not change.

Div 2 C, what does it mean? "Greg wrote down k queries on a piece of paper. Each query has the following form: xi, yi, (1 ≤ xi ≤ yi ≤ m). That means that one should apply operations with numbers xi, xi + 1, ..., yi to the array."

which operation?!

Can someone explain my solution of http://mirror.codeforces.com/contest/295/problem/A is giving wrong answer for test case 11 My code : http://mirror.codeforces.com/contest/295/submission/33406530

Can someone explain the Div 1.B Greg and Graph problem in detail. I Know Floyd's algorithm. But how is it used in this problem.

What is the meaning of "We will not delete the vertices, but add (going from the end). At each step we will try to skip the path between all the vertices through a new one" in the editorial.

Here's a very nice explanation of problem 295C — Greg and Friends. And here's my submission based on the logic discussed in the linked comment: 45487013

can someone explain the solution for div2c / div1a ? i can't understand it just from the editorial.