### PikMike's blog

By PikMike, history, 2 weeks ago, translation, ,

1036A - Function Height

Tutorial
Solution (Vovuh)

1036B - Diagonal Walking v.2

Tutorial
Solution (Vovuh)

1036C - Classy Numbers

Tutorial
Solution with combinatorics (PikMike)
Solution with precalc (PikMike)

1036D - Vasya and Arrays

Tutorial
Solution (Ajosteen)

1036E - Covered Points

Tutorial
Solution (PikMike)

1036F - Relatively Prime Powers

Tutorial
Solution (PikMike)

1036G - Sources and Sinks

Tutorial
Solution (BledDest)

•
• +44
•

 » 2 weeks ago, # | ← Rev. 2 →   +16 I found a strange thing in F. Two ACs codes output different result. Detail in https://codeforces.com/blog/entry/61728. Can anyone help me?
 » 2 weeks ago, # |   0 Can someone prove the author's solution for B?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +1 i thought about this problem lot after the contest.what i came up with is that there is 8 cases for m,n,k: odd/odd/odd, odd/odd/even....even/even/even. all cases reduce down to the odd/odd/odd case or the even/even/even case. we can see that it is possible to solve the odd/odd/odd or even/even/even case using all diagonal moves as long as m,n is reachable in k moves.for an example of "reduction", the even/odd/odd case reduces to the even/even/even case because you can "spend" one non-diagonal move in the n-direction. [1]the author's solution is basically "reducing" down all cases to o/o/o or e/e/e cases with mod. see my coded sol here: 42690270[1] in fact, the o/o/o case reduces down to the e/e/e case by spending 1 diagonal move
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 We can change the problem to this: you should use 1/-1/0 k times totally to get m and n respectively.(remember that m and n are nothing to do with) And according to the problem and greedy algorithm the num of 1/-1 should be as much as possible.for m we should at least use 1 m times and if km then we can add the combination of (1 and -1), then the left (m-k)%2(1 or none) should be 0. for n we do the same.so now for m and n, the num of 0 should be at least (m-k)%2 and (n-k)%2 respectively. And for the 0 in m, we must use a 1/-1 in n to construct a valid move (0,1) or (0,-1), the same for n. at last there are (m-k)%2+(n-k)%2 moves not diagonal, so the answer is k-(m-k)%2-(n-k)%2.
 » 2 weeks ago, # |   +26 Randomized solution for problem G: here
•  » » 2 weeks ago, # ^ |   0 cool.
•  » » 13 days ago, # ^ |   0 cool
 » 2 weeks ago, # |   0 Wasted 1 hour trying to solve a harder version of Problem C. I thought classy numbers were those number which had the number of distinct non zero digits <= 3. And when TC 2 and 3 were not passing, I tried so hard debugging.After successfully wasting 1 hour, read the question again and BAM!!
•  » » 12 days ago, # ^ |   0 what it mean prefix in the tutorial for C??
 » 2 weeks ago, # |   0 The data for G maybe too weak? I can easily hack my code.
 » 2 weeks ago, # |   +18 The problem A is so easy, but I solved it late because of my poor English and my poor wi-fi.
 » 2 weeks ago, # |   0 In problem E, Can anyone please give proof of why exactly GCD + 1 value will give integer co-ordinates?
•  » » 13 days ago, # ^ |   +3
•  » » » 13 days ago, # ^ |   0 Thanks ^_^
 » 13 days ago, # | ← Rev. 2 →   0 [Deleted]
 » 13 days ago, # | ← Rev. 4 →   0 http://codeforces.com/contest/1036/submission/42706346 can someone pls point out the mistake i am making. upd :: got it
 » 13 days ago, # |   0 In Problem G, it is possible to find for every sources all achievable sinks in a linear time. For this it is necessary to store in each visited vertex an integer (the set of bits of achievable sinks).
•  » » 12 days ago, # ^ |   0 Can you explain the approach behind recursion in problem C?
 » 13 days ago, # |   0 Can problem F be solved with some precalculations (generations of correct numbers), simular to problem C?
 » 13 days ago, # |   0 can anyone explain classy numbers editorial ??
 » 12 days ago, # |   0 there is a easy way to solve problem C with DP :) 42742195
•  » » 10 days ago, # ^ |   0 It seems to be an interesting approach, but I don't really understand it. Could you please explain it briefly?
•  » » » 10 days ago, # ^ |   0 f(i,j) means The i th bit of a number(unit's digit,ten's digit...) and already has j non-zero digits.DP uses flag to control upper bound.If it is not the upper bound,we can remember the result of f(x,y).(That's why I initialize f to -1 and update f(x,y) when flag=0).f(x,y) will be accessed multiple times, so we can speed it up by remember it .My English is poor( I use the google translate QAQ ).
 » 12 days ago, # |   0 Why dont we use -C instead of C? I read in internet that the formula will use -C instead of C? I mean this fragment: long long dx = det(l1.C, l1.B, l2.C, l2.B); long long dy = det(l1.A, l1.C, l2.A, l2.C);
•  » » 12 days ago, # ^ |   +3 By the properties of determinant det(-a, b, -c, d) = det(a, -b, c, -d) = -det(a, b, c, d)
•  » » » 12 days ago, # ^ |   0 Ahh it is used then when he does: x = -dx / d; y = -dy / d; right?
 » 11 days ago, # |   0 Why is Problem A tagged with FFT ? Is there a solution with FFT as well ?
•  » » 11 days ago, # ^ |   0 Nope, it means an idiot is going around and trolling.
 » 11 days ago, # |   0 very very good~ !!
 » 9 days ago, # |   -6 E has a tag "fft". Can it be done using FFT too? If yes, then how?
•  » » 5 days ago, # ^ |   0 Honestly, do you even know how to use FFT in the first place?
•  » » » 5 days ago, # ^ |   0 I do. I'm looking for more questions to practice it.
 » 7 days ago, # |   0 For problem 1036E — Covered Points , can anybody explain what's special with the test 14? I've seen some people failing this test.
 » 3 days ago, # |   0 Could someone explain how mobius function could be used in problem F. All I understood is that we are trying to remove the bad elements from the answer. Basically, could someone explain me the formula?