### vovuh's blog

By vovuh, history, 2 years ago, translation,

1066A - Vova and Train

Tutorial
Solution

1066B - Heaters

Tutorial
Solution 1
Solution 2

1066C - Books Queries

Tutorial
Solution

1066D - Boxes Packing

Tutorial
Solution 1
Solution 2

1066E - Binary Numbers AND Sum

Tutorial
Solution

1066F - Yet another 2D Walking

Tutorial
Solution

• +61

 » 2 years ago, # |   +1 What is the proof for problem E?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +4 First, some easy facts for you:a = sum of pow(2,ai) where ai is array of unique indexes of 1 in binary representation of aand b = sum of pow(2,bi) where bi is array of unique indexes of 1 in binary representation of bpow(2,x) here is 2 raised to the power xthen a&b = sum for i,j of pow(2,ai)&pow(2,bj) where & is bitwise and.now, imagine you've erased k last bits of b, and result will be sum of pow(2,bi-k), and all elements with bi-k < 0 will just vanish.so, answer for the problem is: sum for k,i,j of pow(2,ai)&pow(2,bj-k)ranges for k,i,j think yourself.other fact, for integers x,y: pow(2,x)&pow(2,y) != 0 if and only if x == y and result is pow(2,x)so, answer for the problem is: for k,i,j: if ai == bj-k then add to result pow(2,ai)main observation: you can swap order of "for"s:then answer for the problem is: for i,j,k: if ai == bj-k then add to result pow(2,ai)now, ai, bj, k >= 0, then bj >= ai, so you can ignore all others. also, for any bj >= ai, there is k that ai == bj-k, more precisely k = bj-ai. k is basically how many bits you should erase so ai bit from a will match with bj bit from b.so, answer for the problem is: for i: pow(2,ai)*(count how many bits is 1 at position ai or higher) because any bj >= ai will incorporate in the sum.you can precalculate count of high bits.Now all you have to do is calculate recurrently: ans_next = ans_prev*2+count, where count is how many bits is 1 at current position or higher.This trick works because:a*8+b*4+c*2+d*1 = (a*4+b*2+c*1)*2+d = ((a*4+b)*2+c)*2+dYou could also first precalculate counts of high bits (count of bits on all prefixes), and then go from backward, and in parallel raising 2 to power ai, but it is more nice to do it recurrently
•  » » » 2 years ago, # ^ |   +1 Thank you! Nice explain
 » 2 years ago, # |   0 can someone explain why the answer of D's test 4 is 4?5 4 21 2 1 2 1why it isnt 5?1 1221
•  » » 2 years ago, # ^ |   0 It is given that we have to go from left to right in sequence.You cannot change sequence.
•  » » » 5 months ago, # ^ |   0 I think we can do as follow if 5 items is selected: First, throw the first item with value 1 in the first box, the sizes of the boxes will be: 1, 2, 2, 2 Then, throw the second item with value 2 in the second box, the sizes of the boxes will be: 1, 0, 2, 2 Throw the third item with value 1 in the third box, the sizes will be: 1, 0, 1, 2 Throw the fourth item with value 2 in the fourth box, the sizes will be: 1, 0, 1, 0 Throw the last item with value 1 in the first box, the sizes will be: 0, 0, 1, 0Is there anything wrong with this ? I mean i've definitely not changed the order of inserting items.
•  » » 2 years ago, # ^ |   0 You need to go sequentially i.e after putting 1 you cannot put a 1 again because there are no consecutive 1's. If it was not so then i guess it could not be solved in linear time as of now. Btw an easy and interesting problem :)
•  » » 2 years ago, # ^ |   0 Hobody don't speaks, what him algorithm works good and puts maximum things in box.
 » 2 years ago, # |   0 I want real proof of D. What is in explanation is incomplete. For example fact: if you can fit some sequence in straight order, then you can fit in reverse order. Explanation says that you can go in reverse order in same certain box, and it will still fit. But it doesn't touch the fact that any box may change its content. Then what?You can prove this fact by considering content after algorithm ran forward. Then, if last box still has space for previous item that is not in the box but next item is in the box, then you can move it to the box (closer to the end). And you can repeat this proccess until space in the box won't fit previous item. So, the box will have exactly same content as if you ran algorithm backward. Now you can do the same for all other boxes running backwards. In the end, you'll get the same result as if you ran algorithm backward. But you was starting from result of algorithm if it ran forward. Q.E.D.In my opinion this proof is not enough. I don't know how to get proof of continuality from this. In other words: how do you know this: if you can fit starting from i, and you can't fit starting from i-1, then there is no possible j < i-1, that you can fit starting from j. Huh?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 Is it clear for you that if the last box in the best answer contains some set of objects then the first box in the best answer for the reversed array will contain at least this set of objects and possibly other objects? I think it is clear. So if the first box can contain the same objects let's put these objects in it and go to the next box. In such a way we can construct the same answer as in the straight order. Is it clear now?
