### Golovanov399's blog

By Golovanov399, history, 3 years ago,  Tutorial of Technocup 2019 - Elimination Round 2 Comments (65)
 » 3 years ago, # | ← Rev. 2 →   Can someone explain exactly why does greedy solution works for Problem C ? Update :- Understood Now, after translation of editorial
•  » » 3 years ago, # ^ | ← Rev. 2 →   The greedy algorithm I use is a little bit more complicated but you can catch what I mean more easily.The algorithm goes as follows:1.binary search part. Use binary search to find how much lecture notes you can read In the two days. greedy part for the checking function of binary search. Iterate through each note from x to 1. For note i, If you can put it in the day which has fewer hours to spend, It's always better. So we just iterate through. If we find a note that we can't put it in any of the days, we try a smaller amount. To get the answer uses the same algorithm as the checking part. Just iterate from x to 1, and put the note in the day which has fewer hours to spend. If you didn't get this, I may post my code:44658856
 » Quick Editorials! And the editorials for 1031B & 1031C in English were mistakenly published in Russian.Only I used DP for Div.2 B (maybe because I am just a Pupil), sadly?
•  » » Wait please, they're gonna be translated
 » can u plz explain why this is wrong ?? Div2D 44650538
 » Can you proof why this part-> "Let's iterate over all lecture notes from x to 1 , and on each step we put it into the first day if we can, otherwise if in the first day we have w > 0 free time then we put the lecture note w < x to the first day."Why mentioned part gives the optimal solution?
•  » » There are two possibilities: All lecture notes are in the first day, this case is trivial. When we tried to put the x-th lecture note into the first day, there was only w free hours. Let's put the lecture w instead then. Now the first day is full, and since a + b is at least x(x + 1) / 2, the second day is long enough to read the remaining notes.
•  » » » » I propose an algorithm to divide all lecture notes into two groups properly. If I started with 1, I couldn't fill the first day because the w-th lecture note would have been already used, so iterating from the greatest is crucial for me.You can try to start with 1 and act in another way, maybe there is an algorithm which solves the problem.
•  » » » » » I tried and it worked. I have started with 1 and filled the first day. The strategy I followed while filling is, I greedily filled the numbers until their sum became greater than the capacity of the first day. Then I removed (sum — a) from the set of the first day. And filled rest in the second day. It worked. Here is my submission : http://codeforces.com/contest/1072/submission/44715934
•  » » » » » » Yeah I see, it's ok, you fill the first day anyway, but you do it with some set like {1, 2, ..., k - 1, k + 1, ..., l - 2, l - 1, l}, while author does it with a set like {k, l, l + 1, l + 2, ..., n}.
 » 3 years ago, # | ← Rev. 2 →   Can somebody please explain to me why my O(n^2) code for problem D is getting TLE? Help is very appreciated 44655948EDIT:It's the string comparison, my mistake
 » Can anyone please help me with question B. I am new to programming and kind of stuck. how to move ahead with the hints given above?
•  » » 3 years ago, # ^ | ← Rev. 2 →   I'm not a native English speaker, sorry for my poor explanation.It's easy to find that if we get the first two items of the series t, we will be able to determinate whether it's possible to build a t meets the conditions.Then we will try every possibilities for t1 and t2, we will be able to find the relationships between t and a, b.Finally we try every possibilities for the first two items (not so much, though), and find if it is possible to meet every ai and bi (we have one item of ti, and it's easy to determinate whether it's OK for the other items).My solution using DP is described as following: Let dp[i][j] standing for the possibility of i-th number of t is j, and dp[i][j] means which number is the number before i-th number of j, we can easily iterate k from 0 to 3 for the last number of t, and we can get: Specially, we have dp = dp = dp = dp = 1.Then we can judge if dp[n][·] is 1, for YES or NO, and if the answer is YES, use dp[n][·] with a stack to print t.
•  » » Just use simple depth-first-search. The hint means(I think) that you when you brute force the problem, you will not get a TLE.
•  » » » Hi, can you elaborate more on your DFS approach? Thanks!
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   Well this isn't so hard. The code is like the folloingIf the process give no answer, just output "NO".44657446
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   It seems that DFS can be hacked by this data:input: 100000 3 3 3 2 3 ...(repeat) 0 2 0 0 0 ...(repeat) output: YES 1 2 3 0 2 ...(repeat) DFS will get TLE or RE (tested in my computer).
•  » » » » Sorry for my reckless. It seems my computer is too weak to run this data. I find that DFS is right to solve this problem. Very sorry!Because if ti has been determined, ti + 1 will have only one value to choose. Specially, if a = 3, b = 0, t can be 0, 1, 2, 3. But if ti has been determined, we should not worry about ti + 1.
• »
»

There is some interesting observation.

there exist at most one value of t(i) for specific value of t(i+1),a(i),b(i).

