Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | Radewoosh | 3707 |

2 | Benq | 3691 |

3 | tourist | 3669 |

4 | ecnerwala | 3565 |

5 | Um_nik | 3533 |

6 | ksun48 | 3489 |

7 | maroonrk | 3457 |

7 | jiangly | 3457 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | awoo | 187 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 178 |

6 | Radewoosh | 177 |

7 | -is-this-fft- | 176 |

7 | maroonrk | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Round #593 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/14/2021 22:06:14 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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

How can we solve the

problem Dusing 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.

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

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.

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 :((

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)^nCan 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

Think reversibly. consider

`n = 1`

(only one kind of present)`More Mathematical approach`

`Hence`

`for General 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$$$

Thanks a lot.Really helpful explanation.Expending a lot of time finally understand after reading this.

whats's the actual logic behind C.I could not understand the editorial of C. why a spiral representation of matrix works here?

`if x increases, n-x decreases and vice versa`

`Why Spiral Pattern?`

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.

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?

https://codeforces.com/blog/entry/70654?#comment-554933

update: this answer is much more detailed: https://codeforces.com/blog/entry/70654?#comment-551757

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

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? 62842405

Hopefully 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/62858367

I don't understand why?

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

Problem F is very cool :)

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#:

Golang:

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: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?

In Problem C,Labs

why can't we make division of groups for n=3 as

A->1 2 3 B->7 8 9 C->4 5 6

It 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 .

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:

So the groups are:

thank you..

TLE on test case 3 of problem B. Can anyone figure out what's the issue in my code: Problem B

I'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?

For problem : 1236B - Alice and the List of Presents. Can anyone explain me why the code is giving different output when used

`#include <bits/stdc++.h>`

and`#include <iostream>`

. Here is code. Please let me know.When used

`#include <iostream>`

gives me correct ans. whereas when used`#include <bits/stdc++.h>`

gives me`0`

for the input`1000000000 1000000000`

(n, M).Why is it behaving strangely??