A — Star
The next multiple of $$$100$$$ after $$$X$$$ is $$$X + 100 - (X \mod{100})$$$, so our answer is $$$100 - (X \mod{100})$$$.
Time complexity: $$$O(1)$$$ My solution
B — uNrEaDaBlE sTrInG
Simply check if the condition given in the statement is fulfilled.
Time complexity: $$$O(|S|)$$$ My solution
C — Kaprekar Number
We can simulate the process directly. $$$g_1(x)$$$ can be calculated by sorting the digits in $$$x$$$ in ascending order, while $$$g_2(x)$$$ can be calculated by sorting the digits in $$$x$$$ in descending order.
Time complexity: $$$O(K \times log_{10}(N))$$$ My solution
D — Base n
I suggest using Python for this task. We can use binary search to find the largest integer $$$n \ge d+1$$$ such that $$$X_n \le M$$$. There exists an edge case for $$$X$$$ of length $$$1$$$, as there can only be $$$0$$$ or $$$1$$$ unique values of $$$X_n$$$ in base $$$10$$$.
Time complexity: $$$O(log_2(10^{18})*|X|)$$$ My solution
E — Train
We can solve this problem using a modified version of Dijkstra's algorithm. Since we can only take a train $$$i$$$ at multiples of $$$K_i$$$, before taking a train, we must also add the waiting time for the next train to the "weight" of an edge. The next occurrence of train $$$i$$$ given current time $$$t$$$ is $$$K_i \lfloor \frac{t+K_i-1}{K_i} \rfloor$$$.
Time complexity: $$$O(MlogN)$$$ My solution
F — Potion
We can solve this problem with dynamic programming. Let $$$dp_{i,j,k}$$$ be the maximum possible initial potion magic power, where $$$i$$$ is the planned final number of materials used, $$$j$$$ is the number of materials used so far, and $$$k$$$ is the potion power modulo $$$i$$$. Our transitions are $$$dp_{i,j,k} = dp_{i,j-1,k-a_y \mod{i})}$$$ for each index $$$y$$$ in the given array $$$a$$$. Our answer is the minimum of $$$X - dp_{i,i,X \mod{i}}$$$ for all $$$1 \le i \le n$$$.
Time complexity: $$$O(n^4)$$$ My solution
Right before posting this the first time, I ended up deleting it accidentally and had to rewrite it :)
A,B and C were easier this time..
Why the LATEX disappears 5 second after opening some solution?
Is it still being weird?
Why my code showing TLE at after_contest_2 and after_contest_3 test case
My submission link
That's because, when you are updating the distance in the priority queue, you should also delete the previous wrong distance which might be already present in the priority queue. In your code, multiple copies of the wrong distance are increasing as you are only deleting the top one. Hence queue size is increasing very fast. Ultimately results in TLE.
Not now, thanks sir:).
Sub to D Can someone help me with this code? My approach was to find b such that $$$a_nb^n=m$$$, and the required answer if possible will be lesser than b, so that i will decrement till i find the polynomial to be less than m.Random tc Can someone also explain this as well? My code when i stress tested it worked fine for $$$m<=10^{16}$$$
.
It's part of the standard Dijkstra implementation, it ensures you don't needlessly visit the same node multiple times.