Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Grid's paths, River crossing pawn, and avoiding Knight's move, start to end count

Правка en9, от yawn_lento, 2026-07-22 05:33:52

My attemt using Monte Carlo, effective when the number is small, but will resulting in WA when dealing with larger numbers.The advantage lies in its simplicity in maths logic, while the disadvantage leadsto repetitive attemps in same paths;

You can view the full, well-formatted C++ source code of Monte Carlo method here on GitHub:

https://github.com/yawn-lento/yawn-s-codes/blob/main/P10002-Monte%20Carlo.cpp

As for DFS, using iteration and recursion does make a crucial difference: we no longer waste our time on same paths, instead memory mechanism is introduced(though still not very effective). However, we still have to try every single paths when the number grows exponentially, ending up in TLE.

You can view the full, well-formatted C++ source code of DFS method here on GitHub:

https://github.com/yawn-lento/yawn-s-codes/blob/main/P1002-DFS%E5%B0%9D%E8%AF%95.cpp

Finally we come to the DP method. Focusing only on results using iteration and recursion, the calculation complicity is dramatically reduced, with the only cost of not knowing the exactly how a specific path looks like.

You can view the full, well-formatted C++ source code of DP method here on GitHub:

https://github.com/yawn-lento/yawn-s-codes/blob/main/P1002-DP.cpp

Теги monte carlo, grid paths, start to end

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский yawn_lento 2026-07-22 05:33:52 33 Tiny change: 'introduced. However,' -> 'introduced(though still not very effective). However,'
en8 Английский yawn_lento 2026-07-22 05:23:58 970
en7 Английский yawn_lento 2026-07-21 05:10:51 12
en6 Английский yawn_lento 2026-07-21 05:09:09 82
en5 Английский yawn_lento 2026-07-21 05:05:33 1583
en4 Английский yawn_lento 2026-07-21 05:01:28 42
en3 Английский yawn_lento 2026-07-21 04:55:47 22
en2 Английский yawn_lento 2026-07-21 04:53:13 26
en1 Английский yawn_lento 2026-07-21 04:51:02 1725 Initial revision (published)