Блог пользователя atcoder_official

Автор atcoder_official, история, 6 месяцев назад, По-английски

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

We are looking forward to your participation!

  • Проголосовать: нравится
  • +52
  • Проголосовать: не нравится

»
6 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Hope to ak!

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hope to solve ABCD!

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope to solve ABCD, and E/F

»
6 месяцев назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

有中国人吗?

Is there Chinese?

»
6 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

swap D and E plz

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 месяцев назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

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

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

    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
    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          6 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 месяцев назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

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

    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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!!

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

D without cancer casework how?

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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).

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    • 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;
        }
      }
    
    
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 месяцев назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

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;

}

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

    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

    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          6 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            6 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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. :)

            • »
              »
              »
              »
              »
              »
              »
              6 месяцев назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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.

        • »
          »
          »
          »
          »
          6 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          thanks

      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится -13 Проголосовать: не нравится

        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.

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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??

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    DP bitset

  • »
    »
    6 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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;
}
»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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();
    }
}

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    oh it was to be printed —

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

    now i solved it

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

D > E

»
6 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

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

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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"

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone kindly breakdown G's solution for me?

»
6 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

My post contest discussion stream

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

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
#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

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Even the example is the same.

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve bonus problem mentioned in F?

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.
»
6 месяцев назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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;
}

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please help me with E problem This is my submission I am not able to understand my mistake https://atcoder.jp/contests/abc354/submissions/55748268

Thank you

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

excited