chokudai's blog

Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280) Announcement
By chokudai, history, 17 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

Comments Comments (29)
| Write comment?
»
17 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. :(

→ Reply
»
17 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.

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

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

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

      I did not use binary search. Submission

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

      The maximum count of a single prime factor can be log2(1e12) ~ 40

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

      Code

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

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

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

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

→ Reply
  • »
    »
    17 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)

    → Reply
  • »
    »
    17 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

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

      how to avoid TLE?

      → Reply
      • »
        »
        »
        »
        17 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])

        → Reply
      • »
        »
        »
        »
        17 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

        → Reply
»
17 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.

→ Reply
  • »
    »
    17 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].

    → Reply
    • »
      »
      »
      17 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

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

      How to check if it spoils pairwise distances?

      → Reply
      • »
        »
        »
        »
        16 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$$$.

        → Reply
»
17 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?

→ Reply
»
17 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

→ Reply
»
17 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);

`

→ Reply
  • »
    »
    16 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$$$.

    → Reply
»
16 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.

→ Reply
  • »
    »
    16 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.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply