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!
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.
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
NisE(N). Now, you may do 1 damage withpprobability or 2 damage with1-pprobability.Both of these steps require 1 move over
E(N-1)andE(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] = 0anddp[1] = 1as 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
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.
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
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!