Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### Fefer_Ivan's blog

By Fefer_Ivan, 5 years ago, translation, ,

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?

•
• +215
•

 » 5 years ago, # |   -65 Too late and too short announcement!
•  » » 5 years ago, # ^ |   +78 Do you use codeforces to take part in contests or to read announcements?
•  » » » 5 years ago, # ^ |   -58 It was just my thought about the announcement!
 » 5 years ago, # |   -23 I hope to it has DP && graph problems ... thanks for great time
 » 5 years ago, # |   +24 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...
•  » » 5 years ago, # ^ |   0 Yep, we're trying
•  » » 5 years ago, # ^ |   +3 There is no Cow Level!
 » 5 years ago, # |   -12 Really intresting [but easy!] Problemset and nice horse joke and photo!! Thank U a lot!!
•  » » 5 years ago, # ^ |   -6 Are you sure that this round easy? Especially problem E? I don't think so
•  » » » 5 years ago, # ^ |   0 Just Problem E is not easy!!Usually Problem Ds are harder than Xenia and Bit Operations...
•  » » » » 5 years ago, # ^ |   0 Ooops! Problem C : Trinket
 » 5 years ago, # |   +7 Very nice problems.. Thanks to authors...!!!
 » 5 years ago, # |   +36 How to solve E?
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 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).
•  » » » 5 years ago, # ^ |   0 Imaginative ""!I thought you're right as 3 swaps would split the sequence into 7 part (14 point) at most.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 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?
 » 5 years ago, # |   -26 WE WANT EXTRA TIME FOR SERVER PROBLEMS
 » 5 years ago, # |   -13 pretests are too weak!
 » 5 years ago, # | ← Rev. 2 →   +11 nice system testing! ))) thanks
 » 5 years ago, # | ← Rev. 2 →   0 How to Solve D?
•  » » 5 years ago, # ^ |   0 I you knew Segment tree you could solve it!!!
•  » » » 5 years ago, # ^ |   0 enlighten me please, I could't find a suitable Data Structure for it
•  » » » 5 years ago, # ^ |   +3 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.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +1 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 :)
•  » » » 5 years ago, # ^ |   0 GOOOD ONE bro !!! Helped a lot, I couldn't see that way ;)
 » 5 years ago, # |   +22 Nuff said.
•  » » 5 years ago, # ^ |   +29 swap(problem C,problem D); 
 » 5 years ago, # |   +9 Problem C is very tricky :(
•  » » 5 years ago, # ^ |   +3 I failed C as well, however the contest was interesting and the problems were very well explained. Thank you very much Fefer_Ivan.
•  » » 5 years ago, # ^ |   0 I get AC after the end of competition. Just because I add code that enumerate the first weight of left scale. so sad...
 » 5 years ago, # | ← Rev. 3 →   +2 Got it... Sry
•  » » 5 years ago, # ^ | ← Rev. 2 →   +11 Your program didn't print anything in output
 » 5 years ago, # | ← Rev. 3 →   -15 7 successful hacks for Problem C just with this simple test: 1110000000 4 :O Just Like my previous avatar!
•  » » 5 years ago, # ^ |   +4 ~650 solutions failed on that test (number 34)
•  » » » 5 years ago, # ^ |   0 Its a very simple but clever test!!
•  » » » 5 years ago, # ^ |   0 yep I failed there too
 » 5 years ago, # |   -11 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.
 » 5 years ago, # |   +5 Can anybody explain why do this solution get AC?
•  » » 5 years ago, # ^ |   0 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
•  » » » 5 years ago, # ^ |   +5 No, your answer is reversed.
•  » » » » 5 years ago, # ^ |   -8 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.
 » 5 years ago, # |   +15 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? #include #include #include using namespace std; char s[15]; int m,last,cnt; vector v,ans; int l,r; int main() { scanf("%s%d",s,&m); for(int i=0; i<10; i++) if(s[i]=='1') v.push_back(i+1); while(1) { int i; for(i=0;ir) { last=v[i]; l+=last; ans.push_back(last); break; } } if(i==v.size()) break; cnt++; if(cnt==m) break; for(i=0;il) { last=v[i]; r+=last; ans.push_back(last); break; } } if(i==v.size()) break; cnt++; if(cnt==m) break; } if(cnt==m) { printf("YES\n"); for(int i=0;i
