Consider this problem — 766C - Махмуд и сообщение. It asks the number of ways to partition the given string such that each substring holds the given condition. I understood how to solve this.

At first, I interpreted the problem slightly differently. I thought you have to count the unique combination of the partition of the string. But I couldn't come up with the solution for this. How to not overcount/find unique combinations?

For example,

Assume that the following two partitions are valid,

String — "abbba"

1. a|bb|b|a

2. a|b|bb|a

They should be considered the same in this variation of the problem.

How to approach this?

Given a weighted undirected graph. There are N cities connected by M roads. For each road, you know the fuel needed to travel that road. A small subset of cities have gas station. The price per litre at each gas station is different. The task is to travel from city A to city B in a car with fuel capacity C minimizing the total cost.

Stuck at — Create a new graph including only the cities with gas stations along with source and destination cities. The edge weights in this graph can be found by multiple runs of Dijkstra's algorithm. Now, how to proceed with different fuel price at each node? Some DP?