atcoder_official's blog

By atcoder_official, history, 7 weeks ago,

We will hold AtCoder Beginner Contest 343.

We are looking forward to your participation!

• +53

 » 7 weeks ago, # | ← Rev. 2 →   0 I hope good luck to everyone!
•  » » 7 weeks ago, # ^ |   -11 Did I say something bad? Just downwoting for no reason
 » 7 weeks ago, # |   -13 Hope to solve A,B,C,D
 » 7 weeks ago, # |   0 I hope everyone enjoyed testing this round a lot!
 » 7 weeks ago, # |   0 Hope to solve A,B,C,D!
 » 7 weeks ago, # |   0 Hope to solve A,B,C,D,E!
•  » » 7 weeks ago, # ^ |   0 I hope as you
•  » » » 7 weeks ago, # ^ |   0 GL,HF! ys,qd!
 » 7 weeks ago, # |   0 I hope us all solve the A,B,C,D at least,and hope me solve the E even the F .
 » 7 weeks ago, # |   +8 ABC 343 ......Looks like questions will involve palindromes?
•  » » 7 weeks ago, # ^ |   0 true.
•  » » 7 weeks ago, # ^ |   +3 and $7\ast 7\ast 7$
 » 7 weeks ago, # |   0 Good Lucky
 » 7 weeks ago, # |   0 Are there any Chinese? (I'm not good at English)
 » 7 weeks ago, # | ← Rev. 2 →   0 Why this code is getting TLE for task F
 » 7 weeks ago, # |   +17 What are those 2 test cases in problem E ??there were many WA's in Problem E.
•  » » 7 weeks ago, # ^ |   0 No idea. I too want to know.
•  » » 7 weeks ago, # ^ |   +38 You cannot fixate the first cube to be in (0,0,0) and require that both of the other 2 have positive coordinates. The symmetry is wrong. Imagine a cube1 in the middle, cube 2 with positive y and positive z and cube 3 with negative y and positive z. Here are the cases for which your solutions should fail: Test cases960 33 1 563 173 40 568 163 45 619 160 30 627 171 20 671 143 24 678 135 27 679 139 24 684 165 5 687 156 10 687 159 8 694 145 15 698 143 15 699 135 20 706 139 15 711 147 8 743 128 10 760 127 5 768 117 9 780 117 5 798 108 5 806 107 3 844 85 5 850 85 3 854 83 3 960 33 1 
 » 7 weeks ago, # |   +53 E is the most garbage problem I've ever had the misfortune of attempting
•  » » 7 weeks ago, # ^ |   0 is it simulation ? how to solve it ?
•  » » » 7 weeks ago, # ^ |   0 Notice that we can fix the first point to be (0,0,0) without loss of generality. Now, for the second and third points, we can brute upto (7,7,7) and (14,14,14) respectively. For some triplet of points, we can check the answer in O(1) by taking the intersecting cuboids and inclusion exclusion. Atleast that's what I did. I get wa on two testcases and cannot fix it no matter what I do ;-;
•  » » » » 7 weeks ago, # ^ |   0 try fixing the first point at (7,7,7) , doing this got me AC.
•  » » 7 weeks ago, # ^ |   +22 Sounds like a skill issue
•  » » » 7 weeks ago, # ^ |   +14 Ape has no skill, only issues
 » 7 weeks ago, # | ← Rev. 2 →   0 Can anyone tell me why this $O(n\log^2 n)$ solution cannot pass F?https://atcoder.jp/contests/abc343/submissions/50837622
•  » » 7 weeks ago, # ^ |   0 I guess the time limit is tight. I first wrote a nlog^2n solution that didn't pass then I switched to nlogn by merging two sorted lists each time I merge two nodes. My submission
 » 7 weeks ago, # |   +3 G is the same as this task.But the data range of that task is smaller.
 » 7 weeks ago, # |   0 Problem G is a direct application of a standard technique and CF1200E: Compress Words. I've added hints and thought process for this problem on CF Step
 » 7 weeks ago, # |   0 Can someone please tell me what is wrong with my solution to Problem F? I get the TLE part, but not the WA.
 » 7 weeks ago, # |   0 JasonQin is a cheater. He asked me solutions during the contest.
 » 7 weeks ago, # |   +3 For problem E,is there any special conditions that I should take into consideration? I got 24/26 AC and it drove me crazy。
