Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

chokudai's blog

By chokudai, history, 5 weeks ago, In English,

We will hold AtCoder Beginner Contest 152.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

»
5 weeks ago, # |
  Vote: I like it +49 Vote: I do not like it

Note — Contest starts 10 mins before the usual time.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Hope that there is no question which is available on any other platform. PS:- F of last contest :(

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do F?

»
4 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Commentary:

  • A: Implementation.
  • B: Implementation. The easiest approach is actually building both strings and using your language's built-in lexicographic comparison.
  • C: If we read the elements of $$$P$$$ left-to-right and maintain the "minimum so far," the answer is equal to the number of times that minimum is updated.
  • D: $$$N \leq 2\cdot10^5$$$, so we can iterate over all numbers in $$$[1, N]$$$ and build a map $$$(f, d) \rightarrow \textrm{number of integers starting with } f \textrm{ and ending with }d$$$. The map has at most $$$100$$$ elements. We can iterate over all possibilities for the pair $$$(A, B)$$$ in quadratic fashion.
  • E: Let $$$L = A_1B_1 = A_2B_2 = \dots = A_NB_N$$$. Each $$$A_i$$$ must divide $$$L$$$. $$$\sum_i B_i$$$ is minimized when $$$L = \textrm{LCM}(A)$$$. We need to compute $$$\textrm{LCM}(A)$$$ modulo $$$10^9 + 7$$$. If prime $$$p$$$ has multiplicity $$$m_i$$$ in entry $$$A_i$$$, it has multiplicity $$$\max_i m_i$$$ in $$$\textrm{LCM}(A)$$$. We can factor each element of $$$A$$$ using a pre-computed sieve and maintain an array with the maximum multiplicity for each prime. Finally, we compute and print $$$\sum_i \frac{L}{A_i}$$$.
  • F: The main idea is inclusion-exclusion. Let $$$R$$$ be the set of all restrictions and for any $$$r \subseteq R$$$ let $$$f(r)$$$ be the number of edge-colorings which violate all of the restrictions in $$$r$$$. Violating a restriction $$$(u_i, v_i)$$$ means that each edge on the path from $$$u_i$$$ to $$$v_i$$$ is colored white. Hence if $$$g(r) = $$$ the number of edges in the union of all paths in $$$r$$$, $$$f(r) = 2^{N - 1 - g(r)}$$$. $$$g$$$ can be computed efficiently if we prepare bitmasks for each $$$(u_i, v_i)$$$ indicating which edges occur on the path from $$$u_i$$$ to $$$v_i$$$ (note $$$N \leq 50$$$, so we can use 64-bit integers for this purpose). Our final answer, the number of colorings which violate no restrictions, is $$$\sum_{r} -1^{|r|} f(r)$$$.
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice approach in E by prime factorising

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In F why does dp with bitmask fail? For each edge, I had a mask that represented that if, I painted this edge black then which constraints will be satisfied due to it.

    Now just a dp(edgeNumber, mask).

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    For E LCM can be calculated with idea product of two numbers=gcd * lcm. for large number we can take modulus

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't think it works: $$$gcd(a, b)$$$ is not necessarily congruent modulo $$$M$$$ to

      $$$gcd(a\bmod{M}, b \bmod{M})$$$

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

      CF community is weird.idk why i am getting so many downvotes :(

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can anyone share the implementation of E.I am not able to implement E.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why it is -1^r in problem can you plz clear it saketh

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's a general technique known as Principle of Inclusion-Exclusion: [1] [2].

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        we add things when r is odd and subtract when r is even so so if A==sum(when r is odd) B == sum(when r is even)

        So shouldn't the answer be total-violation in restriction i.e. {2^(N-1)-(A-B)}.

        what is wrong with this please tell.

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

why am i getting WA in some cases in E? lcm(a1,a2,a3...an)*(1/a1+1/a2+1/a3+....+1/an) was the ans right?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thats beacuse of overflow while calculating lcm(a1,a2,...,an).

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why does this python code -> Link fails?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Try running your code in Custom Tests section. It gave GCD undefined error when i copied your code and tried.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to deal with large numbers in E ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the idea is to factorize the numbers, you can come up with a formula for finding LCM(a_1, a_2, ..., a_n) from their prime representations.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Python can solve this trivially. Code

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'll use python next time when big number arithmetic pops up. Thanks mate

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

Explain D please

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Define f(a,b) as number of integers less than or equal to n such that the first digit is a and the last digit is b. Observe that the solution is f(a,b)*f(b,a) over all possibilities. there are 81 possibilities (as leading 0's are not allowed) like so)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain C, please?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why no code in D, E, and F?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Unfortunately usually there are no sample code attached for the latter problems. You can see any submissions here anyway. (You can use filter in order to show only AC codes for a specific problems, and even filter by the programming languages.)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can we see others solution after contest in atcoder?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yes,After the contest go to Results tab then All Submissions.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I did not get how to solve D, can someone explain?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First, fix an integer $$$A$$$ where

    $$$1 \leq A \leq N$$$

    . Assume that the first digit of $$$A$$$ is $$$i$$$ and the last digit is $$$j$$$. How many

    $$$B$$$s are there that satisfies the given condition? The necessary and sufficient condition is that the first digit of $$$B$$$

    is $$$j$$$ and the last digit is $$$i$$$. So, in order to count them, you can iterate the integers from $$$1$$$ to $$$N$$$, and check whether each of them satisfies the conditions written above or not.

    Then what to do next? Since $$$N$$$ can be up to

    $$$2 \times 10^5$$$

    , the total loops can be up to

    $$$4 \times 10^10$$$

    , so it won't finish in time. This means that you are wasting time for something, typically doing the same calculation over and over again. Now focus on this step mentioned above:

    you can iterate the integers from $$$1$$$ to $$$N$$$, and check whether each of them satisfies the conditions written above (= whether its first digit is $$$j$$$ and the last digit is $$$i$$$) or not

    Instead of performing the step for every $$$A$$$, you can count "the number of integers such that the first digit is $$$j$$$ and the last digit is $$$i$$$" (Let this number be

    $$$c_{ji}$$$

    by looping through from $$$1$$$ to $$$N$$$ only once. So, you could solve this problem.
»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For F is O(n*m*2^m) under TL?

https://atcoder.jp/contests/abc152/submissions/9614620

or i am not considering complexity correctly?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

for F did anyone understand the tutorial's solution?

Also if i have a tree with nodes <= 10^5 and some M paths how can i know the total number of edges covered?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    O_E what u didn't get in editorial?i don't think it can be solved for large constraints

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      i didn't understand how it uses LCA and cumulative sums

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

        I'll try my best to explain it.

        suppose you want to all edges b/w u-->v

        so path will be like u---->lca(u,v)----->v.

        in this way determine number of all paths which are white.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        You can use LCA since any path from u to v can be decomposed into a path from u to lca(u,v) and another path from v to lca(u,v) which makes our lives easier when we use prefix sums.

        Using prefix sums is similar to updating a range in array [l,r] when you arr[l]++ and arr[r+1]-- in this way the prefix sum of every index equals to the number of update ranges that has start<= index and end >=index, similarly when it comes to trees, if you want to say that the path from u to v (where u is an ancestor of v) is used, you can do arr[u]-- , arr[v]++, and then for each node let arr[node] = summation of all values of its subtree, if arr[node] is positive, this means the edge parent[node] to the node is used because this can happen if there is at least one path that start in one of the subtree's nodes and end in an ancestor of that node.

        You can check my submission if it's not clear.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          It's a nice solution thank you ya zeyad