formally, if there exist t(i) such that t(i) | t(i+1) == a(i) and t(i)&t(i+1)==b(i) then t(i) can be one of the {0,1,2,3}. it means that the equations t(i) | t(i+1) == a(i), t(i) & t(i+1) == b(i) has exactly one solution of t(i) if we know the value of t(i+1),a(i),b(i) or doesn't exist.

you can see this fact using my below code. just run the code and you will see that observation. ~~~~~

# include<bits/stdc++.h>

using namespace std;

int main(){ for(int i = 0;i<=3;i++){ // values of a(i)

for(int j = 0;j<=3;j++){ // values of b(i)

for(int k = 0;k<=3;k++){ // values of t(i+1)

cout << i << " " << j << " " << k << " -> ";

for(int l = 0;l<=3;l++){ // possible values of t(i)
if((k & l )== j && ((k|l) == i)){
cout << l << " ";
}
}
cout << endl;
}
}
}
return 0;

} ~~~~~

now simply take t(n) as 0,1,2,3 one by one and find t(n-1),t(n-2),t(n-3)... if there exist sequence for some t(n) then print it otherwise change the value of t(n)..

see this for full code (c++)

 » Problem 1031A - Golden Plate can be calculated directly by formula:2k(w + h - 4k + 2)
 » can you please explain problem B a little more ? i was not applying dp . the thing i concluded was these two conditions 1. a[i]|b[i]=a[i] 2. a[i]&b[i]=b[i] . If any of these fails for any index ,it will show "NO". How to proceed for rest solution ?
•  » » I'm not a native English speaker, sorry for my poor explanation.There is something interesting about Bitwise operation:a^b=(a|b)-(a&b).So let c[i]=a[i]-b[i],then just let t=0~4 ,and calculate the others t by array c.After this,just judge the array t if or not satisfy the conditions
 » Golovanov399 I think there is some mistake in editorial of 1031B — Curiosity Has No Limits because 4th case "If t1=0 and a1=1 and b1=1 then t2= 1" is wrong as t2 can't have any value because since t1 is 0 , b1 can never be 1 as b1=t1&t2, instead it should be "then there is no such t2".
•  » » i agree
 » Can someone explain their solution for 1031D plz ?
 » Can someone help be with this solution for 1031B ? Link:44642434
 » how to solve the Div2.D with above algorithm and not get MLE?
 » My solution of C is showing error "wrong output format Unexpected end of file — int32 expected" someone please explain:- here is my code https://codeforces.com/contest/1072/submission/44658102
 » In Div2D, how to write DP for the lexicographically smallest path from (i, j) to (n, m) in O(n2) memory? My solution requires O(n3) memory (with recursion using memoization).
•  » » 3 years ago, # ^ | ← Rev. 2 →   I used something bfs-liked instead , I have the list of last-minimum block at that length then(For each row there can only be at most 1 element so this list will never exceed n) name A. Considering this example bcc caa ggg We know that the first character must be 'b' , second character must be 'c' , BUT WE DO NOT KNOW IF THE 'c' IS FROM (1,2) or (2,1) , so after we append 'c' to answer our A must contain both (1,2) and (2,1) for future use.For the next length each block in A can generate 2 more blocks. For the sake of simplicity i used std::set name B to store it to get rid of duplicate blocks and auto sort for me.Then the next character of the answer is value of the first block in the set(set sorted for me). So I get all the blocks from B which has the value equal to the minimum block back into A and repeat until we reached the answer's length. This way I do not need to store all the string length but only 1 letter for each block in list A. So the total memory used for this step never exceeds O(n) I guess...Sorry for my bad English
•  » » » 3 years ago, # ^ | ← Rev. 3 →   Thank you! This makes sense. But I think this requires O(n2) time for every time we ask for path from some (i, j) to (n, m). If there are multiple such (i, j) pairs (let M) to check, this would take O(M × n2) time, where M itself can be atmost O(n2). How to handle this? UPDATE: I understand it now. We will initialize our set B with these pairs.
 » In question C, why can't be sum of the lecture notes be exactly equal to a+b, it will only affect the last term i.e. x; the sum n+m will still remain same!!
•  » » 3 years ago, # ^ | ← Rev. 93 →   it can be but it won't increase the count of lectures. ex: a = 9, b = 12 output: 2 3 6 4 1 2 4 5 but for a = 10 and b = 12 output: 2 3 7 4 1 2 4 5 OR 2 3 6 4 1 2 4 5 here the sum of lecture notes is exactly a+b but it doesn't affect the count.
 » Why we always can make all elements be equal to zero when n>=8 in problem 1031e?
