atcoder_official's blog

UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312) Announcement
By atcoder_official, history, 11 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

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

Wish this contest will be great!

→ Reply
»
11 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
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can you make any feature on the atcoder's website to make a discussion part in the announcements like here!!

I think it will be specialized to the website and a good one to the users.

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

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

→ Reply
»
11 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
  • »
    »
    11 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
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No bro it is not. for problem B you just write a code. no idea.

    → Reply
  • »
    »
    11 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
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      bro did you solved problem D?

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

        Yeah. It was simple DP.

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

          yes,here is the code,

          code
          → Reply
    • »
      »
      »
      11 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
      • »
        »
        »
        »
        11 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
        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can you please clarify how you simplified it?

          → Reply
          • »
            »
            »
            »
            »
            »
            11 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
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Useful learning stuff.

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

I am unable to understand b and c in this contest..

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

Could only solve A B C

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

anyone solved problem D with Dp??

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

    here is the formatted code,

    code
    → Reply
»
11 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
»
11 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
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 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
    • »
      »
      »
      11 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
»
11 months ago, # |
  Vote: I like it +20 Vote: I do not like it

really hard problem e

→ Reply
»
11 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
»
11 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
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do E ;-;

→ Reply
»
11 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
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the problem B Tak Code in a better and more understandable way?

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

Please can I see the solution for C

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

Can someone tell me why this solution for C results in WA:

#include <bits/stdc++.h>

using namespace std;

int main() {
  size_t n, m;
  cin >> n >> m;

  set<size_t> sellers, buyers;
  for (size_t i = 0; i < n; ++i) {
    size_t price;
    cin >> price;
    sellers.insert(price);
  }
  for (size_t i = 0; i < m; ++i) {
    size_t price;
    cin >> price;
    buyers.insert(price);
  }

  size_t price = max(*buyers.rbegin(), *sellers.rbegin());
  for (auto lo = min(*buyers.begin(), *sellers.begin()), hi = price;
       lo <= hi && price > lo;) {
    auto mid = lo + (hi - lo) / 2;

    size_t numSellers = distance(sellers.begin(), sellers.upper_bound(mid));
    size_t numBuyers = distance(buyers.lower_bound(mid), buyers.end());

    if (numSellers >= numBuyers && price > mid) {
      price = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }

  cout << price << "\n";
}
→ Reply
»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

The key part of Ex is similar to CF1732D1

→ Reply
»
11 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
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abc312/editorial/6864 There may be a problem in D editorial(Only English Version)! https://cdn.luogu.com.cn/upload/image_hosting/0jki5uai.png

It should be dp(i+1,j+1) and dp(i+1,j-1).

→ Reply
»
11 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
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is D possible to solve without dp?

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

Can someone help me understand why this TLE? Thanks.

Submission

→ Reply
»
8 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
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does there exist a faster solution to problem D?

→ Reply