atcoder_official's blog

UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312) Announcement
By atcoder_official, history, 13 months ago, In English

We will hold UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312).

We are looking forward to your participation!

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

Comments Comments (38)
| Write comment?
»
13 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Finally AtCoder added a link to the discussion area on the homepage of ABC!

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

Let's work hard , get a great mark together !

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

  1. Is atcoder begineer contest c,d is more easier than b? is it right? Most of the time b implementation is heavy for me.

  2. Atcoder abc contest: b,c,d is how much rating simillar than a codeforces problem?

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

    Generally, you don't have to prove anything in B since most of the time you can just brute force it.

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

    B C D were all <= 1400 rated. F was <= 1600. I couldn't solve E and G.

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

      bro did you solved problem D?

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

        Yeah. It was simple DP.

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

          yes,here is the code,

          code
          → Reply
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      G was easy to be honest , I forgot to consider the case of all triplets in a subtree of a particular node, but after I implemented time got over :(

      The solution is to consider the count of nodes above a node X and the number of nodes in the subtree of each child of X.

      We can form a triplet in two ways :

      1st way : take all the nodes above node X and you can pair it with any two nodes which can be choosen from the subtree of X's children nodes.

      2nd way : take all the triplets among X's children nodes' subtree

      Suppose z = count of nodes above X.

      z can be calculated as n-sub(X) , sub means subtree size of node X

      lets say a1, a2 , a3,...., am are the children of node X. We need to calculate the all pair product sum of the subtree sums of a1, a2 , a3,....,am.

      Then ans1 = z*(all pair product sum of (sub(a1),sub(a2),sub(a3),....,sub(am))

      ans2 = (all triplet product sum of (sub(a1),sub(a2),sub(a3),....,sub(am))

      I forgot ans2 case during contest

      Final ans is ans1+ans2 , and we will consider all the nodes of the tree as X , tree rooted at 1.

      My implementation : code

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

        Just $$$C(n,3)-(\sum_{i,j}dis_{i,j}-C(n,2))$$$. It's a classic problem.

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

          can you please clarify how you simplified it?

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

            $$$i<j<k$$$ means $$$i,j,k$$$ just need to count once, so it equals to count i in the simple path of j,k. So it can be simplified.

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

        Useful learning stuff.

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

anyone solved problem D with Dp??

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

    here is the formatted code,

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

Can someone point out what's wrong in this solution of F.It gives WA on 1 testcase.

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

In my solution i got WA on 3 testcases can anyone tell my mistake code

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

I'v passed A, B, C and G.

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

    how to approach G,i did D in place of G.

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

      you can find the number of tuples of integers $$$(i,j,k)$$$ such that $$$i<j<k<n$$$ and the given tree does contain a simple path that contains all of vertices $$$i,j$$$ and $$$k$$$. the answer is $$$\sum_{i=1}^n \sum_{j=i+1}^n (dis(i, j) - 1)$$$. This is a typical problem.

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

really hard problem e

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

cleaner solution to B: Let us observe the coordinates of # and . in the grid.

visual interpretation

We can see, in respect to the upper left corner, the red lines are $$$x=3$$$ and $$$y=3$$$, and the blue lines are $$$x=5$$$ and $$$y=5$$$. Then, the area with . are $$$\max(x,y)=3$$$ and $$$\min(x,y)=5$$$ respectively. Then, the area with # become $$$\max(x,y)<3$$$ and $$$\min(x,y)>5$$$. You can use these directly to get AC.

AC submission

→ Reply
»
13 months ago, # |
  Vote: I like it -26 Vote: I do not like it

chokudai cn449 problem F, I got it accepted after the context, the statement doesn't mention I can take a regular cans without opening it with a can opener. If Ti=1, the i-th item is a regular can; if you obtain it and use a can opener against it, you get a happiness of Xi. so if I wasn't able to open it I assumed I can't take it, and there's no where in the statement mentioned that I can take it with zero happienes.

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

How to do E ;-;

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

Can anyone check, whats wrong in this solution for problem F

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

The key part of Ex is similar to CF1732D1

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

Could someone tell me why did the total number of tuples in G was n*(n-1)*(n-2)/6 ? Why should the number /6 ?

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    $$$n \choose 3$$$. also because of the $$$i < j < k$$$ constraint

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

For problem C, after watching the official video editorial, I am surprised to see a solution which doesn't use binary search and doesn't use pairs.: Submission

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

is D possible to solve without dp?

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

i think problem F might need to say maximum total happiness that you get by obtaining atmost M items out of N , instead of maximum total happiness that you get by obtaining M items out of N. can anyone conform

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

Does there exist a faster solution to problem D?

→ Reply