### atcoder_official's blog

By atcoder_official, history, 5 weeks ago,

We will hold Panasonic Programming Contest 2024（AtCoder Beginner Contest 354）.

We are looking forward to your participation!

• +52

 » 5 weeks ago, # |   +8 Hope to ak!
•  » » 5 weeks ago, # ^ |   0 Failed to solve G...
•  » » » 5 weeks ago, # ^ |   0 I think problem G is a bit hader than usual.
•  » » » » 5 weeks ago, # ^ |   0 Actually some problem G's will be harder than yesterday's
•  » » » 5 weeks ago, # ^ |   0 I used a strange method to solve G, and it passed: It's a kind of "Hill Climbing" that can solve the "Weighted Maximum Independent Set Problem", but I'm not sure about its correctness. You can refer to my code for more details.Who can hack it or analyze its correctness? Thank you.
•  » » » » 5 weeks ago, # ^ |   0 how did you find Weighted Maximum Independent Set for a given graph ?
•  » » » » » 5 weeks ago, # ^ |   0 Just find the weighted maximum clique. And I used hill climbing to find it.
 » 5 weeks ago, # |   0 Hope to solve ABCDE, and one of F and G!And, GL&HF(Good Luck and Have Fun)!
 » 5 weeks ago, # |   0 hope to solve ABCD!
 » 5 weeks ago, # | ← 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.
 » 5 weeks ago, # |   0 Hope to solve ABCD, and E/F
 » 5 weeks ago, # |   -25 有中国人吗？Is there Chinese?
•  » » 5 weeks ago, # ^ |   -25 我是韩国人
•  » » 5 weeks ago, # ^ |   -25 有
•  » » 5 weeks ago, # ^ |   -25 有
•  » » 5 weeks ago, # ^ |   -25 有
•  » » 4 weeks ago, # ^ |   -25 有
•  » » 4 weeks ago, # ^ |   -10 Anyone who answered this question got -15, but 我是中国人。
 » 5 weeks ago, # |   +4 swap D and E plz
•  » » 5 weeks ago, # ^ |   0 +1
 » 5 weeks ago, # |   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 problemI have also added hints for F on CF Step
 » 5 weeks ago, # |   +37 D is created only to give pain and trauma :skull:
•  » » 5 weeks ago, # ^ | ← 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#include #define int long long using namespace std; int tot(int a,int b,int c,int d,int rem1,int rem2,int mod1,int mod2){ int l=0,seen=0,r=0,cur=0; for(int i=a+1;i<=min(a+mod1,c);i++){ if(((i%mod1+mod1)%mod1)==rem1){ seen=1; l=i; } } if(!seen)return 0; for(int i=c;i>=max(a+1,c-mod1+1);i--){ if(((i%mod1+mod1)%mod1)==rem1){ r=i; } } cur=1+(r-l)/mod1; l=0,seen=0,r=0; for(int i=b+1;i<=min(b+mod2,d);i++){ if(((i%mod2+mod2)%mod2)==rem2){ seen=1; l=i; } } if(!seen)return 0; for(int i=d;i>=max(b+1,d-mod2+1);i--){ if(((i%mod2+mod2)%mod2)==rem2){ r=i; } } cur*=1+(r-l)/mod2; return cur; } int calc(int a,int b,int c,int d){ int tmp=tot(a,b,c,d,1,1,4,2)*2; int ans=tmp; tmp=tot(a,b,c,d,2,0,4,2)*2; ans+=tmp; tmp=tot(a,b,c,d,1,0,4,2); ans+=tmp; tmp=tot(a,b,c,d,2,1,4,2); ans+=tmp; tmp=tot(a,b,c,d,3,0,4,2); ans+=tmp; tmp=tot(a,b,c,d,0,1,4,2); ans+=tmp; return ans; } void solve(){ int a,b,c,d;cin>>a>>b>>c>>d; cout<
•  » » » 5 weeks ago, # ^ |   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?
•  » » » » 5 weeks ago, # ^ |   +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
•  » » » » » 5 weeks ago, # ^ |   0 Yeah I also felt was E easier, I should have skipped problem D. Thanks for help.
•  » » 5 weeks ago, # ^ |   +3 I saw geometry and skipped it. Lol, Ended up solving both E and F.
•  » » 5 weeks ago, # ^ |   0 hi, did you solve it? can you share your code
•  » » 5 weeks ago, # ^ |   0 I spent the majoirty of my time on it and never got it :sob
 » 5 weeks ago, # |   -9 how to Memoize this solution ??? without memoization it gives a correct output
 » 5 weeks ago, # |   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
•  » » 5 weeks ago, # ^ |   +2 It's a standard dp on masks problem (The mask should store the removed cards)
•  » » » 5 weeks ago, # ^ |   +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!!
•  » » 5 weeks ago, # ^ | ← 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.
 » 5 weeks ago, # |   +3 D without cancer casework how?
