atcoder_official's blog

By atcoder_official, history, 5 weeks ago, In English

We will hold Panasonic Programming Contest 2024(AtCoder Beginner Contest 354).

We are looking forward to your participation!

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

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Hope to ak!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to solve ABCDE, and one of F and G!

And, GL&HF(Good Luck and Have Fun)!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hope to solve ABCD!

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Do you notice the problems can be read NOW???

UPD: i'm idiot, didn't notice the statements are not in this contest.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to solve ABCD, and E/F

»
5 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

有中国人吗?

Is there Chinese?

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

swap D and E plz

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F is similar to a variation of Dijkstra (computing edges on at least one shortest path), for which I recently created a practice problem

I have also added hints for F on CF Step

»
5 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

D is created only to give pain and trauma :skull:

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -18 Vote: I do not like it

    It was a great educational problem imo as I struggled for quite some time before landing on a fairly elegant solution. It seemed like a mess at first, but ended up being solvable by repeating a function 8 times which I liked.

    Code
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi, I am new to Atcoder is it normal difficulty of a D problem in ABC? And after how much time does editorial comes out?

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

        It is one of the most difficult D's I've ever seen. IMO, E and F were both miles easier than D today. Editorial takes a couple hours to a day to come out but there's usually a video editorial by evima for first 6 or all problems.

        Evima editorial

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

          Yeah I also felt was E easier, I should have skipped problem D. Thanks for help.

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

    I saw geometry and skipped it. Lol, Ended up solving both E and F.

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

    hi, did you solve it? can you share your code

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

    I spent the majoirty of my time on it and never got it :sob

»
5 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

how to Memoize this solution ??? without memoization it gives a correct output

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone please explain the approach behind problem E to me? I tried using a queue to simulate all possible moves keeping track of available cards but it doesn't seem to be working

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    It's a standard dp on masks problem (The mask should store the removed cards)

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

      Ohh!! I did use a mask to store which cards were used, but I used a queue instead of dp!! I guess replacing my queue operations with dp states will solve my problem. Thanks!!

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    We can discover that when the same card was removed, then the current player's possible move is same.

    So we can just use a binary number to describe the set of cards that was removed and use another variable to store THE CURRENT PLAYER.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

D without cancer casework how?

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

    This is my solution,there is some casework but not much.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Probably there are simpler solutions, but to minimize the casework I implemented a function f(c, d) that computes the solution for rectangles with the origin (0, 0) as the bottom left corner and (c, d) as top right. Since the pattern is 4-periodic in both x and y shifting the rectangle by multiples of 4 does not change the answer. So I just shift everything to the top right quadrant (i.e. I make all coordinates a, b, c, d positive by adding multiples of 4) and then compute the solution using inclusion-exclusion as f(c, d) — f(a, d) — f(c, b) + f(a, b).

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    • Only first two rows matter;
    • In each row, the pattern repeats, the size is (2 + 1 + 1) * (c — a) / 4 + remaining blocks.

    For the remaining blocks, suppose we cacluate from right to left, the pattern can be found if x and y is given: x % 4 and y % 2, there will be 8 cases for the start index.

    int vals[] = {2, 1, 0, 1};
      auto calc = [&](int x, int y) {
        int r = (x % 4 + 4) % 4;
        int idx;
    
        switch (r) {
        case 0:
          idx = (y % 2 != 0) ? 1 : 2;
          break;
        case 1:
          idx = (y % 2 == 0) ? 1 : 0;
          break;
        case 2:
          idx = (y % 2 != 0) ? 3 : 0;
          break;
        case 3:
          idx = (y % 2 != 0) ? 2 : 3;
          break;
        }
    
        return idx;
      };
    // first row
      int r1 = (c - a) / 4 * 4;
      for (int i = 0; i < (c - a) % 4; i++) {
        r1 += vals[idx1];
        idx1++;
        if (idx1 == 4) {
          idx1 = 0;
        }
      }
    
    
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can check my video editorials of D, E, and F here

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved both C and F using segment Trees. All I see is segment trees now :<

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone pls tell what is wrong with my E — https://atcoder.jp/contests/abc354/submissions/53637099 7 cases are failing

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Missed F by 2 min because D took all my time.

»
5 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

CAN SOMEONE TELL WHY IS THIS WRONG FOR E , IM FRUSTATED

include<bits/stdc++.h>

using namespace std;

define int long long int

define endl '\n'

