chokudai's blog

By chokudai, history, 2 months ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +41
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for breaking no-contests-week!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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) respectively

    So, E(N) = p * (1 + E(N-1)) + (1 - p) * (1 + E(N-2))

    Code

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      how to avoid TLE?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Use dynamic programming, store the expected value of nth move in dp[n]

        Also dp[0] = 0 and dp[1] = 1 as base conditions

        Iterate from 2 to n and update dp[n] as

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

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it +4 Vote: I do not like it

        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   Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it +13 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      Ahh thanks, now I got it.

      Edit: got AC now

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to check if it spoils pairwise distances?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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$$$.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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);

`

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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$$$.

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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