When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Cirno_9baka's blog

By Cirno_9baka, history, 4 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +59
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 6   Vote: I like it +32 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    True — the only motivation to code this is rating

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it +7 Vote: I do not like it

Love math, so think that contest was cool... Except for the F task )

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How can we solve the problem D using the Greedy approach?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

        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

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Can someone explain the tutorial of problem E? thats not clear for me

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +44 Vote: I do not like it

    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   Vote: I like it +14 Vote: I do not like it

      Your solution has been hacked by me.

      It will become $$$O(n^2logn)$$$ in some situations.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +26 Vote: I do not like it

        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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why did the pretest for problem D not contain a case where you need to turn on the start field?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    why should it?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      normally you don't want thousand people to fail an implementation heavy task because they forgot one detail?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -31 Vote: I do not like it

        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.

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

In problem E, my method needs to judge the case of n = 1, but I didn't think of it.

»
4 years ago, # |
  Vote: I like it +38 Vote: I do not like 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)$$$ .

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain problem B please?i am stuck :((

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like 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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone pls explain C?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't understand problem E? who can do me a favor? Every guess influences what?

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Me too :'( , I've left contest after solving problem A

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Auto comment: topic has been updated by Cirno_9baka (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me solution B?, please my maths is not to much mature yet

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    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`
    
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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   Vote: I like it +1 Vote: I do not like it
    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 = [1]
    group2 = [2]
    group3 = [3] 
    
    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..
    
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why such arrangement in C gives exactly floor(n^2 / 2) minimum? P. S. Proof is desirable.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +13 Vote: I do not like it

D: wrong answer on test 219... E: add case n=1 -> AC so sad...

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

with all due respect but this contest wasn't a programming contest there were lots of math actually!

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How's this? 62842405

    Hopefully it's clear enough, though I'm not sure how intuitive Kotlin code is if one isn't used to it

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      That's pretty clean, even compared to like the top ranks here. Thank you!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Help me with this python code getting RTE on Test case #6: https://codeforces.com/contest/1236/submission/62858367

I don't understand why?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem F, I think its should be the cycle instead of ring

»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Problem F is very cool :)

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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))
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?