•  » » 5 weeks ago, # ^ |   0 This is my solution,there is some casework but not much.
•  » » 5 weeks ago, # ^ | ← 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).
•  » » 5 weeks ago, # ^ | ← 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; } } 
•  » » 5 weeks ago, # ^ |   0 You can check my video editorials of D, E, and F here
 » 5 weeks ago, # |   0 Solved both C and F using segment Trees. All I see is segment trees now :<
 » 5 weeks ago, # |   0 Can someone pls tell what is wrong with my E — https://atcoder.jp/contests/abc354/submissions/53637099 7 cases are failing
 » 5 weeks ago, # |   0 Missed F by 2 min because D took all my time.
»
5 weeks ago, # |
-18

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

# include<bits/stdc++.h>

using namespace std;

# 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, # ^ |   0 I can't read your code easily. Please write it in markdown.
•  » » » 5 weeks ago, # ^ |   0
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 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, # ^ |   0 what issue ? is my solution correct ?
•  » » » » » » 5 weeks ago, # ^ |   0 Ok, I've found the approximiate wrong.The probelm is that the basic rectangle(which is arr) can be shifted.
 » 5 weeks ago, # |   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?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -13 i've only tried a, b, c and e i guess it would bea-800b-800c-1300 or something like thate-1600 or something like that
•  » » » 5 weeks ago, # ^ |   0 No, that's not what I meant. Is it like div2, div3, div1 + div2, etc.?
•  » » » » 5 weeks ago, # ^ |   +3 ABCs seem to be most similar to div3 I'd say.
•  » » » » » 5 weeks ago, # ^ |   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.
•  » » » » » » 5 weeks ago, # ^ |   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. :)
•  » » » » » » » 5 weeks ago, # ^ |   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.
•  » » » » » 5 weeks ago, # ^ |   0 thanks
•  » » » » 5 weeks ago, # ^ |   -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.
•  » » » » » 5 weeks ago, # ^ |   0 ok, thanks
 » 5 weeks ago, # |   0 What is the idea behind G once the connection graph is built?
•  » » 5 weeks ago, # ^ |   0 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, # |   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??
•  » » 5 weeks ago, # ^ |   0 DP bitset
•  » » 4 weeks ago, # ^ | ← 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.
 » 5 weeks ago, # |   0 why problem use priority_queue wrong? AC x6, WA x11 auto main() -> int32_t { int n = 0; cin >> n; vector> 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&, pair&)> maxPQCmp = [](pair& x, pair& y) { return x.first < y.first;}; priority_queue, vector>,function&, pair&)>> maxPQ(maxPQCmp); vector 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, # |   0 Oh! I've ranked 28! I'm so happy!
•  » » 5 weeks ago, # ^ |   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?
 » 5 weeks ago, # | ← Rev. 2 →   0 Why the problem C cant be solved using priority_queue https://atcoder.jp/contests/abc354/tasks/abc354_cplease explain the issue in the logic void solve(int __tc) { int n; cin >> n; vector> v; rep(i, n) { int a, c; cin >> a >> c; v.push_back({a, c, i+1}); } sort(all(v)); priority_queue> pq; // pq has max cost in the top and i compare it with v[i].cost for(int i=0; i 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, # ^ |   0 oh it was to be printed — , in ascending order. Print these in the following format:now i solved it
 » 5 weeks ago, # |   0 D > E
 » 5 weeks ago, # |   +8 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, # |   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"
 » 5 weeks ago, # |   0 Can someone kindly breakdown G's solution for me?
 » 5 weeks ago, # |   +11 My post contest discussion streamAlso, can someone hack my solution for G?Gentle ping maroonrk because of this
 » 5 weeks ago, # |   0 I think problem D is not very good and I only solved ABCEF.
 » 5 weeks ago, # | ← Rev. 2 →   0 #include #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 a; signed main() { int n; cin>>n; for(int i=0;i>a1>>a2; a.push_back({a1,a2,i+1}); } sort(a.begin(),a.end(),cmp1); int x=0; for(int i=0;ia[i+1].A) { a[i+1]=a[i]; a[i].p=-1; x++; } } cout<
•  » » 5 weeks ago, # ^ |   0
•  » » » 5 weeks ago, # ^ |   0 Thanks for the answer, it was solved perfectly
 » 5 weeks ago, # |   0 F is similar to https://www.spoj.com/problems/SUPPER/Even the example is the same.
 » 5 weeks ago, # |   0 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, # ^ |   0 That picture of you is absolutely adorable！
 » 5 weeks ago, # |   0 how to solve bonus problem mentioned in F?
•  » » 5 weeks ago, # ^ |   0 SummerSky mentioned the idea in his commentThere 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 →   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 #include #include using namespace std; struct Card { int front; int back; }; int N; vector cards; unordered_map 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, # |   0 I think F needn't to use Segment Tree, Fenwick is okay. It only needs prefix maxminum.