China use different calendar , interesting.

Are you really ke jie playing go? Wow

In india we got another New Year on the day of festival 'HOLI'.

Jie baby,my jie baby

Happy New Year :)))) Vietnam 3 — 1 China

*lunar

It will be held on extended ICPC rules. It's like div.3, contestants will be sorted by the number of solved problems,then penalties

well.... :')

guess what happened.... I got one

10 min penalty for every incorrect submission until it gets accepted

penalty-based

As far as I know, out of all problems you solve finally, each minute you put a problem unsolved is counted as penalty.

Suppose you solved 2 problems("A" and "B") in a contest:
Let's assume "A" takes 10 min and "B" takes 20 min to solve.
- Case 1 : You started with "A" and solved "A" after 10 minutes of the contest and "B" after 30 minutes of the contest. Penalty for these two is (10 + 30) = 40 minutes.
- Case 2 : You started with "B" and solved "B" after 20 minutes of the contest and "B" after 30 minutes of the contest. Penalty for these two is (20 + 30) = 50 minutes.

So it is good to start with problems that take less time to solve.

good luck to ya :DD

Happy Chinese New year!

It felt interesting to me, that in rated rounds I try to not even waste a single second, while you also take the time to announce your submit status xD.

calculate the number of operations required to convert ai to bi and then knapsack.

Observe that if k is greater than sum of all operations we can skip knapdsack dp. And sum won't be too big.

the maximum number of operation to obtain any number from 1 to 1000 using that operation is 12. So k can be at most 12*n. So if k > 12*n just make k = 12*n

Your DP state is incorrect. Use 01 Knapsack DP : Link

O(m^2) distinct MSTs.

NHK bro?

k doesn't need to be 1e6

No this fails for b[i] = 7

Is it possible to get the cost to transform a number to b[i] using greedy?

something like,

k=1
while(a<b and k<=a):
   while(a+a/k > b) k+=1
   steps+=1
   a+=a/k
if(a==b)
   return steps

Share my solution here :

Notice that the sum of k<2*10^5.

That means the solution should be O(n).

To Check who wins- find number steps needed by both to win (that means if the character kept attacking how many rounds are needed to defeat the monster and vise-versa)

character_steps = ceil(monster_health/character_damage)

monster_steps = ceil(character_health/monster_damage)

if character_steps<=monster_steps then character wins (First chance is of character so <=) Checking who wins is o(1)

To find all possible combinations in the way we can use the coins- we can go from 1 to coins (i) and use i as the coins used for damage boost and use coins-i as the coins for health boost and add the boost to the damage and armor. We can do this in O(n)

It's not actually $$$O(n\cdot k)$$$ where $$$k\approx 10^6$$$.

Since the number of operations needed for any $$$b_i$$$ to get constructed is at max $$$12$$$, if $$$k\ge 12\cdot n$$$, you can simply print $$$\sum_{i=1}^n c_i$$$. Otherwise you can use a knapsack dp solution so solve the problem in $$$O(n\cdot k)$$$ time where $$$k\lt 12\cdot n$$$.

There might be some solutions which either shouldn't pass according to the given constraint or are actually wrong but the systems tests don't cover the cases where they fail.

Codeforces gives the users, an opportunity to identify such solutions and hack them (submit a valid test where they fail). Obviously it does not guarantee $$$100\%$$$ strength to the new test set formed after hacking.

I precompute them using BFS. Find the shortest path from 1 to all nodes

You can write a brute force dp for this. Just make sure you have an idea about dp solutions.
Consider $$$dp_i$$$ stands for the minimum number of operations required for making the number $$$i$$$ starting from $$$1$$$.

Then, it can be seen that before forming the number $$$i$$$, we might have had a number $$$j$$$ such that the value of $$$\lfloor \frac{j}{x} \rfloor$$$ was equal to $$$i-j$$$ for some $$$x$$$ (because that's the only way $$$j+\lfloor \frac{j}{x} \rfloor$$$ will become equal to $$$i$$$). Let's iterate on $$$j$$$ too. We will then need to find the value of $$$x$$$ (if it actually exists).

Well it says ai / x floored (note the floor function brackets) which indicates that x doesn't necessarily divide ai.

Same Here, but i figured it out after 1 hour and 3 wrong attempts :(

Same thing bro

I think you answered your own question. You can't solve 0-1 knapsack with greedy.

Never be greedy :p

c — 10, 4 operations — 2, 1 k = 1

according to you 10/2 is better than 4/1 but we cannot take 10/2 as limit is k=1.

Klog(m^2) passed for me with maps in 2000ms. Hack it, maybe? :p

No need of fancy math. run n*n bfs as {1,1}

{i, steps} -> {i + (i/j), steps + 1} for all 1<=j<=i

states = 10^3, TC: 10^6 bfs

How do you know this regularity?

Have u tried? I did the exact same thing first but got 2 WA. Then I switched to BFS.

I did this in contest and got wrong answer, brute force implementation after contest gave AC, are you sure this is correct? (maybe I implemented it wrong)

This isn't correct:

Try for 19: 10011
Index of msb: 4
setBits: 3
Your ans: 4+3-1=6
Actual answer: 5
How to reach: 1->2->4->8->16->19 [19 = 16 + 16/5] in total 5 steps

I did this mistake too.

15 = 1111 Here ans ≠ (3) + 4 — 1 = 6

But optimal soln is 5 (1->2->4->8->12->15)

I didn't know 2 can be done with binary search.

$$$k = min(k, 12n)$$$

It's because you are using float and float is not accurate, i had the same problem from few days my solution got accepted in c++ 17 but not in c++ 20 and someone told me why this happened you can check the reason float fail sometimes to give AC here
PS: changing float to double in your code give AC, so when u want a floating number next time use double!

I submitted with vector of vectors and it ran in TL. 144786518