Do you use codeforces to take part in contests or to read announcements?

Что там вообще в углу происходит?! Там кажется искривление пространства.

Yep, we're trying

There is no Cow Level!

Are you sure that this round easy? Especially problem E? I don't think so

Not sure if this is correct ;) Would also be curious to learn the intended solution. I think this is not it.

Intuition: a sequence of length 1000 after three operations consists mostly of a few sequences like 5,6,7,8,... and 9,8,7,... . The boundaries of such sequences are of interest to us, because they may have probably been the points where the string 1,2,...,1000 was "broken". For example, in the sequence 321789456, the numbers 3,1,7,9,4,6 seem to be interesting. On the other hand, there should not be many interesting numbers.

So, let's say that a number i is suspect if it is not neighboured in the sequence by the numbers i-1 and i+1 (and let's also have 1 and n be suspect). We do backtracking — we try to generate all possible sequences that are created by reversing subsequences that begin and end with a suspect number. The complexity should be , where s is the number of suspect numbers (I would guess no more than around 14).

1. На том, что рассматривали непрерывные блоки как один элемент.

2. Жадный алгоритм.

На TLE.

Это был контест на один дивизион. В приписке div. 2 не было необходимости...

Я дорешал таким алгоритмом:

Разделим наш массив на цельные куски, то-есть такие, что состоят из последовательных чисел (возрастающих или убывающих). Запомним все позиции, которые являются концами таких кусков, а потом переберём все возможные пары (L;R) из этих позиций, для каждой из них выполним переворот в массиве, и пойдём рекурсивно(с максимальной глубиной 3) к началу алгоритма. Если в какой-то из моментов получили правильную последовательность — восстанавливаем ответ.

Единственное что, потребовалась следующая оптимизация: для R брать только концы кусков.

Итого: 810 мс, и если избавиться от векторов — 342 мс.

Асимптотика что-то около O(n·maxc⁶) , где maxc — максимальное количество цельных кусков в массиве.

I you knew Segment tree you could solve it!!!

You can simply solve it using Segment Tree. Suppose you have a Segment Tree which is a Full Binary Tree with 2^17 leaves and thus has height of 18. Now you need a property to compute the value of one node using its children. If your node is at odd height then its result is the OR of its children, otherwise it's their XOR. You can update in O(logn) and find the wanted value in O(1) (just take the root of the tree) Hope i helped :)

swap(problem C,problem D);

I failed C as well, however the contest was interesting and the problems were very well explained.

Thank you very much Fefer_Ivan.

I get AC after the end of competition. Just because I add code that enumerate the first weight of left scale. so sad...

Your program didn't print anything in output

~650 solutions failed on that test (number 34)

i didn't read the algorithm, but it's output for TC#7 is same as mine, but he passed it and i didn't! i don't know why!!! here is my code

He sent me the same message also.

He sent me the same message! Of course I ignored him...

Yeah I made the same mistake at first as well. Just goes to show that reading the sample helps. :)

I'm so silly huh...I know why I've made that mistake...

it is(just a kind of feeling)! but i dont understand the meaning of the problem D. perhaps i should learn maths harder..

After every query only n elements of this pyramid are changing, and you can recalculate them after each query.

ADD: You can store all information in array a[2N], where N = 2ⁿ, elements with indexes more or equal N are leaves and childs of vertex i are 2i and 2i + 1. See my solution

Одно из решений: посчитаем такую динамику bool dp[n][prev][balance], которая говорит нам, можем ли мы после n, положенных на весы гирек иметь такой баланс, при том что последней мы положили гирьку с весом prev. Переходы вроде бы очевидны. Код

ADD: На самом деле можно обобщить подход и сделать граф с состояниями (prev, balance) c опять же понятными ребрами. И просто проверить, есть ли в этом графе цикл, в который мы можем попасть из начального состояния или простой путь длины не менее n.

Я написал обычный рекурсивный перебор. Можно заметить, что либо решения нет вообще, либо если есть, то их много. Я имею ввиду тесты с большим N.

Он уже появился.

OMG. really INCREDIBLE. i dont belive that is realy. but it is realy.==> TEST is very low

:|

include

include

include

include

include

include

include

include

include

include

include

include

include

include

define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i++)

define DOWFOR(i,a,b) for (int i=(a),_b=(b);i>=_b;i--)

define mp make_pair

define pb push_back

define reset(c,x) memset(c,x,sizeof(c))

define oo 1000000000

using namespace std; char s[100]; int m,res[10000],sl=0,w[20],t=0,sum[2]; bool ok; void duyet(int x) { if (sl>=m&&ok==false) { printf("YES\n"); FOR(i,1,m) printf("%d ",res[i]); ok=true; return; } if (ok==false) FOR(i,1,t) if (ok==false) { if (w[i]!=res[sl]) if (w[i]+sum[x%2]>sum[(x+1)%2]) { sl++; res[sl]=w[i]; sum[x%2]+=(w[i]); // cout<<sl<<" "<<sum[x%2]<<" "<<sum[(x+1)%2]<<endl; duyet(x+1); sl--; sum[x%2]-=(w[i]); } } else break; return ; } int main() { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); gets(s); scanf("%d",&m); reset(w,0); reset(res,0); FOR(i,0,strlen(s)-1) if (s[i]=='1') { t++; w[t]=i+1; } // FOR(i,1,t) // cout<<w[i]<<endl; if (t<1) { printf("NO"); return 0; } sum[0]=0; sum[1]=w[1]; sl=1; ok=false; FOR(i,1,t) if (ok==false) {

    sum[0]=0;
    sum[1]=w[i];
    res[1]=w[i];
    sl=1;
    duyet(2);
}
else 
{
    break;
}
if (ok==false)
{
    printf("NO");
    return 0;
}
return 0;

}

i do something like this i used dfs on a tree that have t^m vertex but it will get much faster if you code that if a vertex can't be an answer don't continue it. see my solution 4358155

He wrote it within few hours of contest. GL :)

http://mirror.codeforces.com/blog/entry/8725

4350288 this one for example.

Can you explain the idea behind this testcase?