### Cirno_9baka's blog

By Cirno_9baka, history, 4 years ago,  Tutorial of Codeforces Round 593 (Div. 2) Comments (49)
| Write comment?
 » 4 years ago, # | ← Rev. 6 →   Maths. :) too maths. I get the idea for D, but didn't code it and will not code it even now. Too much implementation. haha!.Looking at F solution. should this problem be in any contest. hmm.. I don't know. may be other people can tell :)The problems were good, just +1 shift was needed.
•  » » True — the only motivation to code this is rating
•  » » agree that was very sad that i already write the code but there were a tiny implementation error and i got -11 rating but not +100 or something like that
 » 4 years ago, # | ← Rev. 2 →   Love math, so think that contest was cool... Except for the F task )
 » How can we solve the problem D using the Greedy approach?
•  » » IMO the aproach in the tutorial is the greedy approach because you always want the doll to move straight then turn right instead of turning right randomly. This could cover the graph as much as possible.
•  » » The greedyness here is: Go in the current direction as far as possible/allowed. Don't stop and turn earlier.My submission. As you can see, I update pc or pr (position column/row) to the cell before the next obstacle. Also max/min/r/c are to enforce the spiral shape of the path, i.e. do not cross previously visited cells.
•  » » » Why the greedy approach is working here? There must be a case where answer comes out to be different if we do right turn earlier then waiting for the obstacle.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   Assume, that you turn right, although there is a cell in front of you. Then it is impossible in the future to visit that cell. That is because you would have to cross your path.=> If there is a solution, then you must walk straight as long as possible
 » Can someone explain the tutorial of problem E? thats not clear for me
•  » » 4 years ago, # ^ | ← Rev. 3 →   I don't fully understand the solution, but I can tell you my way.(Not much different from the solution)Mark each $a_i$ given in the title to $(i,a_i)$ in the two-dimensional coordinate system as black. Start from $(0, x)$, and to reach $(n + 1, y)$, you can move right, right up or right down one grid at a time, and cannot pass through the black point.For a starting point, we need to find the largest $y$ and the smallest $y$ that it can reach.Let me take the largest $y$ as an example.Because you need to go up and to the right as much as possible, you can get the position of the first black dot $(x0,y0)$ by Binary search the number on the slash (if not, you can go to the last column unimpeded). Then you can only go to $(x0-1,y0-1)$, and then continue Binary search (in fact, you can preprocess an array, but this is not a problem). Find the first ordinate that is not $y0$. Point $(x1, y1)$, move to $(x1, y0)$ and continue the process.But when $n = 1$, special judgment is required.For specific implementation, please refer to my code.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   Your solution has been hacked by me.It will become $O(n^2logn)$ in some situations.
•  » » » » I'm so sorry that my program is wrong.That's because I've done similar problems before, so I subconsciously think that the time complexity is right.I have modified my program. I store the final location of each point in the process with a map. If I encounter it again, I will jump to the end. This time complexity can be proved to be correct, because the number of points I encountered in the process is at most $m$.My program can be optimized to $O(n+m)$, but I don't think it makes much sense.At last, thank you for helping me find out the mistake.
 » why did the pretest for problem D not contain a case where you need to turn on the start field?