void solve(){ int a,b,c,d; cin>>a>>b>>c>>d; double arr[2][4]; arr[1][0]=0.5; arr[1][1]=1; arr[1][2]=0.5; arr[1][3]=0; arr[0][0]=1; arr[0][1]=0.5;arr[0][2]=0; arr[0][3]=0.5;

double ans=0;
// cout<<(c-a)<<endl;
// cout<<(c-a)/4<<endl;
int x=(c-a)/4;
int y=(d-b)/2;

ans+=x*y*4;

// cout<<ans<<endl;

int xd=((c-a)%4+4)%4;
int yd=((d-b)%2+2)%2;

int stx=(4+a%4)%4;
int sty=(2+b%2)%2;

//portion 1
double pos1=0;
for(int i=stx;i<stx+xd;i++){
    pos1+=(arr[0][i%4]+arr[1][i%4]);
}
pos1*=y;

//portion 2

double pos2=0;
for(int i=sty;i<sty+yd;i++){
    pos2+=(arr[i%2][0]+arr[i%2][1]+arr[i%2][2]+arr[i%2][3]);
}
pos2*=x;

//portion 3
// cout<<stx<<" "<<sty<<" "<<xd<<" "<<yd<<endl; 
double pos3=0;
for(int i=sty;i<sty+yd;i++){
    for(int j=stx;j<stx+xd;j++){
        pos3+=arr[i%2][j%4];
    }
}

// cout<<ans<<" "<<pos1<<" "<<pos2<<" "<<pos3<<endl;

cout<<(int)(2*(ans+pos1+pos2+pos3))<<endl;

}

int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

//int t;cin>>t;while(t--)
solve();
return 0;

}

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

    I can't read your code easily. Please write it in markdown.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        What the things! You said this is problem E but this is problem D.

        Upd:Stupid me! I've realized that it's not the issue in AtCoder. But I can still check your code.

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

          what issue ? is my solution correct ?

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

            Ok, I've found the approximiate wrong.

            The probelm is that the basic rectangle(which is arr) can be shifted.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This is the first time I've paticipated in AtCoder contest. Could someone please say, what is the approximate difficulty of the contest by cf standards?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -13 Vote: I do not like it

    i've only tried a, b, c and e i guess it would be

    a-800

    b-800

    c-1300 or something like that

    e-1600 or something like that

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

      No, that's not what I meant. Is it like div2, div3, div1 + div2, etc.?

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

        ABCs seem to be most similar to div3 I'd say.

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

          I wouldn't agree with that. Normally I can solve all div3 problems without any special effort. As for AtCoder ABC, I can only solve 6 (out of 7) problems normally. And in approximately 50% of rounds I have no idea on how to solve G even after some time spent on it.

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

            But if not div3 then what, div2? And since div3 last position problems are typically rated 2000-2300 from what I gather (and last div4 also had its last problem be of similar difficulty), they would match pretty well with the ABC difficulty curve you mention: most participants below CF yellow will reach but often not solve the hardest problem. :)

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

              It's something between div2 and div3, but closer to div2 in my understanding, yes. Doesn't matter really, just wanted to show that to some people (like me) it seems more like div2 round, rather than div3.

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

          thanks

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

        you can say kinda div 2.5.

        problem a and b are usually div. 4 a and b problem c is usually close to d2. C or d2. B d is like d2. c or d2. d and others followed.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the idea behind G once the connection graph is built?

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

    I suspect finding the largest antichain is somehow solved by decomposing into chains as per Dilworth's theorem through some max-flow/min-cut...

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I spent soooooo much time on D!!!!!!!!!!! NOOOOOOOOOOO!!!!!!!!!! By the way, I think E is more difficult than F.So how do you guys solve E??

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

    DP bitset

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    upd: E not use bitset, it can also AC. I can understand why so many people AC E now.

    It is more stranger that the people solve E are 2223, D are 2092. D、F are quite a lot easy compare with E. D is quite easy by the way, but only 2092 people solve it. I doubt if some of them using chatgpt by solving proble E. I get AC of problem E using code generated by chatgpt 4o.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why problem use priority_queue wrong? AC x6, WA x11

auto main() -> int32_t {
    int n = 0;
    cin >> n;

    vector<array<int, 3>> a(n);
    for (int i = 0; i < n; i++) {
        a[i][0] = i + 1;
        cin >> a[i][1] >> a[i][2];
    }

    sort(a.begin(), a.end(), [](auto& x, auto& y) { return x[1] < y[1]; });

    function<bool(pair<int, int>&, pair<int, int>&)> maxPQCmp =
        [](pair<int, int>& x, pair<int, int>& y) {
            return x.first < y.first;};    
    priority_queue<pair<int, int>, vector<pair<int, int>>,function<bool(pair<int, int>&, pair<int, int>&)>>
        maxPQ(maxPQCmp);

    vector<bool> st(n + 1, true);

    for (int i = 0; i < n; i++) {
        if (maxPQ.size() and maxPQ.top().first >= a[i][2]) {
            auto t = maxPQ.top();
            maxPQ.pop();
            st[t.second] = false;
        }
        maxPQ.push({a[i][2], a[i][0]});
    }

    int haha = 0;
    for (int i = 1; i <= n; i++) {
        if (st[i] == true) haha += 1;
    }

    cout << haha << endl;
    for (int i = 1; i <= n;i++) {
        if (st[i] == true) {
            cout << i << ' ';
        }
    }

    return 0;
}
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh! I've ranked 28! I'm so happy!

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

    I have felt practising topic wise is better for me as implementation speeds improves for me as i solve same topic in a row. But how to choose quality problems.

    how do you choose problems to practise?

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why the problem C cant be solved using priority_queue

