### MikeMirzayanov's blog

By MikeMirzayanov, history, 6 years ago,

Welcome to 2016-2017 CT S03E03: Codeforces Trainings Season 3 Episode 3 - 2007-2008 ACM-ICPC, Central European Regional Contest 2007 (CERC 07). The training duration is 4.30 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be available as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

We are planning to start on September, 21, 2016 13:10 (UTC).

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

• +104

 » 6 years ago, # | ← Rev. 3 →   +7 Typo in title: S03E02 (should be S03E03)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 same typo is in gym page contest name too...
 » 6 years ago, # |   0 available*
 » 6 years ago, # |   0 how to register for it?
•  » » 6 years ago, # ^ |   +11 Follow this
 » 6 years ago, # |   0 is Season 03 Episode 02 editorial available ?????
 » 6 years ago, # |   +44 What's wrong with the problems?
 » 6 years ago, # | ← Rev. 2 →   0 Please, help me to find a max sum of test cases in problem — A?
 » 6 years ago, # |   0 How to solve Problem Weird Numbers ?
•  » » 6 years ago, # ^ | ← Rev. 3 →   +9 I'll explain my solution, which I'm pretty sure is not optimal. It's clear that with a negative base, odd positions will be negative and even positions will be positive. So all numbers in base  - b can be expressed as e + o where e is some number in base b with all zeroes in odd positions and o is some number in base b with all zeroes in even positions. So what I did was generate all said numbers up to 109 and store them in E[b] and O[b], where b is the base. Then for every query [b, x] (that is express number x in base  - b), I iterate over all e in E[b] and check if e - x is in O[b]. If it is, I just have to print e + o in base b. The other type of queries is trivial, is just processing a number in base  - b.
•  » » » 6 years ago, # ^ |   +8 Thanks for the explanation!!! :)
•  » » 6 years ago, # ^ |   +12 I'll explain my solution, which I think is optimal.Its almost the same as converting in positive bases. Lets convert N from base 10 to base b (b < 0):N = a0·b0 + a1·b1 + ... + an·bnnote that , so (N - a0) / b = a1·b0 + ... + an·bn - 1 and we can repeat recursively.
•  » » » 6 years ago, # ^ |   +8 Thanks for the explanation!!! :)
 » 6 years ago, # |   +5 Anybody knows where can I find the editorial ( :Thanks
 » 6 years ago, # | ← Rev. 2 →   +5 Why did answer "4 2 3 4" fail on the second sample? (Problem S. Robotic Sort)
•  » » 6 years ago, # ^ |   +8 It is said in statement: their mutual order must be preserved: the one that was given first in the initial order must be placed before the others in the final order too. So you should also consider the INITIAL indexes of elements.
 » 6 years ago, # |   0 What is solution for problem C(Phone Cell)? We thought that problen can be solved by geometric invertion, but we don't know, how we can use it.
•  » » 6 years ago, # ^ |   +14 You can find all solutions here: Link
 » 6 years ago, # |   0 Anyone knows what is testcase 2 in P ?
 » 6 years ago, # |   +3 How to solve B? :(
•  » » 6 years ago, # ^ |   +11 Consider all the tiles of row 1. There are m tiles and 2^m ways to select a subset of them to be flipped. Notice that this uniquely determines all the other tiles which needs to be flipped to clear the billboard afterwards.Consider cell(2,1). If cell(1,1) is on, then cell(2,1) must be flipped. And if (1,1) is off, (2,1) should not be flipped. Because after flipping (2,1), (1,1) is on and now there is no way to turn off (1,1) since the columns to be flipped in row 1 is fixed.Complexity: O(2^m * n * m)
•  » » » 6 years ago, # ^ |   0 I used bitmask but it keeps giving me TLE on test 2, I submitted the same code on SPOJ(where time limit is 3.6sec) it got AC, How to get AC when time limit is 1sec using bitmask? my code#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define F first #define S second #define endl "\n" #define pb push_back #define mp make_pair #define bs 1000000007 #define pi 3.141592653589793 #define y1 kjdfshnvoavaofobiopj using namespace std; int n, m, ans, final_ans, newary[17][17]; vectormyvec; char ary[17][17]; bool error; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, 1, -1}; bool pass(int a, int b) { if(a >= 0 && a < n && b >= 0 && b < m) return true; return false; } int main(){ //freopen("input.txt", "r", stdin); //ios_base::sync_with_stdio(0); //cin.tie(0); while(1) { scanf("%d %d", &n, &m); if(n == 0) break; for(int i = 0; i < n; i++) scanf("%s", ary[i]); final_ans = INT_MAX; for(int mask = 0; mask < (1<
•  » » » » 6 years ago, # ^ |   +1 You can optimize your solution with the bitwise operation! Complexity: O(2^m * n) Here is my solution Spoiler using namespace std; const int N = 1123; int t[N]; int d[N], cnt[(1 << 18)], w[(1 << 18)]; int bit(int x) { int cnt = 0; while(x > 0) { cnt ++; x &= x — 1; } return cnt; } int n, m; void funk(int n, int m) { int i, j, k; char x; for(i = 1; i <= n; i ++) { d[i] = 0; for(j = 0; j < m; j ++) { scanf(" %c", &x); d[i] += (x == 'X') * (1 << j); } } int ans = 1e9; int s = 0; for(i = 0; i < (1 << m); i ++) { s = 0; for(j = 1; j <= n; j ++) { t[j] = d[j]; } t[1] ^= w[i] & ((1 << m) - 1); t[2] ^= i; s += cnt[i]; for(j = 2; j <= n; j ++) { t[j] ^= (w[t[j - 1]] & ((1 << m) - 1)); t[j + 1] ^= t[j - 1]; s += cnt[(t[j - 1])]; } if(t[n] == 0) ans = min(ans, s); } if(ans != 1e9) { printf("You have to tap %d tiles.\n", ans); } else { puts("Damaged billboard."); } } main() { for(int i = 0; i < (1 << 16); i ++) { for(int j = 0; j < 16; j ++) { int c = ((i & (1 << j)) != 0); c += (j != 0 && ((i & (1 << (j - 1))) != 0)); c += (j != 15 && ((i & (1 << (j + 1))) != 0)); c %= 2; if(c) w[i] ^= (1 << j); } cnt[i] = bit(i); } while(cin >> n >> m) { if(n == 0 && m == 0) break; funk(n, m); }  
•  » » 6 years ago, # ^ |   +3 Try all possibilities for the first row, after that it's easy to see which ones you should switch in the second row (the ones that are still black in the first row), then the same applies for the third row, etc..
•  » » 6 years ago, # ^ |   +8 We actually solved it using systems of linear equations.Suppose aij is the number of times a tile at row i and column j gets swapped. First of all, aij ≤ 1. Then, for each position (i, j) we can get it's final color as (initial_colorij + aij + ai - 1, j + ai + 1, j + ai, j - 1 + ai, j + 1) mod 2. That gives as a system of equations with n·m equations and unknowns. Sure it's not as easy to code, but it gives better time asymptotic.
•  » » » 6 years ago, # ^ |   +8 The system of equations can have many solutions, how do you choose the one that minimizes the number of taps?
•  » » » » 6 years ago, # ^ |   +8 Great question!It turns out, that number of free variables (meaning we can choose any value for them) is not that big (7 for 16x16 matrix). We can search over all possible values for this (at max 7) free values and find other unknowns, then choose one that minimises number of taps.
 » 6 years ago, # |   +5 Can anyone explain the solution for Problem C?