•  » » why should it?
•  » » » normally you don't want thousand people to fail an implementation heavy task because they forgot one detail?
•  » » » » It's called edge cases. This task's difficulty was to correctly analyze the problem and implement it. I think that a pretest like that could help inadvertent a little bit too much.
 » In problem E, my method needs to judge the case of n = 1, but I didn't think of it.
 » The variance is equal to $E(X^2)-2E(X)^2+E(x)^2=E(X^2)-E(X)^2$ ,not $E(X^2)-E(X)$ .
 » can anyone explain problem B please?i am stuck :((
•  » » 4 years ago, # ^ | ← Rev. 4 →   Think of it this way, from the box kind's perspective. For each box kind, there are m boxes to go to. It can choose to go to 1 box (minimum) OR it can choose to go to 2 boxes OR 3 boxes..... OR all the boxes. i.e. mC1 + mC2 + mC3 + ..... + mCm. (We add because since it's a single choice it can make i.e. it can choose to be in a single box OR it can choose to be in 2 boxes but not BOTH the choices). By Binomial Theorem, mC1 + mC2 + mC3 + ..... + mCm equals 2^m -1 .To calculate this for all the n box kinds, you got to multiple this n times. We multiply now because each box kind makes a choice independent of what the other box kind makes. i.e. (2^m-1) ^ n. Don't forget the modulo part. Peace.
•  » » First, we can think about putting one present in m boxs, each box has two condition（put or not） ,so the res is 2^m, and we should subtract 1(all boxs are empty).(the answer one present in m boxs is 2^m-1)Then we have n presents, so the amnswer is (2^m-1)^n,my english isn't good, hope it's useful for you.
•  » » consider send the gifts to men. if there are 3 people. you can send this gift to: person A  person B person C  person A,B person A,C  person B,c  person a,b,c each gifts have 2^m-1 ways to send.because you can't send this gift 0 times; as there are n gifts in total,so the answer will be (2^m-1)^n
 » Can someone pls explain C?
 » I can't understand problem E? who can do me a favor? Every guess influences what?
 » Math was my greatest weakness. I was afraid of Math. I wrote a shit ton of code in attempt to evaluate the answer without coming up with the formula. Finding workaround Math was always my approach.But it seems that it didn't work for this round. Nor it will work often in general.I shall not detest it any longer, and start embracing it from today. For my hatred only hinders my advance in CP.
•  » » Me too :'( , I've left contest after solving problem A
 » Auto comment: topic has been updated by Cirno_9baka (previous revision, new revision, compare).
 » Can someone explain me solution B?, please my maths is not to much mature yet
•  » » 4 years ago, # ^ | ← Rev. 3 →   Think reversibly. consider n = 1 (only one kind of present) How many ways of distributing this kind among m boxes with given constraints?  let m = 3  then ways of distributing is -  001 -> gift is only packed for first box  010 -> gift is only packed for second box  100 -> gift is only packed for third  011 -> gift is packed for first and second box  101 -> gift is packed for first and third box  110 -> gift is packed for second and third box  111 -> gift is packed for first, second and third box  these are total 7 possible ways of distribution for one kind we have ignored the case -> 000 as it violates condition  for m boxes, number of ways of distributing one kind of gift is -> pow(2, m) - 1 More Mathematical approach Consider n = 1, m = 3  total ways such that only one of the boxes contains the gift = total ways of selecting one box out of m boxes = mC1  total ways such that exactly two of the boxes contains the gift = mC2  total ways such that exactly tree of the boxes contains the gift = mC3  .  .  .  total ways such that exactly m of the boxes contains the gift = mCm Hence total ways = mC1 + mC2 + mC3 + . . . + mCm = pow(2, m) - 1 for General n Ways of distribution of Every kind of gift is independent to each other. Each kind has same number of ways of distribution among m boxes (i. e. pow(2, m)-1)  Hence Total ways = (2**m - 1)**n 
 » whats's the actual logic behind C.I could not understand the editorial of C. why a spiral representation of matrix works here?
•  » » 4 years ago, # ^ | ← Rev. 3 →   If you observe the pattern, you will see that for any given n The answer is floor(n/2)... Why?  let n = 2 There will be two groups (group A, group B). let Units of water that can be transported from group A to group B= x then Units of water transported from group B to group A will be n-x output = min(x, n-x) if x increases, n-x decreases and vice versa our goal is to maximize the output, to x and n-x should be very close to each other, so if x is floor(n/2), n-x will be ceil(n/2) Why Spiral Pattern? We have to place all n*n elements in n groups such that result is maximum of the minimum number of the sum of units of water that can be transported from one group to the another..  for n = 3 there are (1, 2, 3, 4, 5, 6, 7, 8, 9) elements we have to distribute in 3 groups. group1, group2, group3 we start in ascending order of numbers. on first iteration => units of water transported (from group2 to group1) > units of water transported (from group2 to group1) units of water transported (from group3 to group2) > units of water transported (from group2 to group3) group1 =  group2 =  group3 =   so in next iteration we have to make them equal (nullify the iteration 1 effect).. in iteration2 => start placing elements(numbers) from the last group (group3) to first group(group1).. group3 = [3, 4] group2 = [2, 5] group3 = [1, 6] each group has one number greater than one number of any other group and one smaller number than one number of any other group So min(units of water tranported between any group) is 1 (maximum till now)  continue the all the iterations, spiral pattern is what we get.. 
 » Can someone explain why such arrangement in C gives exactly floor(n^2 / 2) minimum? P. S. Proof is desirable.
•  » » Yeah so let's consider the f(1,2) where 1 means 1st row & 2 means 2nd row , now count it you can see the following pattern 0+2+2+4+4+6+6+... solve this you will get the desired result
 » I did problem C by filling NxN matrix with 1 to N^2 in a column-wise zig-zag manner and it passed. Can anyone please explain why this works?
 » 4 years ago, # | ← Rev. 2 →   Hi guys, Can you help me please on task B.Based on solution formula i wrote code in C# & Golang, but on test 3 i got errors: memory limit for C#, time limit on Golang. Can it be language limitation or its just code not optimized? C#: BigInteger t = BigInteger.Pow(2, m); t -= 1; t = BigInteger.ModPow(t, n, 1000000007);  Golang: var tmp big.Int var t = tmp.Exp(big.NewInt(2), big.NewInt(m), nil); t = tmp.Sub(t, big.NewInt(1)) t = t.Exp(t, big.NewInt(n), big.NewInt(1000000007)) 
•  » » Hi, I think you need a fast pow algorithm. The basic pow operation's complexity is $O(n)$, and will get TLE since $1 \leq n, m \leq 10^9$. Besides, the big int operation is much slower and use more memory than the int64 operation.To avoid using big type, you can mod $10^9+7$ in every operation, so it won't get overflow. And instead of the basic pow, use fast pow (its complexity is $O(log\ n)$).Here's how to write fast pow algorithm in Go: package main import ."fmt" const mod = 1000000007; func fastpow(base, exp, mod int64) int64 { var t, y int64; t = 1; y = base; for ; exp != 0; exp >>= 1 { if exp & 1 == 1 { t = t * y % mod; } y = y * y % mod; } return t % mod; } func main() { var n, m int64; Scan(&n, &m); Print(fastpow(fastpow(2, m, mod) - 1, n, mod)); } 
•  » » » 4 years ago, # ^ | ← Rev. 12 →   I don't think this is the problem because he's using big-integer library functions (which I assume uses fast exponentiation); the problem is that he's not finding $2^m$ using the modulo, so the size of the big-integer blows up. (the end result could have $10^9 + 1$ bits!)It is generally advisable though, as one gains CP experience, to roll their own small library/template for working with modulo operations using plain 32- or 64-bit integers, as that's significantly more performant than big-ints. (In Kotlin, I use the inline class feature to wrap integers in a ModInt` class) The big-int overhead shouldn't be a problem for this puzzle though, since you're only implementing a simple formula.
•  » » Finding $2^m$ should be done with the modulo too to prevent explosion of memory and time (memory on the order of $O(m)$, and time even worse)