atcoder_official's blog

Toyota Programming Contest 2023#7（AtCoder Beginner Contest 328） Announcement
By atcoder_official, history, 12 months ago, In English

We will hold Toyota Programming Contest 2023#7（AtCoder Beginner Contest 328）.

We are looking forward to your participation!

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

Comments Comments (60)
| Write comment?
»
12 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Hello!

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

Hello everyone! Is everyone ready to contest? I wish luck to everyone! :)

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

I wish everyone luck in the game

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

Wish everyone luck!

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

Hello!

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

Good Luck everyone

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

Good Luck！

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

Good luck!

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

Good luck!

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

Is AtCoder down again? Why is it always failing during contests?

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

Good luck!

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

Problem F:

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

for problem E i did the black box strategy since i don't know the algorithm, I copied and pasted solution from GFG with some modification of course

why does it give a wrong answer for testCase 3?

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

    Kruskal's Algorithm wont return minimum cost spanning tree in this case.

    As its modulo sum.

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

    becoz, it asked min modulo of answer, not min answer modulo.

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

    You can actually try out all possible parent arrays (these arrays will correspond to single predecessor graphs) with vertex 1 as your root. We will have atmost 7 ^ 8 = 6 * 10 ^ 6 such arrays of which some won't correspond to trees. We can eliminate those by a simple dfs. My solution : link

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

      what does the function test stand for ?

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

        It is where you check whether all vertices are reachable in a single dfs run from vertex 1.

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

Nice problems, I liked solving D, E and F today.

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

In problem G, were $$$O(2^n \cdot n^2)$$$ solutions intended to pass if optimized well?

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

    No it will get MLE :(

    And the memory limit is intentionally set to $$$512\operatorname{MB}$$$, since you need long long it will cost $$$22\times2^{22}\times8\operatorname{B}=704\operatorname{MB}$$$.

    UPD: Ohhhhhhhhhhhh I optimized the space (halved it) and got AC

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

      You can reduce space complexity to O(2^n) by solving the dp in increasing order of popcount and only allocating space for current and next popcount.

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

        Alternatively, just maintain $$$dp_{mask}$$$ = min cost to take these elements from A and map them to a prefix of B. Then just take a consecutive subarray of elements without a split $$$[i, j]$$$ in one shot using an $$$O(n ^ 2)$$$ loop.

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

      That's because you're using $$$O(2^n \cdot n)$$$ memory. On the largest input this will use around 700 MB, but the memory limit is only 512 MB.

      But you can notice that some of the $$$2^n \cdot n$$$ states aren't valid, and the number of valid states is just small enough ($$$46137344$$$ on max test) to fit in the memory limit. In my code I only allocate memory for valid states and it gets AC. Submission

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

    I don't think so.
    My $$$O(2^n \cdot n)$$$ soln took 0.9/2.8s time.
    $$$O(2^n \cdot n^2)$$$ should get TLE.

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 4   Vote: I like it +12 Vote: I do not like it

      Nevermind mine turned out to be O(n * 2^n)...

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

      My $$$O(2^n \cdot n^2)$$$ soln passed in 0.4s. The key part being that it only actually uses ~$$$8 \cdot 10^7$$$ ops in practice due to not all possible values of $$$1 \leq i \leq j \leq n$$$ being used in a mask.

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

        The key part of your solution is that it's actually $$$O(2^n \cdot n)$$$, not $$$O(2^n \cdot n^2)$$$.

        For each of the $$$2^n$$$ bitmasks and for each subarray $$$[i, j]$$$, your solution does calculations for this subarray if all of the corresponding bits of this subarray are $$$0$$$.

        For a subarray of length $$$k$$$, there are $$$2^{n-k}$$$ bitmasks where all bits of this subarray are $$$0$$$. There are also $$$(n + 1 - k)$$$ subarrays of length $$$k$$$.

        This means that the number of operations your code does is on the order of

        $$$\displaystyle\sum_{k=1}^n 2^{n-k}(n+1-k)$$$

        $$$=\displaystyle\sum_{k=1}^n 2^{k-1}\cdot k$$$

        $$$\le \displaystyle\sum_{k=1}^n 2^{k-1}\cdot n$$$

        $$$= n\displaystyle\sum_{k=1}^n 2^{k-1}$$$

        $$$= n\displaystyle\sum_{k=0}^{n-1} 2^k$$$

        $$$= n(2^n-1)$$$

        $$$\subseteq O(2^n \cdot n)$$$

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

For problem E, I tried using a Dijkstra to find the MST. To my concern, the implementation is well written. Why didn't it work?

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

Please can anyone explain how to solve G? my n*2^n method got WA, thanks a lot.

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

    from where can we learn such DSU tricks like problem f?

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

      CP Algorithms website is particularly useful. This page contains all the ideas needed for F — link

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

In editorial of E, how is he enumerating the spanning trees?

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

    from what I understand, it sets last $$$n-1$$$ bits of $$$m$$$ bits and use next_permutation to enumerate

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

So, origin problems:

D — abc307D Mismatched Parentheses

Because of some problems, it isn't completed.

May update.

Very special things:

In sometimes in the contest, I'd ever solved problem E and don't solve problem D!

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

Porblem F is very great, and I have seldom solved a problem which uses weighted dsu (this may be the second time). I learned a lot from this problem, thank you, atcoder team.

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

    Can you please explain your dsu approach?

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

      In fact, I didn't solve it during the contest, and I also learned this from the editorial. My dsu approach is just the same as the one mentioned in the editorial. Different from the simple dsu, which only records whether two nodes are "connected", this weighted dsu would maintain another variable which stores the "relation" from each node to its ancestor node. I think you can search this topic on the Internet, or, blogs at codeforces. I think there have been several blogs talking about this at codeforces.

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

Why does kruskal not work for problem E ?

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

Problem E can be hardcoded :) submission

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

Problem F is good, worth solving.

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

Why in B they didn't take 12 December???

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

    Day j of month i is said to have a repdigit date if and only if one can represent both i and j using just one kind of digit in decimal notation. For example, December 12th is not a repdigit date, as i = 12 and j = 12, requiring two kinds of digit (1 and 2) to represent them.

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

Is there a solution for problem D without the use of stack?

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

    no because worst case will be $$$O(n^2)$$$ without it

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

    I solved it without using a stack or something similar. https://atcoder.jp/contests/abc328/submissions/47497326

    My approach was to find each "ABC" and expand it to the left and right trying to find more prefixes and suffixes like "AB" with "C" and "A" with "BC". Then I remove the matched sub string [l, r] from S and continue the process from l.

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

E = Brute Force. Do you see the $$$2<=n<=8$$$?

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

Can someone tell me the data of the F HACK or modify my code? Thanks!

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int n,q;
int fa[200001],g[200001];
inline int find(int x){
    if(fa[x]==x)return x;
    int f=find(fa[x]);
    g[x]+=g[fa[x]];
    return fa[x]=f;
}
inline bool merge(int x,int y,int c){
    int fx=find(x),fy=find(y);
    if(fx==fy)return g[y]-g[x]==c;
    fa[fx]=fy;
    g[fx]=g[y]-g[x]-c;
    return true;
}
signed main(){
    n=read();q=read();
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=q;i++){
        int a=read(),b=read(),c=read();
        if(merge(a,b,c)){
            write(i);
            putchar(' ');
        }
    }

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

HELP, Can anyone explain the F solution? Actually, What are we storing in the weight array?

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

    It is the weight of the path from the node to the leader of that component.

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

      Thanks. I think weights are stored from leader to node. Leaders will always have weight zero.

      Img
      → Reply