atcoder_official's blog

Toyota Programming Contest 2023#7（AtCoder Beginner Contest 328） Announcement
By atcoder_official, history, 2 years 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 (59)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Hello!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

I wish everyone luck in the game

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Wish everyone luck!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Hello!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Good Luck everyone

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Good Luck！

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Good luck!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Good luck!

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

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Good luck!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -40 Vote: I do not like it

Problem F:

→ Reply
»
2 years ago, hide # |
← 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
  • »
    »
    2 years ago, hide # ^ |
     
    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
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +15 Vote: I do not like it

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

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    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
»
2 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
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
  • »
    »
    2 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      2 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        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
    • »
      »
      »
      2 years ago, hide # ^ |
       
      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
  • »
    »
    2 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      2 years ago, hide # ^ |
      ← Rev. 4  
      Vote: I like it +12 Vote: I do not like it

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

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

E — Modulo MST and i choose kruskal to solve it. why it failed on case 3? please help me

Your code here...
#include<bits/stdc++.h>
#define cout3(a,b,c) cout<<a<<' '<<b<<' '<<c<<endl;
#define int  long long
using namespace std;
const int maxn=2e5 + 10;
int n,m,k,f[maxn],ans=0;

struct Edge{
    int u,v,w;
}e[maxn];

int find(int x){
    if(f[x] == x) return x;
    return f[x]=find(f[x]);
}

bool cmp(Edge x,Edge y){
    return x.w < y.w;
}
signed main(){
    // freopen("in.txt","r",stdin);
    cin >> n >> m >> k; 
    for(int i=1;i <= n;i++) f[i]=i;
    for(int i=0;i < m;i++) cin >> e[i].u >> e[i].v >> e[i].w,e[i].w%=k;
    sort(e,e + m,cmp);
    for(int i=0;i < m;i++){
        int fv=find(e[i].v),fu=find(e[i].u);
        if(fv == fu) continue;
        f[fv]=fu;
        // cout3(e[i].u,e[i].v,e[i].w);
        ans+=e[i].w;
        ans%=k;
    }
    cout << ans % k;
    return 0;
}
→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    oh no,i understand the reason,i misunderstood "the cost of T is defined as the sum, modulo K, of the weights of the edges in T.".And now,the problem has been solved.

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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

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

    Can you please explain your dsu approach?

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      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
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it -18 Vote: I do not like it

Good problems.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Problem E can be hardcoded :) submission

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Problem F is good, worth solving.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

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

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

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
← 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