### chokudai's blog

By chokudai, history, 2 months ago, We will hold Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280).

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation! Comments (36)
 » Thank you for breaking no-contests-week!
 »
•  » » 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 and dp = 1 as base conditionsIterate from 2 to n and update dp[n] asdp[n] = p * (1 + dp[N-1]) + (1 - p) * (1 + dp[N-2])
•  » » » » 2 months ago, # ^ | ← Rev. 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: $\text{prob}(2) \cdot \text{prob}(1) \cdot (m2 + m1)$ ${m2 + m1}\choose{m2}$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
•  » » 2 months ago, # ^ | ← Rev. 2 →   If you know Markov Chains then the problem is quite easy.
 » 2 months ago, # | ← Rev. 3 →   How to do F ? I am clueless about how to answer queries in less than $\mathcal{O}(N)$, when there are zero-sum cycles only.
•  » » 2 months ago, # ^ | ← Rev. 2 →   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].
•  » » » 2 months ago, # ^ | ← Rev. 2 →   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. cnt = count of this prime number. ans = max(ans, maximum number under which we can get 'cnt' number of 'this prime').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?
 » 2 months ago, # | ← Rev. 3 →   Can Someone explain how I can approach Problem D in this Atcoder Round? I couldn't understand their approach in their editorial while(a>0){ n+=p; x=n; while(x%p==0)x /= p,a--; } ans=max(ans,n); `
•  » » 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.