We will hold Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280).

- Contest URL: https://atcoder.jp/contests/abc280
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20221203T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: kyopro_friends, math957963, physics0523, Eugle_na, Nyaan
- Tester: cn449, MMNMM
- Rated range: ~ 1999

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

Thank you for breaking no-contests-week!

whats wrong in my D solution

We can first calculate all the prime factors of N. We then reduce the problem to finding a factorial which has all the prime factors of N, at least as many times as they appear in N. Then binary search on elements from 1 to N. then find the smallest such number.

I couldn't finish coding solution for F, it was a simple idea but I messed up implementation. :(

"simple"

D can be solved with binary search and $$$O(\sqrt{N})$$$ check function. It is easier to implement.

Is there any other way to do it ? I am asking because I have also used binary search.

I did not use binary search. Submission

The maximum count of a single prime factor can be

`log2(1e12)`

~ 40Now you can just brute for all the prime factors as you would have to check at most 40 multiples of that prime factor.

Code

we can brutefore till N <= 40 * root k. if prime > root k didn't come in that then ans is that prime.

https://atcoder.jp/contests/abc280/submissions/36980501 Could you please check what is wrong in this?

I hate these expected value questions. How to solve E?

E(n) = 1 + (p/100)*E(n-2) + (1 — (p/100))*E(n-1)

What will be E(2) and E(1) then?

Base cases : E(0) = 0, E(1) = 1

Say, Expected number of moves for

`N`

is`E(N)`

. Now, you may do 1 damage with`p`

probability or 2 damage with`1-p`

probability.Both of these steps require 1 move over

`E(N-1)`

and`E(n-2)`

respectivelySo,

`E(N) = p * (1 + E(N-1)) + (1 - p) * (1 + E(N-2))`

Code

how to avoid TLE?

Use dynamic programming, store the expected value of nth move in

`dp[n]`

Also

`dp[0] = 0`

and`dp[1] = 1`

as base conditionsIterate from 2 to n and update dp[n] as

`dp[n] = p * (1 + dp[N-1]) + (1 - p) * (1 + dp[N-2])`

I used an iterative approach like this:

Basically, there can be 2 final states, 0 or -1 after the moves, and the moves can be like (222...111...), so we can just fix number of 2-moves (say m2), and calculate the 1-moves (say m1), then the expected value for 0-state would be:

We can then iterate over counts of 2, and add this up. Similarly, for -1 state, we can calculate it like N-1 to 0, and then append a 2-move.

Submission would make it clearer: https://atcoder.jp/contests/abc280/submissions/36977527

If you know Markov Chains then the problem is quite easy.

How to do F ? I am clueless about how to answer queries in less than $$$\mathcal{O}(N)$$$, when there are

zero-sum cyclesonly.You change the whole graph into trees by doing DFS. Hint is, if you face a back edge, either it is completely useless or it spoils all pairwise distance to INF in that component. Now, you have to maintain a score for each node in that component from some root. Then it will be score[y]-score[x].

Ahh thanks, now I got it.

Edit: got AC now

How to check if it spoils pairwise distances?

For a component $$$C$$$, if there is a non-zero-sum cycle $$$cyc$$$ in it, we know there will be a positive-sum cycle, i.e., either $$$cyc$$$ or its reverse. So, for any two nodes $$$x$$$ and $$$y$$$ in $$$C$$$, $$$x$$$ can go to $$$cyc$$$ and increase its score infinitely then go to $$$y$$$.

Proof that ignoring back-edges that cause a cycle sum to be $$$0$$$ is equivalent to checking that there are no non-zero-sum cycles:

Consider one of such edges $$$e$$$ with score $$$w$$$ connecting nodes $$$x$$$ and $$$y$$$, we know that $$$y$$$ goes to $$$x$$$ through a sequence of edges $$$S$$$ with total score of $$$-w$$$ then goes from $$$x$$$ to $$$y$$$ through $$$e$$$. This means we can go from $$$x$$$ to $$$y$$$ through reverse of $$$S$$$ with a total score of $$$w$$$. Which means we can remove $$$e$$$ as it can be replaced by reverse of $$$S$$$.

So, after removing all back-edges, we are sure all path scores in the original graph have equivalents in the reduced graph, i.e., only $$$w$$$ from $$$x$$$ to $$$y$$$ and only $$$-w$$$ from $$$y$$$ to $$$x$$$.

What's wrong with my approach in problem D.

for every prime number in K.

can anyone help?

Similar logic as my submission

Thanks! i was doing i*=a but it should be i+=a; this mistake costed me this contest.

My approach on E gives TLE. Any slight modifications to change this to avoid TLE? Submission

For problem d: I found prime factorisation of k,now I used binary Search to find the value of smallest such n We can check whether or not n! Is possible by simply finding powers of primes that are in k in n For this I used a basic formula of n/p+n/p^2 and so on Is something wrong in this?

Can Someone explain how I can approach Problem D in this Atcoder Round? I couldn't understand their approach in their editorial

`

Before this while loop in the master solution, you find the maximum a satisfying $$$p^a \vert K$$$. Then, in the last while loop you are bruteforcing to find the minimum $$$N!$$$ such that $$$N!$$$ is a multiple of $$$p^a$$$.

sorry for being late! But can anyone tell me how to check whether all loops have sum zero or not in F-Pay or recieve. Nothing clear is mentioned about this in the editorial too.

Let $$$dist[n_x]$$$ be the distance from node $$$n_1$$$ to $$$n_x$$$ during normal traversal. Consider cycles known from back-edges, i.e., edges going to visited nodes, e.g., if our traversal looks like $$$n_1\rightarrow ...\rightarrow n_2\rightarrow ...\rightarrow n_3\rightarrow n_2$$$, if the weight of edge $$$n_3\rightarrow n_2$$$ is $$$w$$$, then $$$dist[n_3]+w-dist[n_2]$$$ must be $$$0$$$, this is the basically the cycle length. If this is true for all the found back-edges, then there are no non-zero-sum cycles. A proof can be found here.

Wonderful round! I solved E in 10min for the first time!

Hey i am very bad at probability can you tell me what are the topics in probability which will help me in competitive programming.