https://atcoder.jp/contests/abc354/tasks/abc354_c

please explain the issue in the logic

void solve(int __tc) {
    int n;
    cin >> n;

    vector<array<int, 3>> v;
    rep(i, n) {
        int a, c;
        cin >> a >> c;

        v.push_back({a, c, i+1});
    }

    sort(all(v));

    priority_queue<array<int, 3>> pq; // pq has max cost in the top and i compare it with v[i].cost
    for(int i=0; i<n; i++) {
        while(!pq.empty() and pq.top()[0] > v[i][1]) {
            pq.pop();
        }
        pq.push({v[i][1], v[i][0], v[i][2]});
    }

    print1(pq.size());
    while(pq.size() > 0) {
        cout << pq.top()[2]<< " ";
        pq.pop();
    }
}

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

    oh it was to be printed —

    , in ascending order. Print these in the following format:

    now i solved it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

D > E

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

This time I solved problem F much faster than usual(maybe 15 minutes), because I have met a similar one, https://mirror.codeforces.com/contest/650/problem/D , during my virtual participation.

This makes me believe again that hard work will pay off sooner or later.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me to figure out that why my solution for Problem C is running locally but giving wrong answer on atcoder ? (I have also not used any global variables). "https://cl1p.net/code_c"

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone kindly breakdown G's solution for me?

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

My post contest discussion stream

Also, can someone hack my solution for G?
Gentle ping maroonrk because of this

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think problem D is not very good and I only solved ABCEF.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct zp
{
    int A,C,p;
};
bool cmp1(zp a,zp b)
{
    if(a.C<=b.C)return true;
    else return false;
}
bool cmp2(zp a,zp b)
{
    if(a.p<=b.p)return true;
    else return false;
}
vector<zp> a;
signed main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int a1,a2;
        cin>>a1>>a2;
        a.push_back({a1,a2,i+1});
    }
    sort(a.begin(),a.end(),cmp1);
    int x=0;
    for(int i=0;i<n-1;i++)
    {
        if(a[i].A>a[i+1].A)
        {
            a[i+1]=a[i];
            a[i].p=-1;
            x++;
        }
    }
    cout<<n-x<<"\n";
    sort(a.begin(),a.end(),cmp2);
    for(int i=0;i<n;i++)
    {
        if(a[i].p!=-1)cout<<a[i].p<<" ";
    }
    return 0;
}

why Re

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

F is similar to https://www.spoj.com/problems/SUPPER/

Even the example is the same.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My classmate hzr hzr2023 got a good grade in this contest. but after the contest, He changed his country to the USA...

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

    That picture of you is absolutely adorable!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve bonus problem mentioned in F?

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

    SummerSky mentioned the idea in his comment

    There are 2 methods.

    • Calculate the number of LIS ending at $$$i$$$, call it $$$end[i]$$$. Calculate the number of LIS starting at $$$i$$$, call it $$$start[i]$$$. The number of LIS crossing the $$$i-th$$$ element is $$$start[i] \cdot end[i]$$$. If this number is equal to the number of LIS of the entire array, then this index will be included in all LIS. Counts can be exponential, so you can compute it modulo some prime and hope for no collisions.
    • If the length of LIS ending at $$$i$$$ is $$$L$$$, then we know that $$$i-th$$$ element would go into position $$$L$$$ of the final LIS (assuming that it's part of at least one LIS). We can iterate over every index and check if there are other elements that are contesting for position $$$L$$$. If not, then this element will be part of every LIS.
»
4 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

upd: E not use bitset, it can also AC. I can understand why so many people AC E now.

So many people solve E in the competition. I doubt if some of them using chatgpt. I get AC of problem E using code generated by chatgpt 4o. The code is as follows.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

struct Card {
    int front;
    int back;
};

int N;
vector<Card> cards;
unordered_map<int, bool> memo;

bool canWin(int state) {
    if (memo.count(state)) return memo[state];

    // Check all pairs of cards
    for (int i = 0; i < N; ++i) {
        if (!(state & (1 << i))) continue; // Card i is already removed
        for (int j = i + 1; j < N; ++j) {
            if (!(state & (1 << j))) continue; // Card j is already removed
            if (cards[i].front == cards[j].front || cards[i].back == cards[j].back) {
                int newState = state & ~(1 << i) & ~(1 << j);
                if (!canWin(newState)) {
                    memo[state] = true;
                    return true;
                }
            }
        }
    }
    memo[state] = false;
    return false;
}

int main() {
    cin >> N;
    cards.resize(N);
    for (int i = 0; i < N; ++i) {
        cin >> cards[i].front >> cards[i].back;
    }

    int initialState = (1 << N) - 1; // All cards are initially on the table
    if (canWin(initialState)) {
        cout << "Takahashi" << endl;
    } else {
        cout << "Aoki" << endl;
    }

    return 0;
}

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think F needn't to use Segment Tree, Fenwick is okay. It only needs prefix maxminum.