•  » » » 2 years ago, # ^ |   0 Indeed, I'm dumb. I just need apply same fact to best answer. If you can fit best answer forward, then you can fit it backward, and for each step, you can make "forward version" of algorithm for each starting position using algorithm discussed above.Very nice problem :)
•  » » 2 years ago, # ^ |   +1 Forget about the previous version of the tutorial. I fixed it and now, I hope, there is more clear proof of this solution.
 » 2 years ago, # |   0 Can't solution for problem C be hacked which used linear search for answering 3rd query. A lot of such solutions passed it.
 » 2 years ago, # |   0 Could anybody help me why I am getting wrong answer for Problem C? Submission
•  » » 2 years ago, # ^ |   0 you have to consider that very first placed book has nothing on left or right..so take that input separately and put 0 distance for it.....and everything else in your solution is right
 » 2 years ago, # |   +6 In the tutorial for problem F, I think it should be py > qy.
•  » » 2 years ago, # ^ |   0 You are right, thank you, fixed
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 why p < q in case px = py, if py > qy?sorry, I understand)
 » 2 years ago, # |   0 Could anyone help me solve the problem that my code at the test 10 of problem B get a TLE??? ignore the chinese please! #include #include using namespace std; #define N 1010 int n,r; int a[N]; int main() { cin>>n>>r; for(int i=1;i<=n;i++) { cin>>a[i]; } int ans=0; int last_warmed_pos=0;//初始最后加热点 while(last_warmed_pos=max(0,last_warmed_pos-r+1);i--) { if(a[i]==1&&i-r<=last_warmed_pos)//找到最右端的h使加热范围覆盖进入last_warmed_pos //注意这里的i-r<=last_warmed_pos 所找h的最左未加热部分要确保已加热 //等价于i-r+1<=last_warmed_pos+1 所找h的最左加热起点要小于等于下一个加热点 //而不是i-r+1<=last_warmed_pos 错误！！！ { next_h_pos=i; //cout<<"next h:"<
