Hope to ak!

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

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

hope to solve ABCD!

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

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

Hope to solve ABCD, and E/F

有中国人吗？

Is there Chinese?

swap D and E plz

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

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

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

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

D without cancer casework how?

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

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

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

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;

}

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?

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

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

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

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

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

D > E

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

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

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"

Can someone kindly breakdown G's solution for me?

My post contest discussion stream

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

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

#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

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

Even the example is the same.

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

how to solve bonus problem mentioned in F?

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

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