•  » » 7 weeks ago, # ^ |   0
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Search the 3rd cube within [-7, 14]
•  » » » 7 weeks ago, # ^ |   0 I'll try, thanks a lot.
•  » » » 7 weeks ago, # ^ |   0 i searched from 0 23 for both cubes still WA
•  » » » » 7 weeks ago, # ^ |   0 maybe it's the algorithm?
•  » » » 7 weeks ago, # ^ |   0 yes it got AC
•  » » 7 weeks ago, # ^ |   0 same i was also stuck there my solution https://atcoder.jp/contests/abc343/submissions/50843371
•  » » 7 weeks ago, # ^ |   +4 You cannot fixate the first cube to be in (0,0,0) and require that both of the other 2 have positive coordinates. The symmetry is wrong. Here are the cases for which your solutions should fail: Test cases960 33 1 563 173 40 568 163 45 619 160 30 627 171 20 671 143 24 678 135 27 679 139 24 684 165 5 687 156 10 687 159 8 694 145 15 698 143 15 699 135 20 706 139 15 711 147 8 743 128 10 760 127 5 768 117 9 780 117 5 798 108 5 806 107 3 844 85 5 850 85 3 854 83 3 960 33 1 
•  » » » 7 weeks ago, # ^ |   +3 Why though? Isn't every symmetry which is possible using negative co-ordinates possible wrt the second cube which we assign?
•  » » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 No. That is an interesting fact. It is not intuitive for me either. If it was 2 cubes in total instead of 3, it would be fine.I wonder if for 3 squares, you would need negative number, but Im not sure either.
•  » » » » 7 weeks ago, # ^ |   +11 If the cubes given by $C(a_i,b_i,c_i)$ satisfy $a_1  » 7 weeks ago, # | ← Rev. 2 → 0 This is my solution for F.Luckily i didn't got tle.  » 7 weeks ago, # | 0 Can anyone Please give me the Solution of Problem-F — Second Largest Query ... •  » » 7 weeks ago, # ^ | ← Rev. 2 → 0 I use segment tree. You can maintain [max, sec_max, cnt_max, cnt_sec_max] in each node. Then it's just if-else case working in your propagation function.  » 7 weeks ago, # | +8 I try to find point B and C in [0,14], but I got wrong answer on 04_killer2_00.txt and 04_killer2_00.txt. Who can tell me why :( •  » » 7 weeks ago, # ^ | +1 Problem E •  » » 7 weeks ago, # ^ | ← Rev. 3 → 0 You cannot fixate the first cube to be in (0,0,0) and require that both of the other 2 have positive coordinates. The symmetry is wrong. Here are the cases for which your solutions should fail: Test cases960 33 1 563 173 40 568 163 45 619 160 30 627 171 20 671 143 24 678 135 27 679 139 24 684 165 5 687 156 10 687 159 8 694 145 15 698 143 15 699 135 20 706 139 15 711 147 8 743 128 10 760 127 5 768 117 9 780 117 5 798 108 5 806 107 3 844 85 5 850 85 3 854 83 3 960 33 1  •  » » » 7 weeks ago, # ^ | 0 Could you please tell me the answer for one of these testcase? •  » » » » 7 weeks ago, # ^ | 0 Its Yes for all of them. Just take the solution from someone in contest if you want to see. Lazy people... •  » » » » » 7 weeks ago, # ^ | 0 Thinks.  » 7 weeks ago, # | ← Rev. 2 → +3 F can be solve even if we need to find the number of occurrences of the k-th maximum.If k <= 20, we can still used Segment TreeIf k <= n, simple 3D Mo does the task: Code •  » » 6 weeks ago, # ^ | ← Rev. 2 → 0 Can you explain get_ans() function in your code? I used map to track the occurrence of all elements inside [L:R] then get the second largest value by std::next(map.begin()) but got TLE. •  » » » 6 weeks ago, # ^ | +1 It is a well-known trick. We use additional sqrt-decomposition to find the number of occurrences of x (CNT array).You have a problem: you are changing cnt array during 3D Mo (you use cnt to maintain a set of current elements). And you need to know the k-th minimum of the current set of numbers. We want to modify cnt in O(1) and get k-th minimum in O(sqrt(n)). The number of modify queries is O(n^5/3) and the number of get queries is O(q) — we call get exactly once for each query.We can perform these queries in required time. Divide array into blocks size of sqrt(n). For each block we maintain the number of different elements in it. Modify is trivial. To get k-th minimum, we need to find a prefix of blocks with >= k different elements, and then find the k-th minimum in the last of these blocks. •  » » » » 6 weeks ago, # ^ | +8 I got it. Thank you.  » 7 weeks ago, # | 0$O(n\sqrt{n})$passes in 500 ms in F. •  » » 7 weeks ago, # ^ | 0 How do you remove log factor in sqrt decomp? I tried but could not do it without map. •  » » » 7 weeks ago, # ^ | 0 Why do you need a map? I just stored the maximum, second maximum, and the frequencies of these two for each window. •  » » » » 7 weeks ago, # ^ | 0 Lmao I am so dumb. I stored frequencies of all elements in map to mage updates O(logN), instead of making the update O(segment size). Thanks. •  » » » » 7 weeks ago, # ^ | ← Rev. 4 → 0 My submission I am storing maximum and second maximum using sqrt decomposition . But I am getting wrong answer. Can you pls check what is wrong with it ?  » 7 weeks ago, # | ← Rev. 3 → 0 can anyone help me point out why my solution for problem C fails on testcase17.txt https://atcoder.jp/contests/abc343/submissions/50848352and my solution for problem D only fails on the last testcase: https://atcoder.jp/contests/abc343/submissions/50851607edit: found the cause for WA in problem D, integer overflow. Idk cause for problem C still •  » » 7 weeks ago, # ^ | 0 This is the only test point that I failed. •  » » 7 weeks ago, # ^ | 0 Just avoid using float/double unless you absolutely have to.Your code is AC without the cbrt(n): submission •  » » 6 weeks ago, # ^ | ← Rev. 2 → 0 same as you problematcoder compile use below argsg++ --std=c++20 -O3testcase17 will output 10662526601  » 7 weeks ago, # | 0 I have one question to ask: Do Atcoder encourages participants to use Surfing and Searching Internet for solution? In today's problem E editorial's video, it encouraged to use ChatGPT to convert a python written code to a C++ version. Doesn't it break the fairplay and similar to cheating? (As in almost every official contest, it's punishable to surf and search internet during contest)  » 7 weeks ago, # | 0 Can somebody help me with problem D? I know understand/know why i am getting TLE #include #include #include #include #include #pragma GCC optimize ("O3") #pragma GCC target ("sse4") //======vector========== #define vi vector #define vd vector #define vs vector #define vll vector #define vc vector #define vld vector #define vf vector //=====deque========= #define di deque #define ds deque //=====set============ #define si set #define sll set #define sc set #define mp make_pair #define len(x) x.length() #define sz(x) x.size() //====greater()======= #define gld greater() #define gi greater() #define gll greater() #define gc greater() //=====static_cast()==== #define sci(x) static_cast(x) #define scc(x) static_cast(x) #define scd(x) static_cast(x) #define scll(x) static_cast(x) //========others=============== #define all(x) x.begin(),x.end() #define ll long long #define ld long double #define te *= #define pe += #define me -= #define de /= #define ge >= #define le <= #define ee == #define ne != #define pb push_back #define tos(x) to_string(x) #define nl '\n' //=====END OF TEMPLATE=========== using namespace std; int check(vi a){ int q = sz(a); si s; for(int i = 0; i < q; i++){ s.insert(a[i]); } return sz(s); } void solve(){ int n , t; cin >> n >> t; vi mex; for(int i = 0; i < n; i++) mex.pb(0); for(int i = 0; i < t; i++){ int a, b; cin >> a >> b; mex[a-1] pe b; cout << check(mex) << nl; } } int main (){ ios::sync_with_stdio(false); cin.tie(nullptr); //ll t; cin >> t; //for(;t--;){ solve(); //} return 0; }  •  » » 7 weeks ago, # ^ | 0 It seems like your code is$O(n^2)$.This is my solution:Because of the large value range of the scores, we first discretize each person's score using unordered_map. Then we use buckets to count each person's score, and bitset to maintain whether the score occurs or not, and just output the number of 1's in bitset.Just like this(code in C++): #include #include #include #include #include using namespace std; unordered_mapHash; bitset<200010>bz; long long scores[200010],sum[200010],Hash_cnt; int main() { int n,q; scanf("%d%d",&n,&q); bz[0]=1; sum[0]=n; for(int i=1;i<=q;i++) { long long x,y; scanf("%lld%lld",&x,&y); sum[Hash[scores[x]]]--; if(sum[Hash[scores[x]]]==0) bz[Hash[scores[x]]]=0; scores[x]+=y; if(Hash[scores[x]]==0) Hash[scores[x]]=++Hash_cnt; sum[Hash[scores[x]]]++; bz[Hash[scores[x]]]=1; printf("%lld\n",bz.count()); } } 520ms  » 7 weeks ago, # | 0 I have a way to solve problem use$O(n \sqrt n \log n)$.(My English is quite bad , don't mind)First,divide the array into$\sqrt n$blocks.For each block ,we give it a map it means that number x appear map[x] times in the block.A change for A[x] only need$\log n$time.So,We can find the Largest number by auto it = map.end();it--; it is a pair that the first value is the largest number and it's appear count is the second value.For the second large number,we can use the same way and the only difference is to it-- 2 times.(Note: there maybe only 1 value that map.size()=1 ,so we should have a special decision.For each query,We can record the max and the 2nd.For block which is all in the query range,We should get the max and 2nd (only this two can change our recording) by following the above method.It take$O(\sqrt n \log n)$time.For other pos,We can record in brute force because the number of it will not be larger than$2\sqrt n$.My code is here:Code  » 7 weeks ago, # | 0 My first code gives ACx31, WAx1 on Problem C.I thought of enumerating from$\sqrt[3]{n}$to$1\$ and checking if its cube is a palindrome. #include #include #include using namespace std; unsigned long long n,cub,tmp; bool check(unsigned long long qaq) { int a[30]; int cnt = 0; while (qaq) { a[++cnt] = qaq % 10; qaq /= 10; } for (int i = 1,j = cnt;i <= j;i++,j--) if (a[i] != a[j]) return false; return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; cub = floor(cbrt(n)); for (unsigned long long i = cub;i >= 1;i--) { tmp = i * i * i; if (check(tmp)) { cout << tmp << '\n'; return 0; } } } While my second solution gots AC: (pre-calculating palindromic cube number and do binary search) #include #include #include using namespace std; const int N = 1e6 + 10; long long n,l,r,mid,ans,cnt1; long long a[N]; long long tmp; bool check(__int128_t qaq) { long long a[30]; int cnt = 0; while (qaq) { a[++cnt] = qaq % 10; qaq /= 10; } if (a[cnt] == 0) return false; for (int i = 1,j = cnt;i <= j;i++,j--) if (a[i] != a[j]) return false; return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); for (long long i = 1;i <= 1e6;i++) if (check(i * i * i)) a[++cnt1] = i * i * i; cin >> n; l = 1; r = cnt1; while (l <= r) { mid = (l + r) >> 1; if (a[mid] <= n) { ans = mid; l = mid + 1; } else r = mid - 1; } cout << a[ans] << '\n'; } What happened? I think two solutions are the same.
•  » » 7 weeks ago, # ^ |   0 The first solution uses double (cbrt). Try removing it.
 » 7 weeks ago, # |   0 can someone please tell expected rating of E and F que according to codeforces rating system??
 » 7 weeks ago, # |   0 can anyone prove why for problem Ethe solution that first cube placed at (0,0,0)second cube from 0->7 and third cube from 0->14 fails.i am trying to visualize the placement of 3 cubes not possible from this kind of arrangement, but i am not able to find any such placement.
•  » » 7 weeks ago, # ^ |   +3 Check This submission. Second cube from 0->14 and first from 0->7. and the test cases doesn't fail.
 » 6 weeks ago, # |   0 йеша
 » 6 weeks ago, # |   0 for 1st problem: WRONG ANSWERi submitted this code package mainimport "fmt"func main(){ var a, b int fmt.Scan(&a, &b) if a+b == 0 { fmt.Println((a+b) + 1) } else if a+b <= 9 { fmt.Println((a+b) — (b + 1)) } }logically its correct but don't what are 2 test cases my test case failsplease can someone see and review it.