•  » » 2 years ago, # ^ |   0 last_warmed_pos do not increase test: 2 1 1 0
•  » » » 2 years ago, # ^ |   0 Thank you! l just find the reason that i should > max(0,last_warmed_pos-r+1) rather than >=.:)
 » 2 years ago, # |   0 Can anyone tell me why my FFT gets Wrong Answer on test 3 in problem E? Thanks in advance... #include using namespace std; typedef long long int LL; LL MOD = 998244353; const int N = 524288; double PI = acos(-1); struct comp { double re, im; comp operator*(const comp& a){ comp ret; ret.re = re * a.re - im * a.im; ret.im = re * a.im + im * a.re; return ret; } comp operator+(const comp& a){ comp ret; ret.re = re + a.re; ret.im = im + a.im; return ret; } comp operator-(const comp& a){ comp ret; ret.re = re - a.re; ret.im = im - a.im; return ret; } }; int getord(int x){ int ret = 0; while ((1 << ret) < x) { ret++; } return ret; } comp tmp[N]; comp A[N]; comp B[N]; void fft(comp* ar, int n, int mode) { if (n == 1) return; comp base; base.re = cos(2*PI/n); base.im = sin(2*PI/n); if (mode) base.im *= -1; comp cur; cur.re = 1; cur.im = 0; int dnc = n/2; for (int i = 0; i < dnc; i++) { tmp[i] = ar[i*2 + 1]; } for (int i = 0; i < dnc; i++) { ar[i] = ar[i*2]; } for (int i = 0; i < dnc; i++) { ar[i+dnc] = tmp[i]; } fft(ar, dnc, mode); fft(ar + dnc, dnc, mode); for (int i = 0; i < dnc; i++) { comp ta = ar[i]; comp tb = ar[i+dnc] * cur; ar[i] = ta + tb; ar[i+dnc] = ta - tb; cur = cur * base; } } char str1[200005]; char str2[200005]; int main(){ int n, m; scanf("%d%d", &n, &m); scanf("%s", str1); scanf("%s", str2); int L = (1 << getord(n+m+2)); for (int i = 0; i < L; i++) { A[i].re = A[i].im = 0; B[i].re = B[i].im = 0; } LL mul = 1; for (int i = 0; i < n; i++) { if (str1[n-i-1] == '1') { A[n-i-1 + 1].re = mul; } mul = (mul*2)%MOD; } for (int i = 0; i < m; i++) { if (str2[i] == '1') { B[m-i-1 + 1].re = 1; } } fft(A, L, 0); fft(B, L, 0); for (int i = 0; i < L; i++) { A[i] = A[i] * B[i]; } fft(A, L, 1); LL ans = 0; for (int i = n + 1; i < L; i++) { LL tmp = fmod((A[i].re + 0.5) / L, MOD); ans += tmp; ans %= MOD; } printf("%lld\n", ans); } 
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 My guess is because of the roundoff error the use of floating-point values induces. Your FFT implementation uses doubles, which are imprecise for large numbers. The solution works on small inputs, but fails on larger ones, for example: https://ideone.com/cdIzUi
•  » » » 2 years ago, # ^ |   0 Would it be possible for NTT to pass large test cases then?
 » 2 years ago, # |   0 How to solve D if those distribution in which there my be no empty space left for some last objects and they are not put in any box is also valid like some continuous subarray can also produce maximum answer no matter it reaches to end or not. Ex: n = 5, m = 1, k = 6, A[i] = (6 2 2 2 6) answer: 3 (from element 2 to 4)
 » 2 years ago, # |   0 Clean implementations, really loved it <3
 » 2 years ago, # | ← Rev. 2 →   0 Single pass solution for B: #include int n,r,p,q,c,i,b; int main(){ scanf("%d%d",&n,&r); while(ip?-1:i>q?c+1:c); } 
 » 2 years ago, # | ← Rev. 2 →   0 Can anyone please find a bug in my problem B code.....44389702Its giving runtime error on test case 5 #include using namespace std; typedef long long ll; #define mem(dp,a) memset(dp,a,sizeof dp) #define rep(i,a,b) for(ll i=a;i=b;i--) #define pb(x) push_back(x) #define sl(a) scanf("%lld",&a) #define si(a) scanf("%d",&a) ll INF=1ll<<60; ll MOD=1000000007; int main() { ll n,k;sl(n);sl(k); ll a[n]; rep(i,0,n) sl(a[i]); ll last=-1; rep(i,0,k) { if(a[i]==1) last=i; } ll c=0,cant=0; if(last!=-1) c=1; else cant=1; while(last+k
 » 2 years ago, # |   0 1066E — Binary Numbers AND SumHow to approach this question ?
»
2 years ago, # |
0

hey,I'm not clear about level .anybody help me .

# 1066F

 » 2 years ago, # |   0 I am getting wrong on 4rth test case of F problem Please help if anyone knows the problem here is my code for the samehttp://codeforces.com/contest/1066/submission/44486589Thanks in advance
 » 2 years ago, # |   0 in problem A how can we proof the formula that calculate the number of lanterns that are in range ( l-r)
 » 2 years ago, # |   0 Hi, can someone explain to me in details about how does problem A works? I only get a few parts out of the entire statements.
 » 23 months ago, # |   0 How do we get the complexity in approach 1 as O(nlogn). The n part of the complexity is clear with me I am not able to figure out the presence of logn, where does it come from? Kindly explain. Thanks.
 » 23 months ago, # |   0 Can anyone explain tutorial for 1066C. I tried by arraylist in Java, resulted in TLE. Could not get the given approach in tutorial?
 » 22 months ago, # |   0 can someone help me with my solution for b , it is getting wrong answer on test case 5 https://codeforces.com/contest/1066/submission/47869871
 » 21 month(s) ago, # |   0 why its (l-1)/v in prblm B??
 » 17 months ago, # |   0 I've solved B using DP 55118824
•  » » 16 months ago, # ^ |   0 I solved A using DP