### 9baka_Cirno's blog

By 9baka_Cirno, history, 3 months ago, ,  Tutorial of Codeforces Round #593 (Div. 2) Comments (61)
 » 3 months 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
 » 3 months 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.
•  » » » » 3 months 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
 » c < a < b < d. i think this was the difficulty.
 » Can someone explain the tutorial of problem E? thats not clear for me
•  » » 3 months 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.
•  » » » 3 months 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 :((
•  » » 3 months 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.
•  » » » When, n = 2 and m = 1, then why answer is 1 and why not {1, 2}, {1}, {2}, i mean answer 3?? Please help me to understanding with this problem...
•  » » » » maybe you should revisit the topic， if you understand it, your problem doesn't exist.n = 2, m = 1 that means only one box, and the subject require all persents should be put, so all presents will be put in the only box.then there is no doubt that the answer is 1
•  » » » » » Thank You.. I got it..
•  » » 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.
•  » » First, we can think about putting one present in m boxs, each box has two conditions（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 Cinro_9baka (previous revision, new revision, compare).
 » Can someone explain me solution B?, please my maths is not to much mature yet
•  » » 3 months 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 
•  » » » thank you very much friend
•  » » There are $m$ boxes for the presents:$\{\}\{\}\{\}\{\}\{\}...\{\}$We have $n$ presents, each of which can be placed in the $i$ -th box or not (two options for each box and each present $j$: it is either in the box or not):$\{j\} or \{\}$It will be $2^m$ possibilities for each present, something like these for $m=8$:$\{j\}\{\}\{\}\{j\}\{j\}\{\}\{j\}\{\}$ or $\{\}\{\}\{\}\{j\}\{\}\{j\}\{j\}\{j\}$except we should select at least one present of each type (see the rules in the problem statement). Therefore, the option of "selecting no present of type $j$" is removed and remain $2^m-1$ possibilities for each present.There are $n$ presents: the solution will be $(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?
•  » » 3 months 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.. 
•  » » » thanks.. for your effort. unfortunately,i have clicked on downvote. never mind,it's a mistake.
 » Can someone explain why such arrangement in C gives exactly floor(n^2 / 2) minimum? P. S. Proof is desirable.
 » 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?
•  » » 3 months ago, # ^ | ← Rev. 2 →   https://codeforces.com/blog/entry/70654?#comment-554933update: this answer is much more detailed: https://codeforces.com/blog/entry/70654?#comment-551757
 » with all due respect but this contest wasn't a programming contest there were lots of math actually!
 » I had the idea for the solution to D during the contest, but the implementation was just too disgusting. If anybody managed to write it (relatively) concisely could you share me your answer?
•  » » How's this? 62842405Hopefully it's clear enough, though I'm not sure how intuitive Kotlin code is if one isn't used to it
•  » » » That's pretty clean, even compared to like the top ranks here. Thank you!
 » Help me with this python code getting RTE on Test case #6: https://codeforces.com/contest/1236/submission/62858367I don't understand why?
 » for problem F, I think its should be the cycle instead of ring
 » Problem F is very cool :)
 » 3 months 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)); } 
•  » » » 3 months 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)
 » Problem B is tagged with hashing and matrices.Can anyone tell me how to solve this problem by using hashing and matrices?Thanks in advance
 » Can anyone give a proof of this: “The number of connected components equals to the number of nodes minus the number of edges and then add the number of rings in it.” I wonder is this statement can only apply in cactus graph and what the 'rings' means here?
 » 3 months ago, # | ← Rev. 2 →   In Problem C,Labswhy can't we make division of groups for n=3 as A->1 2 3 B->7 8 9 C->4 5 6It will give F(A,B)=0 F(B,A)=9 F(C,B)=0 F(B,C)=9 F(A,C)=0 F(C,A)=9.As we need to get minimum F(x,y) which is 0 in this division. Any help is highly appreciated, Thankyou .
•  » » 3 months ago, # ^ | ← Rev. 2 →   Because it is asked to maximize the smallest F. In you example the smallest F includes F(A,B) which is 0.The solution in the editorial can be visualized as follows, the way they are place in the mountain: A|B|C | |9 |8| 7| | 6| | |5| | |4 | |3 |2| 1| | So the groups are: A: 1 6 7 B: 2 5 8 C: 3 4 9 `
 » TLE on test case 3 of problem B. Can anyone figure out what's the issue in my code: Problem BI'm returning the same (2**m -1)*n ways
 » Problem E, another solution: "So only the O(k) positions are useful." can you get the variable "k" defined then use it?