atcoder_official's blog

Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383） Announcement
By atcoder_official, history, 6 days ago, In English

We will hold Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）.

We are looking forward to your participation!

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

»
6 days ago, # |
  Vote: I like it +26 Vote: I do not like it

Hope the problem G is easier than last two ABC.

→ Reply
  • »
    »
    5 days ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    There aren't any rated participant passed G.

    → Reply
»
6 days ago, # |
  Vote: I like it -6 Vote: I do not like it

Is Daiwa Securities Co. Ltd. hiring via this contest for any role?

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope all the coders can get a high perf. GL && HF!

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish every could have a fantastic experience at this anticipating contest!

→ Reply
»
5 days ago, # |
  Vote: I like it -10 Vote: I do not like it

I AC D !!!!!!!!!!!!!

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

what even D?

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

    Basic number theory problem

    → Reply
  • »
    »
    5 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    D is easy if you know the divisor formula.

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

      what is that? can you given a high level editorial?

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

        The number of divisor of any positive integer n is (p1+1) * (p2+1) *(pk+1). where pi is one of the distinct prime factor of n. since 9 can only be written as a product of 3 * 3. and 3 * 1. The number of prime factors of such an integer who has 9 divisors and either 2 or 1. get all the primes until 10^7 and brute force it.

        → Reply
»
5 days ago, # |
  Vote: I like it +6 Vote: I do not like it

E harder than F

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

    u did f?

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

      yes

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

        can you explain your approach

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

          Sort on the basis of colour and then apply dp

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

          dp

          first,sort the elements with c

          $$$dp_{i,j,0/1}$$$ being: seeing to the i-th element,having used j money, 0 for no elements of this color have been choosed,1 otherwise

          (sorry for my bad english)

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

    +1

    → Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How G? I had some ideas using aliens trick, but I was still no where close to solution.

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain E?

→ Reply
»
5 days ago, # |
← Rev. 2   Vote: I like it -38 Vote: I do not like it

So, you set this kind of D, what are you gonna do for ABC next time?

  • A. count numbers with 3 divisors (n<=100)
  • B. count numbers with 5 divisors (n<=100)
  • C. count numbers with 8 divisors (n<=10000)
  • D. count numbers with 13 divisors (n<=10000)
  • E. count numbers with 4 divisors (n<=1000000)
  • F. count numbers with 7 divisors (n<=1000000000)
  • G. count numbers with 5 divisors (n<=1000000000000)

huh??????????????????????????????????????????????????????

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

    Why r u mad though?

    → Reply
    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it -15 Vote: I do not like it

      it's just that if these kinds of problems are permitted then they can shit out a task every 30 seconds and one problemset every 10 minutes, and still argue "it makes a problemset anyways" instead of actually considering if it can determine rating properly

      → Reply
»
5 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For D, my solution WA*29. For Sample2 4000000000000, my code output 407097 while the correct answer is 407073. Why?

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

    I was doing the exact same mistake. For the case p^8, p should be prime, you are probably counting for all natural numbers p, if p^8 <= n, but it has to be done only for primes

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

      I was also doing the same mistake. How can so many people think the same way and step into the same trap?? It's actually funny...

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

      Got it, thank you very much!

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

    You're asking why but not providing your code?

    → Reply
»
5 days ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

My Idea for the problem E and F:

E:- Topic — Sorting, DSU || For each node, we will maintain whether the node belongs to arr1 or arr2. We have maintained it using cnt1 and cnt2 variables in DSU. First, sort the edges in ascending order. Then connect the edge one by one and during each Union Operation, We can connect the path from arr1 to arr2 using min(cnt1[node1],cnt2[node2]) or from arr2 to arr1 using min(cnt2[node1],cnt1[node2]). The cost will be no. of operations multiplied by edge weight in current Union. https://atcoder.jp/contests/abc383/submissions/60536697

F:- Topic — Knapsack DP, Sorting || The problem is simple Knapsack, the only catch is how to maintain the number of distinct colors. Suppose the number of distinct colors is X, then we can add K(given constant) by X times. We can sort the items by the colors so that we can check if the next item is of same color or not. We can maintain binary parameter in DP to check if we are taking current color first time or not. https://atcoder.jp/contests/abc383/submissions/60546303

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

    Great job! For E, there's a trick that can simplify your code. You can store the occurrences in one array $$$cnt$$$, add $$$A_i$$$ to it and minus $$$B_i$$$ from it. Then you can just multiply $$$cnt_u$$$ and $$$cnt_v$$$ to see if it gives the answer after the merge. Click to see more information.

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

    Could you please explain how your code checks if a color is being used for the first time in Problem F?

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

      parameter op=0 represents that current color is not used yet, that's why temp variable= k when op=0. Once we use current color, we pass op=1. If next color is different from current color, again pass op=0

      → Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In E, we can find lengths using dijikstra but how would we pair A,B??. One way can be sorting lengths of each pair (Ai,Bi), but that would be k^2.

→ Reply
  • »
    »
    5 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can sort edges based on the weight. As the cost is defined as max weight of the edges on the path, you can add them 1 by 1. When A and B become connected through new edge, it means $$$dist(A, B) = w_{edge}$$$.

    Then it's the greedy idea: if you can pair A, B with a minimal cost of the set, you should do it. Otherwise, the cost would be worse. Consider freshly connected A, B and still not connected C, D. If you don't connect (A, B) now and consider (A, C) + (B, D) was more optimal, that you'll wait until C is connected to the (A, B) component and D is connected with (A, B) component as well. At that moment (C, D) is in the same component too (but maybe they were connected even earlier). Then the 2 holds: $$$cost(A, B) \le cost(A, C)$$$ and $$$cost(C, D) \le cost(B, D)$$$.

    So, $$$cost(A, B) + cost(C, D) \le cost(A, C) + cost(B, D)$$$. And it is better to pair them greedily. Not sure this is a strict proof, but seems strict enough

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

      oh, i was thinking f(x,y) as shortest distance btw x,y

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

      Say |AB|=1, |BD|=2, |CD|=3

      |AB| + |CD| = 1 + 3 = 4 |AC| + |BD| = 3 + 2 = 5

      indeed, |AB| + |CD| <= |AC| + |BD|

      But |BD| < |CD|.

      So I don't think your proof is rigorous.

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

    it's basically the variant of kruskal's algorithm

    → Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can we calculate efficiently next DP:

dp[i][j] = max{0 <= k <= j}(dp[i-1][k] + a[i][j-k])

It's some kind of convulsion but I don't understand how to calculate it.

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with this D solutionIt fails one testcases and i am not able to debug it.

→ Reply
  • »
    »
    5 days ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    try to not use the in-built sqrt function. make your own and try again

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

      fails again here

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

        In the last loop, you should remove the condition (i != sq), as you are leaving out some pairs from (0 to i — 1) when (i == sq).

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

          Thanks for your reply,i realised it rn the mistake

          → Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

any idea about problem G?

→ Reply
»
22 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it rated?

→ Reply