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

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.

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.

why should 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.

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

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

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`

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

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

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

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));
}

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)