•  » » You can run bruteforce
•  » » 3 years ago, # ^ | ← Rev. 2 →   If you have >= 8, you can get rid of a 1 in any position.eg:A) 0 0 0 1 0 0 0 0 Can be done with: 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 B) 0 0 1 0 0 0 0 0 Can be done with: 0 0 1 1 1 0 0 0 thus creating 2 instances of (A)C) 0 1 0 0 0 0 0 0 Can be done with: 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 Similarly, D) 1 0 0 0 0 0 0 0 Can be done with: 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 Ones on the right hand side are of course symmetrical
•  » » » Excuse me,could you please explain it more clearly?I am not very smart so I can't understand it.Sorry,but PLEASE!!
 » In the problem C Cram time, I did the exact same thing, and i guess it runs in O(n)time, still it showed me Time limit in test case 15. I would really appreciate it if someone could check my code once, please. http://codeforces.com/contest/1072/submission/4464724144647241Thanks a lot!
•  » » for(i=max(a,b);i>=0;i--) { if(((i*(i+1))/2)<=a+b) break; } this part gives TLE; reduce this through binary_search or directly use quadratic formula;
•  » » » » long long int p[a],q[b]; it needs a lot memory for a, b <= 1e9.
 » I have an alternate solution of Div1D without graphs. We can use dynamic programming on each vector (x1, x2, ..., xn).Assuming that the upper bound of number of divisors isn't great, we have a fast DP the states are (prod, pos), where prod is the target product, pos is the current position in the vector. Iterating over all divisors of prod, let's assume that k is a divisor of prod, then a possible state is (prod / k, pos + 1) and it "costs" abs(x[pos] - k) to go to this state. When we reached the end of the vector, we have another mini-DP to calculate the minimal number of operations to get remaining prod. Then, the answer for (x1, x2, ..., xn) and (y1, y2, ..., yn) is min(dp(i, 0, x) + dp(i, 0, y)), 0 ≤ i ≤ 256.Due to very small constants it works in no memory and in relatively small time.
 » I think Div.1 C involves some background knowledge about linear algebra. Each operation of flipping ax, ay, az can be viewed as a 01-vector v where only vx, vy, vz are 1. We want to find a linear combination of all such vectors that equals to the given array (modulo 2), and it is easy to verify that only when n > 7 the rank of all such vectors equals to n.
•  » » LOL uflbyk we just learned this stuff
 » http://codeforces.com/contest/1072/submission/44700766 failed at testcase 6.Approach: generate all possible pairs in (0,1,2,3) like p1 = {0,1},{0,2}... for each pair if condition satisfied then print . see my code.
 » Can Anyone point out mistake in my code.(Div2 C) http://codeforces.com/contest/1072/submission/44638820
 » Can anyone explain the solution of problem D ?
 » 3 years ago, # | ← Rev. 2 →   In Problem C My code shows time limit exceed at test case 15.....please explain why is this happening while I follow the same concept as mentioned above.... 44751444 My code is working properly on test case 15 at (http://ideone.com)
•  » » long is 32-bit on Codeforces but 64-bit on Ideone. Use long long instead.
 » How should actually brute force in div2 E work when we are left with <=10 elements?
 » For Div1E, do we really need to consider precision issues and prove that our solutions will be precise enough? Why don't we prove it for other problems which also require floating-point arithmetic?
•  » » As a contestant you don't have to prove anything, but as the editorialist, I felt responsible for doing this.
 » 3 years ago, # | ← Rev. 2 →   Problem C.I want to know why I get WA in test15. I put 1,2...,n into A as many as possible. defined the rest of A is x, I remove the n and put the n+x into A. the I put from 1 to INF if it is not in A.Your text to link here...
 » for Div.2 A I think the input 5 5 2; The answer is 17. Am I right ? ( if you add this to the main test, many would WA...
•  » » Even for 5 5 1 the answer is already 20 > 17 as the number of border cells
•  » » » 3 years ago, # ^ | ← Rev. 2 →   No, answer for 5 5 1 is 16But 5 5 2 is impossible because of restriction on k
•  » » » » You see, I always had bad math
 » Can someone sent me code-solution of tasks from this contest, please?
 » Is it possible to add data after the contest?I found that almost all AC submissions of Div1.E was wrong
•  » » It's possible (the solutions won't be rejudged, though). Moreover, if you happen to mean all AC submissions of Div2.E and during the contest, then more tests have already been added.
• »
»
»

I see.There are 3 small sets of data.They are made when I debug my program using some of the AC codes.But I think my outputs are correct but their outputs are wrong.Would you please check if they're correct?

And I'd like to thank you for holding such a nice contest.

#### in1

3 5 5
3 4
2 1 0
4 2 1
5 4 2


#### out1

1.666667


#### in2

2 5 5
5 0
1 0 0
2 4 0


#### out2

5.000000


#### in3

3 4 4
2 3
2 2 2
4 1 1
5 0 0


#### out3

0.400000

•  » » » » I've just started investigating your tests, and in each of them there is a point with y = 0, while it's forbidden in the problem. As far as I remember, it's essential for the solution.
•  » » » » » Oh,I didn't see the data range clearly.I'm so sorry for bothering you.Then it turns out that most of the AC codes are correct but only a few have problems.in 3 5 5 3 2 2 3 3 4 3 2 6 1 4 out 0.473684 I'm trying to find out why it works.