Hello, Codeforces.

Today at 19:30 moscow time, Codeforces Round #197 will take place.

Authors of this round are me and Gerald. I'd like to thank the following people for their contribution: Delinur for translation of the statements and MikeMirzayanov for creation and supportion of Codeforces.

The score for problems: 500 — 1000 — 1500 — 2000 — 3000.

Good luck!

**UPD:** To make the announcement more interestiong and thrilling we decided to add a horse joke and a photo, taken during the preparation of the round.

Q: What did the teacher say when the horse walked into the class?

A: Why the long face?

Too late and too short announcement!

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

It was just my thought about the announcement!

I hope to it has DP && graph problems ... thanks for great time

Is this a step towards the COW LEVEL?

I wonder what's the effect of the mask on coding performances. On one hand you probably focus a bit better, but you might also become horsey...

Yep, we're trying

There is no Cow Level!

Really intresting [but easy!] Problemset and nice horse joke and photo!!

Thank U a lot!!

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

Just Problem E is not easy!!

Usually Problem Ds are harder than Xenia and Bit Operations...

Ooops! Problem C : Trinket

Very nice problems.. Thanks to authors...!!!

How to solve E?

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

iis suspect if it is not neighboured in the sequence by the numbersi-1andi+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 , wheresis the number of suspect numbers (I would guess no more than around 14).Imaginative ""!

I thought you're right as 3 swaps would split the sequence into 7 part (14 point) at most.

Yes this is correct: http://codeforces.com/contest/339/submission/10794458 Here s can't be more than 8. But shouldn't o(n*(s^2)^3) solution give TLE , if s=14 and n=1000?

WE WANT EXTRA TIME FOR SERVER PROBLEMS

pretests are too weak!

nice system testing! ))) thanks

How to Solve D?

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

enlighten me please, I could't find a suitable Data Structure for it

I haven't learnt about segment trees yet, but I solved the problem by storing all the results inside a 2D vector. Then for each query, you will have to update 17 nodes in the worst case. My solution wasn't very fast though.

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 :)

GOOOD ONE bro !!! Helped a lot, I couldn't see that way ;)

Nuff said.

Problem C is very tricky :(

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

Got it... Sry

Your program didn't print anything in output

7 successful hacks for Problem C just with this simple test:

1110000000

4

:O Just Like my previous avatar!

~650 solutions failed on that test (number 34)

Its a very simple but clever test!!

yep I failed there too

for problem E, answer given by solution for testcase#7 is incorrect. the result won't be 1,2,3,4,...,98,99,100 the result for given answer by judge's solution is: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 97 98 22 23 24 25 26 74 73 72 71 70 47 48 49 50 51 52 53 54 55 56 57 58 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 27 28 29 64 65 66 67 68 69 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 63 62 61 60 59 92 93 94 95 96 99 100

it's not correct! or i & many other contestants understood the problem in a wrong way.

Can anybody explain why do this solution get AC?

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

No, your answer is reversed.

oops. the problem wanted her movements, not us! :| by the way, my algorithm is not correct, i reversed it just to check, and i didn't pass TC#8 because i'm solving it with more than 3 moves.

During the contest,Aatr0x (I don't know him) sent me following message... And I noticed he passed D.Anyone sent D's sourcecode to him?

He sent me the same message also.

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

"she writes down the bit-wise OR of adjacent elements of sequence a" if this sentences wasnt wrong than

1 . step => a1 , a2 , a3 , a4

2 . step => a1|a2 , a2|a3 , a3|a4

3 . step => (a1|a2) ^ (a2|a3) ...

...

but problem is

1 . step => a1 , a2 , a3 , a4

2 . step => a1|a2 , a3|a4

3 . step => (a1|a2) ^ (a3|a4) ...

Because of this statement i couldnt colve this problem , may be i 'm quilty too because dont read all statement or dont look sample test , whatever there is a problem with statement.

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

Can anyone explain test 7 for problem E for us? Lots of contestants failed on that with the same output: 3 22 97 27 74 47 69 I don't think this output is wrong... Can anyone help me?

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

imho, D much more easier than C.

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

this problem is just standard segment tree problem , not related to maths

That is an interesting statement...

Can segment tree be defined without using mathematics?

Unless I am misunderstanding what "maths" means, I do not think it is possible. But someone can prove me wrong.

How to approach D efficiently?

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], whereN= 2^{n}, elements with indexes more or equalNare leaves and childs of vertexiare 2iand 2i+ 1. See my solutionI assume that by pyramid you mean the "recursion" until we reach 1 element...

So if we have the numbers: 1 6 3 5 and we have query 1 4, we will obtain the list 4 6 3 5, you mean that only pair 4 6 needs to be computed, yes? Then this result will "propagate" and we use it with (3 & 5) to get answer?

By pyramid I meant binary tree, which you can draw in process of calculating the result. On every vertex there is number. You need update value of first element(4), update OR-sum of first two elements 4 | 6, and update value of root of this "tree" XORing (4 | 6) with CALCULATED(you have no need to calculate it again) value of (3 | 5).

Thanks, I managed to understand the key idea behind this problem and learnt a lot with it!! :)

Can you please tell me why we need memory of 2^n size? Because, in other seg tree problems I saw using 4*n size of memory.

Segment tree of size

kneeds at most 2^{n + 1}, wherenis the least number such that 2^{n}≥k.system testing was very fast today (Y) :)

why 4344499 and 4341816 solutions were skipped in system test? There were no additional submission in each of the problems and both of them passed the pretest.

Why my solution for Problem D use 1700+ms and other's avg time is 300ms...

the contest dealt with various kind of problems which was very very helpful to develop the skill for a contestant :)

Hi all! I solved problem C but i don't explain my code get Accepted this problem

I think it is O(t^m) with t<=10, m<=1000 This is my code http://codeforces.com/contest/339/submission/4352722 Thank you :D

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) {

}

use pastebin

http://pastebin.com/MJzJMX3R

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

Oh, thanks you. I think you have same idea with me ,I agree with you :D Your code is very short and clear :D Haghani

Well, problem A and B are easier than before... And at first thought use dfs to solve problem C will get TLE...

Will there be a post with the author's solutions?

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

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

Some code got Accepted on problem E will fail on this test:

4350288 this one for example.

Can you explain the idea behind this testcase?

Some codes didn't work this situation.

4 2 4 1 3 That example is more shorter (doesn't work that test on his program)

What a Ridicule joke... :-|

Do you write the problem set only?

why no pubication mi coment

how to solve problem C?

Can i do it by fenwick tree ?