you will~

-247-253=998244353-998244853

sorry

maybe new style :)

Errichto's video

It is the sum of possible outcomes each multiplicated by the propability of that outcome.

I'm wondering for it too...

Or your solution's time complexity is too high XD

F

E looks like BFS problem

how to solve f any hints ?

I'd like to second that. E and F are way too standard problems if you have appreciable experience.

You also need to mark which alphabets you have visited else complexity will be O(n ^ 4). Consider a matrix consisting of all a.

Don't apply BFS again on visited characters. For example you have encountered 'a' once, then don't again visit cells containing 'a'.

You need to optimize your code, not IO.

AC Code in Java

We can create a dp[a][b][c]==prob that that state happens. Then add up the propabilities.

how to solve C?

We can create the table of size 2^20 for first 20 items. Then do the same for the other 20 items, and combine each entry of the first table with the optimal one from the other in O(logn). ie binary search for the value.

The constraint on N is small, i.e, 40. So if we divide it in 20 and 20 and then compute subset sums for the right half and left half using recursion, it will have a time complexity of 2^20, which is doable.

C: Observe that all fields are reachable with 3 moves. This is, because all fields (chess coloring) with same color are reachable with two moves.

So, check if dist==0. Then check if dist==1 by implementing the rules as given in statement.

Then check if dist==2, that is same field color or manhattan dist<=6. Or if destination point+3 fields is on one of the diagonals.

Else dist==3

Dynamic Programming
My submission should be self-explanatory
Submission

I thought about the reverse process, let's build state a, b, c from all possible final states. That way I can add 1 directly while computing expectation from successive states, probabilities of transition remain the same, but the expected value of answer is now expected value of states a, b, c. Transitions are namely (a+1,b,c), (a, b+1,c) and (a, b, c+1) multiplied with respected probabilities ,of course if its a valid state. Submission Link

Here is my submission if anyone can take a look: https://atcoder.jp/contests/abc184/submissions/18338763

Got AC on my DP Solution -> ? Want me to share my code?

https://sapphireengine.com/@/2ptnop :) My DP solution

I had some difficulties to understand this, too.

Then I had to use long double instead of double to get rid of rounding errors. Is that intentional, or is my implementation stupid?

https://atcoder.jp/contests/abc184/submissions/18330299

I think you ain't working hard anymore :(

No, the idea of keeping a visited array is a must to avoid tle, because lets say you are traversing the point with 'a' then if this is the first 'a' you have encountered then all other 'a' will be marked with their best distance (thats how bfs works) and hence when you next encounter a 'a', you dont need to again update the weights of other 'a' because they are already marked to their best.

imagine a grid with full of 'a', this code would have the complexity of n^2 * m ^ 2 then

My first submission also got time limit exceeded so I applied this logic , look once visiting a particular character 'a' in minimum number of moves say 'd' then mark all the unvisited positions that has character 'a' as minimum distance = d+1. Now notice that this character 'a'(assumed here) is no longer use so u can erase it from your adjacency list. Mine such approach passed all test cases. Hope it helps and provide u the sufficient idea. My Solution Link

https://sapphireengine.com/@/2ptnop You can refer this to understand

Let $$$p[i][j][k]$$$ be the probability that we currently have $$$i$$$ gold coins, $$$j$$$ silver coins, and $$$k$$$ bronze coins. Initially, $$$p[a][b][c] = 1$$$ and otherwise $$$p[i][j][k] = 0$$$. We update

For every such $p[i][j][k]$ where exactly one of $$$i, j, k$$$ is equal to 100, we simply update our answer by

where $$$(i+j+k)-(a+b+c)$$$ represents the number of turns needed to reach state $$$(i, j, k)$$$.

Try to think about meet in middle, calculate all possible sum of weights of 2 equal parts of the input array and think of obtaining answer as combination of each value from first set with best value from the other. Ofcourse best answer might just come from one part only, so take care of that separately. Time Complexity will be O(2^(N/2)) with 2 pointers or with a factor of N if you're lazy enough :p

// tele[c].clear();

The above line is correct, uncomment it, and place it after the loop. Each portal letter need to be traversed only once.

Otherwise consider N=2000 grid and all cells marked with 'a', it will result in O(n^4) runtime.

My first submission also got time limit exceeded so I applied this logic , look once visiting a particular character 'a' in minimum number of moves say 'd' then mark all the unvisited positions that has character 'a' as minimum distance = d+1. Now notice that this character 'a'(assumed here) is no longer use so u can erase it from your adjacency list. Mine such approach passed all test cases. Hope it helps and provide u the sufficient idea.My Solution Link

Here

E- I used dijkstra F — Meet in Middle

the_Miracle if (i != tmp) { dist[i.first][i.second] = dist[tmp.first][tmp.second] + 1; vis[i.first][i.second] = 1; Q.push(i); }

The above lines are creating errors. Use !vis[tmp.first][tmp.second] to update.

I changed some part of your code , added some visited arrays.

The ac code

In the sample input, there is one that require 3 moves

2 3
998244353 998244853

If you want a simpler example

0 0
0 7

you can use text-compare to compare them, only 1 space difference between these 2 submissions.