•  » » 5 years ago, # ^ |   +13 He sent me the same message also.
•  » » 5 years ago, # ^ |   +10 He sent me the same message! Of course I ignored him...
 » 5 years ago, # | ← Rev. 5 →   +3 "she writes down the bit-wise OR of adjacent elements of sequence a" if this sentences wasnt wrong than1 . step => a1 , a2 , a3 , a4 2 . step => a1|a2 , a2|a3 , a3|a43 . step => (a1|a2) ^ (a2|a3) ......but problem is 1 . step => a1 , a2 , a3 , a4 2 . step => a1|a2 , a3|a43 . 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.
•  » » 5 years ago, # ^ |   +4 Yeah I made the same mistake at first as well. Just goes to show that reading the sample helps. :)
 » 5 years ago, # |   0 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?
•  » » 5 years ago, # ^ |   0 I'm so silly huh...I know why I've made that mistake...
 » 5 years ago, # |   +14 imho, D much more easier than C.
•  » » 5 years ago, # ^ |   0 it is(just a kind of feeling)! but i dont understand the meaning of the problem D. perhaps i should learn maths harder..
•  » » » 5 years ago, # ^ |   +2 this problem is just standard segment tree problem , not related to maths
•  » » » » 5 years ago, # ^ |   -11 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.
 » 5 years ago, # |   0 How to approach D efficiently?
•  » » 5 years ago, # ^ | ← Rev. 5 →   0 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 = 2n, elements with indexes more or equal N are leaves and childs of vertex i are 2i and 2i + 1. See my solution
•  » » » 5 years ago, # ^ |   0 I 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?
•  » » » » 5 years ago, # ^ | ← Rev. 4 →   +1 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).
•  » » » » » 5 years ago, # ^ |   0 Thanks, I managed to understand the key idea behind this problem and learnt a lot with it!! :)
•  » » » » » 3 years ago, # ^ |   0 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.
•  » » » » » » 3 years ago, # ^ |   0 Segment tree of size k needs at most 2n + 1, where n is the least number such that 2n ≥ k.
 » 5 years ago, # |   +6 system testing was very fast today (Y) :)
 » 5 years ago, # | ← Rev. 2 →   -6 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.
 » 5 years ago, # |   0 Why my solution for Problem D use 1700+ms and other's avg time is 300ms...
 » 5 years ago, # |   0 the contest dealt with various kind of problems which was very very helpful to develop the skill for a contestant :)
 » 5 years ago, # |   +4 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
•  » » 5 years ago, # ^ |   -21 OMG. really INCREDIBLE. i dont belive that is realy. but it is realy.==> TEST is very low
•  » » 5 years ago, # ^ |   -21 :|
• »
»
5 years ago, # ^ |
-38

# 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;


}

•  » » » 5 years ago, # ^ |   +1 use pastebin
•  » » » » 5 years ago, # ^ |   -7
•  » » 5 years ago, # ^ | ← Rev. 2 →   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
•  » » » 5 years ago, # ^ |   0 Oh, thanks you. I think you have same idea with me ,I agree with you :D Your code is very short and clear :D HFN
 » 5 years ago, # |   0 Well, problem A and B are easier than before... And at first thought use dfs to solve problem C will get TLE...
 » 5 years ago, # |   +1 Will there be a post with the author's solutions?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 He wrote it within few hours of contest. GL :)http://codeforces.com/blog/entry/8725
 » 5 years ago, # | ← Rev. 2 →   +11 Some code got Accepted on problem E will fail on this test: 10 5 4 3 2 10 1 9 8 7 6 
•  » » 5 years ago, # ^ |   0 4350288 this one for example.
•  » » 5 years ago, # ^ |   0 Can you explain the idea behind this testcase?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +5 --[-----first swap-----]-------------------------------------------- ---------------------------------[--------second swap------------]-- -----------------[------------third swap-------------]-------------- Some codes didn't work this situation.
•  » » » » 5 years ago, # ^ |   +5 4 2 4 1 3 That example is more shorter (doesn't work that test on his program)
 » 5 years ago, # |   0 What a Ridicule joke... :-|
 » 5 years ago, # |   -8 Do you write the problem set only?
 » 5 years ago, # |   -8 why no pubication mi coment
 » 5 years ago, # |   0 how to solve problem C?