### azberjibiou's blog

By azberjibiou, history, 7 weeks ago,

Hello Codeforces and welcome back to another div2 round.

YeongTree and I are excited to invite everyone to participate in Codeforces Round 851 (Div. 2), which will be held on Feb/09/2023 17:35 (Moscow time).

This round is rated for the participants with ratings strictly lower than 2100. You will be given 6 problems and 2 hours to solve them. All the problems are authored and prepared by YeongTree and me.

We would like to thank

The score distributions will be updated later.

UPD1: Score distribution: $500−1000-1500-2250−2500-3000$

UPD2: Congratulations to the winners!

Overall:

Rated participants

AC submissions at the last second

UPD3: Editorial is out

• +491

 » 7 weeks ago, # |   +10 Auto comment: topic has been updated by azberjibiou (previous revision, new revision, compare).
 » 7 weeks ago, # |   +13 Auto comment: topic has been updated by azberjibiou (previous revision, new revision, compare).
 » 7 weeks ago, # |   0 Looking forward to solve 2-3 problems. Positive delta to all!
 » 7 weeks ago, # | ← Rev. 3 →   -40 Waiting For This Round.
 » 7 weeks ago, # |   -39 as a tester, mister ORZZZZ
 » 7 weeks ago, # |   +31 As a tester, the problems were really good.Participants, please enjoy the contest!
•  » » 7 weeks ago, # ^ |   +15 Similar names (⁠ᗒ⁠ᗩ⁠ᗕ⁠)
•  » » 7 weeks ago, # ^ |   +5 thanks aftors
•  » » 7 weeks ago, # ^ |   -22 Problem C is trash. Change my mind...
•  » » » 7 weeks ago, # ^ |   0 The problem with number C is that it's not called "trash", it's called "high quality".
•  » » » » 6 weeks ago, # ^ |   0 Yeah right, it's the best problem ever made. What would Codeforces become if every problem was of this type... SpoilerHell
 » 7 weeks ago, # |   +45 As a tester, I enjoyed the round and the statements were brief and clear. I hope to see you on the scoreboard!
•  » » 7 weeks ago, # ^ |   -24 What're you talking about? Problem C is complete piece of sh*t.
 » 7 weeks ago, # |   -30 As a tester, this was the best contest I have ever seen.
•  » » 7 weeks ago, # ^ |   -31 as a tester, this was the best contest I have ever seen.
•  » » » 7 weeks ago, # ^ |   +5 As a participant , hoping this would be the best contest of [Contests I have ever seen + this contest]
 » 7 weeks ago, # |   +34 As an apparent tester (I don't remember testing this round recently), I'm sure the problems are good :P
 » 7 weeks ago, # |   0 Good luck to everyone!!!
 » 7 weeks ago, # |   +7 Good Luck for every Candidate Master to promote to Master!
 » 7 weeks ago, # |   0 Best of luck for me
 » 7 weeks ago, # |   +35 OMG South Korean setters, good mathematical problems coming on the way :)
•  » » 7 weeks ago, # ^ |   +13 Hahaha as a tester I cannot say about that now, but good luck if you participate!
•  » » » 7 weeks ago, # ^ |   +4 hahaha haha hahaha haha hahaha haha :(
•  » » 7 weeks ago, # ^ |   +2 Haha nicely predicted.
 » 7 weeks ago, # |   -39 Meme :)...
 » 7 weeks ago, # |   +11 Omg announcement shorter than tourist round
 » 7 weeks ago, # |   0 yes great broo
 » 7 weeks ago, # |   0 This round is going to be amazing! Good luck to all!
 » 7 weeks ago, # |   0 omg early editorial round!
 » 7 weeks ago, # |   0 At the end of the last contest, I submitted the code again, which made my score very low, so I lost the ranking. It's sad, I didn't know this rule before.
 » 7 weeks ago, # |   +8 This contest may be a bit late, I guess I fell asleep at that time.
 » 7 weeks ago, # | ← Rev. 4 →   -19 good luck everyone!
 » 7 weeks ago, # |   +5 As a tester, I tested this round in the period about when I was orange for the first time.Problems are nice tho!
 » 7 weeks ago, # |   -13 Hope we will learn smth)
 » 7 weeks ago, # |   -10 2 days left
 » 7 weeks ago, # |   +26 My first contest was tourist round. I solved 1st 2 problem and earned 389 rating. This will be my 2nd contest .
 » 7 weeks ago, # |   +32 I will skip an academic seminar in my university and participate in this round.
 » 7 weeks ago, # | ← Rev. 2 →   -10 As a participant, I confirm that i will participate.
 » 7 weeks ago, # |   +24 Sometimes I really want to skip school.
 » 7 weeks ago, # |   -85 Please down me, thx.
 » 7 weeks ago, # |   +8 As a tester, I enjoyed this round. Good luck!
 » 7 weeks ago, # |   0 All the best everyone.
 » 7 weeks ago, # | ← Rev. 2 →   0 Thanks for your excitation to invite us to participate in round !
 » 7 weeks ago, # |   +8 Auto comment: topic has been updated by azberjibiou (previous revision, new revision, compare).
 » 7 weeks ago, # |   +6 Good Luck and Have Fun!
 » 7 weeks ago, # |   0 I will skip an academic seminar in my university and participate in this round
 » 7 weeks ago, # |   0 As a grey, already hit the bottom. Hoping to move to green
 » 7 weeks ago, # |   -18 yeah, i guess it will be unrated round :)
 » 7 weeks ago, # |   0 Seems like a huge difficulty gap between C and D.
 » 7 weeks ago, # |   +5 Wishing you all a positive delta!!
 » 7 weeks ago, # |   +3 Best wishes for everyone
 » 7 weeks ago, # |   0 why I am unable to register for the Div 2 contests?
 » 7 weeks ago, # | ← Rev. 2 →   -26 .
 » 7 weeks ago, # |   -55 Worst Contest I have Ever Seen. What are these strict time limits !?!?
•  » » 7 weeks ago, # ^ |   -15 I do agree
 » 7 weeks ago, # |   +37 Me after solving C Waiting for contest to end
•  » » 7 weeks ago, # ^ |   +1 Same lol
•  » » 7 weeks ago, # ^ |   0 Can you please tell your approach on C?
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 I was given some pattern in this comment you can see it. I hope it will help you
•  » » » » 7 weeks ago, # ^ |   0 Or something like this :) Pattern examplen = 9 1 14 2 15 3 16 4 17 5 18 6 10 7 11 8 12 9 13 
•  » » » 7 weeks ago, # ^ |   +4 Approach for C; Let sum of all the numbers [ 1 to 2n ] : S_2n = ((2n)*(2n+1))/2; After the construction of pairs, we will get [n] consecutive numbers let's say the minimum sum of any pair be x; Now, the sum of these [n] consecutive numbers, S_x = (x) + (x + 1) + ... + (x + (n-1)) S_x = n*x + (n*(n+1))/2 = S_2n [ just the sum of all numbers ] After solving the equation minimum sum possible => x = (3n + 3)/2; Then just try to construct pairs with sum x, x+1, x+2, ..., x+n-1. Hope this helps.
•  » » » » 6 weeks ago, # ^ |   0 Problem C. Using the formula for the sum of an arithmetic progression, we found that the sum of the first pair is (3n+3)/2. Now how do we restore all pairs? Thank you.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0
•  » » 7 weeks ago, # ^ |   0 same
 » 7 weeks ago, # |   0 Best problem set. Just awesome!!! No doubt the author is a genius. It is the best problem set I have ever experienced in my coding journey.
 » 7 weeks ago, # |   +19 is that a pattern finding round?
 » 7 weeks ago, # |   +1 MoStarting with problems A Motivation 100 to 50 B Motivation 50 to -100 C Motivation -100 to +50 Depression enters :)
 » 7 weeks ago, # | ← Rev. 2 →   0 How to solve E? Is this some dp? maybe we can precompute the maximum index, i can jump to from index j while keeping the sum of elements from i to j >= 0 . Am i thinking in the right direction ?
•  » » 7 weeks ago, # ^ |   0 The contest isn't over yet.
•  » » 7 weeks ago, # ^ |   +4 no you need to solve A+B first
•  » » 7 weeks ago, # ^ |   0 I thought of doing a segment dp like:dp[L][R][0] — ans for [L; R]dp[L][R][1] — ans for (L;R]dp[L][R][2] — ans for [L;R)dp[L][R][3] — ans for (L; R)But had some troubles with calculating dp[L][R][0]. Other states are easy to calculate
•  » » 7 weeks ago, # ^ |   +3 SpoilerDP on segment tree with coordinate compression on prefix sums. Iterate from 0 to n-1, then answer for $[a_0, a_1 .. a_i] = max(DP_{minprefixsum}....DP_{prefixsum_i}) + i$. Then update $DP_{prefixsum_i}$ to $currentanswer - i$ if $DP_{prefixsum_i}$ is not better than the current answer.
 » 7 weeks ago, # |   +48 Might be an unpopular opinion, but I think all problems were very good and interesting. Congrats to the authors for a beautiful contest. I enjoyed doing the contest very much. Thanks!
•  » » 7 weeks ago, # ^ |   -18 Problem C was good and interesting? You have no taste, Bro
 » 7 weeks ago, # |   0 Did someone constantly get wrong answers on problem B?
•  » » 7 weeks ago, # ^ |   0 Me and Me... Also got TLE Btw, how to solve B? please help somebody...
•  » » » 7 weeks ago, # ^ |   0 me too TLE :/
•  » » » 7 weeks ago, # ^ |   0 The magic of Binary Search.
•  » » » » 6 weeks ago, # ^ |   0 can you share your approcah
•  » » 7 weeks ago, # ^ |   +1 it's me, huh! My final ratings will be negative. But next contest, i will gonna hit harder..
•  » » 7 weeks ago, # ^ |   0 me ;(
•  » » 7 weeks ago, # ^ |   +1 You probably converted the number to string and left a leading zero on during the output (not converting it back to int). It would fail for 101, where you would output 01 and 100. Just my guess. You would have to delete all the leading zeroes instead of just the first one
• »
»
7 weeks ago, # ^ |
0

# include <bits/stdc++.h>

using namespace std;

int main(){ long long t; cin >> t; while(t--){ string str; cin >> str; int y = stoi(str); if(y%2==0){ cout << y/2 << " " << y/2 << endl; } else{

string a, b;
int cnt = 0;
for(int i=0; i<str.size(); i++){
if((str[i]-'0')%2==0){
a =  to_string((int(str[i]-'0')) / 2) + a;
b = to_string((int(str[i]-'0'))/2)+b;
}
else{
cnt++;
if(cnt%2==0){
a = to_string(int(str[i]-'0') / 2)+ a;
b =to_string((int(str[i]-'0'))/2 + 1)+b;
}
else{
a =to_string( (int(str[i]-'0'))/2 + 1)+a;
b =to_string((int(str[i]-'0'))/2)+b;
}
}

}
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int q = stoi(a), w=stoi(b);
cout << q << " " << w << endl;


} } }

 » 7 weeks ago, # |   +8 How to solve C?
•  » » 7 weeks ago, # ^ |   0 see these patterns i hope this will help you if n=6 1 12=13 2 10=12 3 8=11 4 11=15 5 9=14 6 7=13 so the ans is no. if n=5 1 10=11 2 8=10 3 6=9 4 9=13 5 7=12 so the ans is yes 
 » 7 weeks ago, # | ← Rev. 2 →   -27 ABCforces
 » 7 weeks ago, # |   0 How to solve B?
•  » » 7 weeks ago, # ^ |   0 Distribute digit by digit.
•  » » 7 weeks ago, # ^ |   0 Divide n into 2 numbers evenly. One number may be 1 greater than the other. Compare the 2 numbers digit by digit. The digits are either (1) same, (2) 1 vs 0, or (3) 0 vs 9. Keep track of the sum of digits of the 2 numbers so far. In case 3 above, distribute the 9 as 4 and 5 or 5 and 4 depending on the current difference of the sums of digits so far.
•  » » 7 weeks ago, # ^ |   0 If n is even answer is n/2 n/2 else traverse n digit by digit and make answer
•  » » 7 weeks ago, # ^ |   0 if the number is even then n/2,n/2 is the ans. if its odd then n/2,n/2+1; edge cases 1999,3999,599999 etc we can distribute it like eg for 3999 1545 2454
 » 7 weeks ago, # |   0 hi, I am new, are there any editorials or discussions section here? I am kind of lost
 » 7 weeks ago, # | ← Rev. 3 →   +10 E looks standard. Can it be solved by dp with d&c?upd: i think i overcomplicated it
•  » » 7 weeks ago, # ^ |   +5 dp[i] = max(dp[i — 1], dp[j] — j + i) while sum(j + 1 ... i) >= 0 (j < i) using map to keep (sum[i], dp[i] — i) increase.
 » 7 weeks ago, # |   +46 C is too hard
•  » » 7 weeks ago, # ^ |   -8 C is just bad, like B, just intuition is needed...
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 B is common observation that each digit is independent. i meesed up B I tried to split horizontally. I don't know about C. I should have taken help from chatgpt. it would have done it may be one second or may be less
•  » » 7 weeks ago, # ^ |   0 even though huge no of submissions
 » 7 weeks ago, # |   0 The time limit is quite strict I think :(
 » 7 weeks ago, # |   +26 The difference between C and D was massive.
 » 7 weeks ago, # |   0 did anyone else also got wrong answer on test 5 in E
•  » » 7 weeks ago, # ^ |   +1 yeah me
•  » » » 7 weeks ago, # ^ |   0 What was your approach.
•  » » » » 7 weeks ago, # ^ |   0 I used binary search on previous minimas of sum<=sum[i] if sum[i]<0 for getting subsegment with maximum length ending at i.
•  » » 7 weeks ago, # ^ |   0 Yes, i did the classic dp like LIS but get WA on test 5 don't know why
•  » » » 7 weeks ago, # ^ |   0 I know now i forgot about dp[i] = max(dp[i], dp[i — 1])
•  » » » » 7 weeks ago, # ^ |   0 Hello i am also doing same mistake in other method but not getting ig as i am getting same 126 as answer in test case 5. It will be a great favour if you please look into it
•  » » » » » 6 weeks ago, # ^ |   0 Take a look at Ticket 16726 from CF Stress for a counter example.
 » 7 weeks ago, # |   +10 I think that this round had very interesting problems with pretty beautiful possible solutions. Thanks for the contest!
 » 7 weeks ago, # |   +14 My solution to problem E:First, create the prefix sum array $p_0 = 0, p_i = a_i + p_{i-1}$ and compress it. Let $dp_i$ denote the best answer for the prefix upto element $i$. Suppose the last segment we take containing $i$ goes upto $\ell+1$ and misses $\ell$. Then $\ell < i$ and we must have $p_i \geq p_{\ell}$, and the best possible answer in this case would be $dp_{\ell-1} + (i - \ell)$. To efficiently compute these values, create a max segment tree over the compressed $p_i$ values and each time we compute $dp_i$ as $i$ plus the maximum over the segment $[0, p_{i}]$ in the segment tree and after performing $dp_i = \max(dp_i, dp_{i-1})$ (in case we don't take $i$ in the optimum answer) we update the $p_{i+1}$th location by maximising it with $dp_{i} - (i+1)$. That's it, done. Overall solution works in $\mathcal O(n \log n)$.
 » 7 weeks ago, # |   0 can anyone give idea to solve C please
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 I was given some pattern in this comment you can see that
•  » » 7 weeks ago, # ^ |   0
 » 7 weeks ago, # |   +20 https://www.youtube.com/watch?v=1jbhevleu-Y Copy of Problem B...Do Something
 » 7 weeks ago, # |   0 ABCforces
•  » » 7 weeks ago, # ^ |   +3 how to solve C
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   -9 assume consecutive sum of n pairs is : k, k + 1, k + 2, ..., k + n — 1. If u add everything u have k*n + (n — 1)*n / 2. Which should be equal to 2n * (2n + 1) / 2 (sum of 1, 2, ..., 2*n). Equate both terms and you will get k = (3n + 3) / 2. Now figure out the pairing part by yourself, it's not that hard.
•  » » » » 7 weeks ago, # ^ |   0 Asks for a solution, gets "figure out xyz by yourself, it is not that hard".
•  » » » » » 7 weeks ago, # ^ |   0 Hint: If you cannot figure out the pattern, try to write a brute force solution for small cases.
•  » » » » 7 weeks ago, # ^ |   +5 haha, I did until this step, it's intuitive. I couldn't figure out the pairing part.
•  » » » » » 7 weeks ago, # ^ |   0 if the value of k is a integer, then how can we gurantee that a pair always exists?
•  » » » 7 weeks ago, # ^ |   +7 I brute forced for n=7 and the find the answer (4,8) (5,9) (6,10) (7,11) (1,12) (2,13) (3,14) then we are done.
•  » » » » 7 weeks ago, # ^ |   0 hello sir, I am unsure of how to write a brute force algorithm for this question. Do you think you could help me? Thanks.
 » 7 weeks ago, # |   -8 my total score : 390-8*50.. It looks very difficult, was this contest really hard?
•  » » 7 weeks ago, # ^ |   +3 It's normal for a new account to solve only the first (or even zero) problem is the first contest. You just need to take more contests to get familar with the process of CF contests.
 » 7 weeks ago, # | ← Rev. 13 →   +8 Problem D cost much time for me and I didn't have enough time for E.2D dynamic programming with 6 different arrays to maintain (RL, RL_sum, LL, LL_sum, LL_cnt, LL_cnt_sum) is too easy to make mistake at some details. I've spent much time to find a bug that I allocated too much space on the stack for 2D arrays (using something like ll RL[n][n], where n=3000) instead of declare them as global variables. How to solve Ddefine 6 2D arrays for DP:RL[j][k]: The answer consider the cases that the rightmost 2 dots are j, k, and j moves to right (when there are only 2 dots, or the i-th dot is on the left of j, and dist(i,j)<=dist(j,k), which is equivalent to, x[i]>=2*x[j]-x[k]).LL[j][k]: The answer consider the cases that the rightmost 2 dots are j, k, and j moves to left (when there are more than 2 dots, and the i-th dot is on the left of j, and dist(i,j)>dist(j,k), which is equivalent to, x[i]<2*x[j]-x[k]).LL_cnt[j][k]: The number of sets which containing more than 2 dots, and the rightmost 2 dots are j, k, and j moves to left.XX_sum[j][k]: sum(i=0...j)XX[j][k].Then for each pair of (j, k) where j=2*x[j]-x[k] (if there's no such i0 then i0=j),then the DP formula is:LL[j][k]=sum(i=i0...j-1)(RL[i][j]+LL[i][j])RL[j][k]=1+sum(i=0...i0-1)(RL[i][j]+LL[i][j]+LL_cnt[i][j])LL_cnt[j][k]=2^i0*(2^(j-i0)-1)The final answer is sum(i=0...n-1, j=i+1...n-1)(RL[i][j]+LL[i][j]). My approach for E (Now it has been accepted)Dynamic programming, where the formula is $dp[i]=max(dp[i-1],\mathop{max} \limits_{0 \le j \le i, sum[i] \ge sum[j-1]}(dp[j-1]+i-j+1))$, which is equivalent to $dp[i]=max(dp[i-1], i+ \mathop{max} \limits_{0 \le j \le i, sum[j-1] \le sum[i]}(dp[j-1]-(j-1)))$ $dp[i]=max(dp[i-1], i+ \mathop{max} \limits_{0 \le j \le i-1, sum[j] \le sum[i]}(dp[j]-j))$$1$where $sum[j]$ is the prefix sum of $a$. Then we can solve the problem by segment tree (since $sum[j]$ can be large, we need to sort $sum[j]$ first, and give them a new identifier from $0$ to $n-1$).Update: Now my submission 192969220 has been accepted. AC code of E#include using namespace std; char nl = '\n'; char sp = ' '; using ll = long long; using vb = vector; using vi = vector; using vl = vector; using vvb = vector; using vvi = vector; using vvl = vector; using si = unordered_set; using sl = unordered_set; using tsi = set; using tsl = set; using pii = pair; using pll = pair; using vpii = vector; using vpll = vector; using tmii = map; using tmll = map; using mii = unordered_map; using mll = unordered_map; using pqi = priority_queue; using pqig = priority_queue>; using pql = priority_queue; using pqlg = priority_queue>; using pqpii = priority_queue; using pqpll = priority_queue; #define tp3(T) tuple #define tp4(T) tuple #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define outrange(x,min,max) ((x)<(min) || (x)>(max)) #define nano (chrono::system_clock::now().time_since_epoch().count()) #define second_since_start ((nano-start)/1e9) #define init_rng mt19937 rng(nano) #define randint(a,b) ((a)+rng()%((b)-(a)+1)) void yesno(bool a) { cout << (a ? "YES\n" : "NO\n"); } template ostream& operator<<(ostream& out, const pair& p) { out << '(' << p.first << ',' << p.second << ')'; return out; } template ostream& operator<<(ostream& out, vector& v) { for (auto &i : v) out << i << ' '; out << nl; return out; } template ostream& operator<<(ostream& out, set& v) { for (auto &i : v) out << i << ' '; out << nl; return out; } template ostream& operator<<(ostream& out, unordered_set& v) { for (auto &i : v) out << i << ' '; out << nl; return out; } template ostream& operator<<(ostream& out, map& m) { out << '['; for (auto &[k, v] : m) { out << k << ':' << v << sp; } out << "]\n"; return out; } template ostream& operator<<(ostream& out, unordered_map& m) { out << '['; for (auto &[k, v] : m) { out << k << ':' << v << sp; } out << "]\n"; return out; } namespace segtree_single_point{ #define sti segtree #define stl segtree template T lambda_add(T x,T y){ return x+y; } template T lambda_min(T x,T y){ return x T lambda_max(T x,T y){ return x>y?x:y; } template class segtree{ public: segtree(vector &source, T (*merger)(T,T), T defaultValue=(T)0){ this->merger=merger; this->defaultValue=defaultValue; int n=source.size(); int L=1; while(L v(2*L,defaultValue); data=v; for(int i=0;i=1;i--) data[i]=merge(data[2*i],data[2*i+1]); } void add(int index,T value){ put(index,data[size+index]+value); } void put(int index,T value){ _put(size+index,value); } //查询闭区间[l,r] T query(int l,int r){ return _query(0,size,l,r+1); } void show(){ cout< data; T (*merger) (T,T); int size; T defaultValue; T merge(T left,T right){ return (*merger)(left,right); } void _put(int i,T value){ data[i]=value; if(i==1) return; int j=i^1; if(i>j) swap(i,j); _put(i>>1,merge(data[i],data[j])); } T _query(int L,int R,int l,int r){ if(L>=r || R<=l) return defaultValue; int index=(size+L)/(R-L); if(index>=size) { return data[index]; } if(L>=l && R<=r) { return data[index]; } int mid=(L+R)>>1; T ans=defaultValue; if(r>L) ans=merge(ans,_query(L,mid,l,r)); if(l>_t; while(_t--){ int n; cin>>n; for(int i=0;i>a[i]; } sum[0]=a[0]; for(int i=1;i0 && sums[i-1]==sums[i]) continue; inv[sums[i]]=i; } vi v(n); for(int i=0;i=0)?1:0; st.put(inv[sum[0]],dp[0]); for(int i=1;i=0){ dp[i]=i+1; }else{ dp[i]=max(dp[i-1],i+st.query(0,index)); } st.put(index,max(st.query(index,index),dp[i]-i)); } cout<
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   +7 Observe that the answer is equal to the number of adjacent points which moves toward each other.We may check every two points $x_l,x_r$ and count the number of subsets in which $x_l$ and $x_r$ are adjacent and move toward each other, which is equal to $2$ to the power of $(L_{l,r}+R_{l,r})$, where:$L_{l,r}$ represents the number of points satisfying $x_r-x_l •  » » » 7 weeks ago, # ^ | ← Rev. 2 → 0 [deleted] •  » » » 7 weeks ago, # ^ | +1 Why are you not considering point which can possibly lie in between xl & xr in the subset? For ex: If x[]={1,13,14,20} and if l=1 & r=4, then by your soln ans would be 1 ({1,20} would be the only such subset), however there could be one more subset ({1,13,14,20}) as well, here also 1 and 20 would meet each other. •  » » » » 7 weeks ago, # ^ | ← Rev. 2 → +1 for {1,13,14,20}, although 1 and 20 meet each other, they end up in the same place as 13 and 14's. So it is calculated when l=2 and r=3. •  » » » » » 7 weeks ago, # ^ | 0 Ok, so when two particles collide, they just stop there. I thought that the colliding ones just disappear! •  » » » » 7 weeks ago, # ^ | 0 It's the sum over all$(l,r)$such that$x_l$and$x_r$meet each other and are adjacent. •  » » » 7 weeks ago, # ^ | +9 Same approach. It is a miracle that this came to my mind during the time of contest. Finally i can see some improvement.Thanks to this contest i reached specialist rating. •  » » 7 weeks ago, # ^ | +1 I didnt use DP. I just iterated over every pair$(i,j)$and found the number of subsets of points such that$i$and$j$meet each other. The idea and code are both simple. Code for D#include #include #include #include using namespace atcoder; using namespace __gnu_pbds; using namespace std; using mint = modint1000000007; template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; #define endl '\n' typedef vector vi; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; vi vec(N); for (int &i : vec) cin >> i; ordered_set s; for (int i : vec) s.insert(i); mint ans = 0; mint two = 2; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { int d = vec[j] - vec[i]; int t1 = s.order_of_key(vec[i] - d); int t2 = N - s.order_of_key(vec[j] + d); ans += two.pow(t1 + t2); } } cout << ans.val() << endl; return 0; }  •  » » » 7 weeks ago, # ^ | ← Rev. 2 → +1 Excellent solution. Comparing to yours, my solution can even be regarded as wrong answer. •  » » » 7 weeks ago, # ^ | +4 I see that you've used this header file #include Is it supported in codeforces? •  » » » » 7 weeks ago, # ^ | ← Rev. 2 → +2 No, it is only available in Atcoder, not in codeforces. My actual submission looks like thisBut the AtCoder Library GitHub repo provides a python script that takes a C++ file and replaces the atcoder header file with the atcoder library, enabling it to submit to all platforms. I also use the VSCode extension called CodePal which automates this process. •  » » » » » 7 weeks ago, # ^ | 0 Thank you. I'll take a look •  » » 7 weeks ago, # ^ | ← Rev. 2 → 0 Can you please explain your dp approach for D . I tried doing this by dp but failed and my obervation skills suck , hence wasnt able to do the question the other way too. •  » » » 7 weeks ago, # ^ | ← Rev. 2 → 0 We consider what would happen if we add a new dot at right. We call the previous 2 right-most dots i, j (assume there's >=3 dots in the set, because set with only 2 dots is trivial). In the previous set j would move left since it's right-most dot, and i could move left or right. If j still move left after we add a new dot, the number of final points will not increase. But if j move right, there's 2 situations: if i moves left (we call this situation LL), then it would like RR...LL --> RR...LRL, we can see there's one more final point (by the "RL" we've created), and if i moves right (we call this situation RL), then it would like RL --> RRL, where number of final points remained same. Therefore we can get the transition formula. (don't forget to consider situations of RL when there's only 2 dots in the set)Also this DP approach need to store prefix sums for optimization. See this comment for a simpler solution.  » 7 weeks ago, # | 0 Was D just a DP on pos[previous][current] then looping through [current+1, n) to try placing the next particle?The observation there I believe is that for all values <= a[i] + (a[i] — a[p]), the direction is left, while the rest are right, so you can do some casework there to add on that subarray after precomputing prefix sums (the number of dots is equal to the number of adjacent RL's that show up in the final subsequence), but I had a stroke implementing ;-; does anybody have a simple enough implementation of that idea? •  » » 7 weeks ago, # ^ | 0 Wouldn't this be$n^3$? Each of your$O(n^2)$values take some$O(n)$time unless there is a trick I am missing. •  » » » 7 weeks ago, # ^ | ← Rev. 5 → 0 I couldn't even get the n^3 working cuz I'm bad but I think that the recurrence would look like for j in range(i+1, n): if (P is closer to I than J): // place an L in this case DP += solve(i, j) //(if previous was R, then add 1, otherwise don't add) else: // place an R in this case DP += solve(i, j) (never add in this case) Then since every single transition is just solve(i, j) + (a bool) in either case, then you split it up into the ranges whether the bool is true or false with bsearch. The second range never gets added to, and the first range you would casework and then multiply by the length of that range.So in the end the transition is DP += (sum of everything from DP(i, [j+1, n) )) + (len of good range) * (caseworked boolean)(though again I didn't get the casework working so I'll still need to work out the conditions)Though it seems like other people had easier solutions ;-; •  » » 7 weeks ago, # ^ | 0 had a similar observation but could not come up with the implementation ;( •  » » 7 weeks ago, # ^ | 0 I have a simpler approach, iterate over i,j (i •  » » 7 weeks ago, # ^ | 0 Let's assign directions to the dots in some subset, they will look like:(RR...RRLL...LL)|(RR...RRLL...LL)|......|(RR...RRLL...LL)So the number of distinct endpoints is the number of "LR" adjacent pairs + 1 (to account for the first block). So we can iterate on every pair$(i,j)$and count in how many subsets they can exist as an adjacent LR pair.Based on$x[j]-x[i]$, we can know how many dots before$i$can be directly before$i$in a subset and how many dots after$j$can be directly after$j$in a subset. If$[l, i-1]$is the left range and$[j+1, r]$is the right range, then the left subset counts can be$2^{l-1}$,$2^l$, ...,$2^{i-2}$, and the right subset counts can be$2^{n-r}$,$2^{n-r+1}$, ...,$2^{n-j-1}$.So, add$(2^{l-1}+2^l+...+2^{i-2})\cdot (2^{n-r}+2^{n-r+1}+...+2^{n-j-1})$to$ans$. Make sure to initiate$ans$with$2^n-n-1$to account for the first block in all the subsets.Submission  » 7 weeks ago, # | -7 B was much more difficult than C In B only case we need to worry about is n%20==19 but even after that it was more of implementation problem than maths which it seemed to be initially •  » » 7 weeks ago, # ^ | 0 you can solve B with binary search •  » » » 7 weeks ago, # ^ | 0 Could you tell how please? •  » » » » 7 weeks ago, # ^ | 0 check my submission •  » » » » 7 weeks ago, # ^ | ← Rev. 2 → 0 codeint get(int i){ int sum = 0; while(i > 0){ sum+=i%10; i/=10; } return sum; } void solve() { int n; cin >> n; int l = 0,r = n; while(l <= r){ int m = (l+r)/2; if(abs(get(m)-get(n-m))<=1){ cout << m << " " << n-m << "\n"; return; } if(get(m) > get(n-m)){ r = m - 1; } else { l = m + 1; } } }  •  » » » 7 weeks ago, # ^ | 0 Not required •  » » 7 weeks ago, # ^ | 0 if n%20==19 what should you do next? •  » » 7 weeks ago, # ^ | ← Rev. 2 → 0 Since the guy with more elo literally posted the same answer as mine and my comment is being ignored because of it, I might as well just remove it. •  » » » 6 weeks ago, # ^ | 0 you're too sensitive for these things •  » » » » 6 weeks ago, # ^ | 0 Yes I am, because it's happened before. Good thing it was a 5 minutes comment and not a full editorial. •  » » 7 weeks ago, # ^ | +15$B$can be implemented simpler. Iterate over digits. If digit is even, split it equally for both answers. If digit$x$is odd, add$x / 2$to first answer,$x / 2 + 1$to second answer and then swap them.At the end remove leading zeros.Example: 16934 -> 1**** + 0**** -> 13*** + 03*** -> 035** + 134** -> 1342* + 0351* -> 13422 + 03512  » 7 weeks ago, # | 0 Feels like massive cheating on C, I might be wrong but it feels like it. •  » » 7 weeks ago, # ^ | 0 C is super easy to guess •  » » 7 weeks ago, # ^ | +9 Cheating is happening too much nowadays.. •  » » 7 weeks ago, # ^ | 0 i guess it is for both B and C, B was much harder than c •  » » » 7 weeks ago, # ^ | 0 how to solve C > •  » » » » 7 weeks ago, # ^ | 0 •  » » » 7 weeks ago, # ^ | 0 In what universe is B harder than C, only if you cheated cause code might be more trivial for C. To figure out idea for B it takes less than 50 seconds. •  » » » » 7 weeks ago, # ^ | 0 yes you maybe right but i am just saying what I felt was observation for C was easier to pick than Bfor C if n=5 then1,10 = 11 -1 2,7 = 9 -2 3,9 = 12 -3 4,6 = 10 -4 5,8 = 13 -5if we see 1,10=11 next big numbers can be 12,13 since in -2, 3-1=2 and 9+1=10 we compensated for that 1 similarly this can be seen for other casesbut if n%2==0 there will always be a pair such that its sum is repeated in other pair •  » » 7 weeks ago, # ^ | 0 I am also feeling this •  » » 7 weeks ago, # ^ | ← Rev. 2 → 0 I think , There were not much difference between level of B and C . SpoilerB was an implementation and C was Observation + Implementation.  » 7 weeks ago, # | 0 What is test 2 for B? •  » » 7 weeks ago, # ^ | 0 maybe 1999 3999 59999 ....etc any such •  » » 7 weeks ago, # ^ | 0 i think it could be 100,1000,10000 etc •  » » » 7 weeks ago, # ^ | 0 i think its easy to guess for these nos n/2,n/2=> {50,50},{500,500}.... •  » » » » 7 weeks ago, # ^ | 0 different emplementation  » 7 weeks ago, # | +3 guessforces •  » » 7 weeks ago, # ^ | 0 more like observation forces  » 7 weeks ago, # | 0 Kinda solved problem C by guessing. You can calculate the first number in the sequence s through math. Iterate over all possible odd numbers first, then iterate over all possible even numbers. This apparently works, but I would be interested in a proof.  » 7 weeks ago, # | 0 Any proof for C I solved it by just some observations •  » » 7 weeks ago, # ^ | ← Rev. 2 → 0 if n is even then "NO". else sum of first pair should be (3*(n+1)/2). proof: S1 + (S1+1) + (S1+2) + ....... + (s1+n-1) = 2n*(2n+1)/2  » 7 weeks ago, # | -19 The worst round •  » » 7 weeks ago, # ^ | +9 I also wanna say this... but to be honest the problems are fine and I'm just unlucky. •  » » 7 weeks ago, # ^ | +1 For me too :( •  » » 7 weeks ago, # ^ | 0 why? D was alright but maybe D > E. I guess A,B were easier than usual for sure.  » 7 weeks ago, # | ← Rev. 4 → -13 Imagine asking how to solve D and getting -13 ^D  » 7 weeks ago, # | ← Rev. 2 → +1 It was great PatternForces Round <3  » 7 weeks ago, # | ← Rev. 2 → 0 I wish C was 1500-1600, but unfortunately it's more likely to be 1200  » 7 weeks ago, # | 0 How to solve B? please somebody help. •  » » 7 weeks ago, # ^ | ← Rev. 2 → 0 Hint 1Think in term of digits Hint 2Can we divide each digit by 2 and then assign in the two numbers. SolutionLet a and b be empty arrays , from which we form number a1 and b1 later.Traverse from the least significant digit ,Divide each digit by 2 ,now two cases arise : Case1: Digit is even, Then simply push digit/2 in a and b.Case2: Digit is odd ,As We have to maintain the sum of digits of a and b equal to 0 or 1 ,so if there are multiple odd digits then we have to maintain a flag such that we can push (digit+1)/2 and (digit)/2 alternatively in number a and b.for eg .n= 134we traverse the number in the way 431 :initially a={ } b={ } FOR digit 4 , a={2} b={2} 4/2=2 (case of even digit)For digit 3 , a={2,2} b={2,1} as (3+1)/2=2 and (3/2)=1 (case of odd digit).for digit 1 a={2,2,0} b={2,1,1} as we have already push for an odd number in a then this time we will push (digit+1)/2 in b.So final number formed from a is a1=220 and from b is b1= 211 (i am assuming you may know how to form a number from given digits.)mycode . Note : this is one of the approach ,there can be multiple optimized approaches.apologize for my shit English.  » 7 weeks ago, # | ← Rev. 4 → 0 Anyone know why my sol for D is wrong?dp[i] stands for sum where i is chosen, and tot[i] is total of chosen & not chosen dp[0] = 1; tot[0] = 1; for (int i = 1; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (j == 0) { dp[i] = (dp[i] + 1) % mod; } else if (x[i] - x[j] < x[j] - x[j - 1]) { dp[i] = ((dp[i] + tot[j - 1]) % mod + mod_pow(2LL, j + 0LL, mod)) % mod; } else { dp[i] = ((dp[i] + dp[j]) % mod + mod_pow(2LL, j + 0LL, mod)) % mod; } } tot[i] = (tot[i - 1] + dp[i]) % mod; } cout << (tot[n - 1] - n + mod) % mod << '\n';   » 7 weeks ago, # | 0 anyone tried to divide horizontally for problem B ?  » 7 weeks ago, # | 0 Woohoo, my best ever contest :)  » 7 weeks ago, # | 0 After a very long time i was able to solve only one question. Best contest of my lyf (T_T)  » 7 weeks ago, # | +1 I wast stuck in problem C for approximately 2 hours, In problem C multiple kind of pairing was possible so it must be mentioned in the question that we can output any valid answer. I am not talking about order of pairs... actually you can pair any number with 2 values and accordingly I found 2 valid answer exists for each odd number.  » 7 weeks ago, # | 0 Always two problems.Can someone tell me how to train to solve problem C? •  » » 7 weeks ago, # ^ | ← Rev. 3 → 0 the idea is that we find the sum of 1 and 2n and store it, for example, in set(). it is clear that now we will not be able to take the sum of 2 and 2n-1, so we will make a "shift on the right" and take 2 and 2n-2 and mirror the "shift on the left" by taking the sum of 3 and 2n-1. then we need to apply this algorithm to the end, increasing each time the "shifts on the left and right" by 1 (that is, the next two sums are (4 and 2n-5 ) and (6 and 2n-4). it is not difficult to make sure that for even n the answer will always be "No", and for odd n it is possible to split the permutation into pairs using this algorithm (but not for all odd n there is a solution, for example, for n=11 there is no solution) upd: it remains only to be able to carefully remove pairs from the permutation :) •  » » » 7 weeks ago, # ^ | 0 Thank you:). I know it is impossible for even but i spent 50 min to think how to construct the pair . •  » » » » 7 weeks ago, # ^ | 0 Not at all! Good luck with C :)  » 7 weeks ago, # | ← Rev. 2 → 0 I just would like to say that I didn't fully understand the problem A, could someone please explain it more or provide me more test cases with explanition?I feel that this round's first problem is a little harder than before.Thanks in advance. •  » » 7 weeks ago, # ^ | 0 To think what is useful for multiply  » 7 weeks ago, # | 0 Any Hints For D? I Was Thinking In A DP Direction :( •  » » 7 weeks ago, # ^ | 0 the main observation is that the distinct points increase when$ith$index moves left and$i+1th$index moves right. Now try to figure out the contribution of each$i$seperately by fixing the position that moves left and the position that moves right.  » 7 weeks ago, # | -6 great contest. for the first time there is no feeling that after B I can't solve anything. this time there was such a feeling only after task C!  » 7 weeks ago, # | +9 Toooooooooooooo much Cheating •  » » 7 weeks ago, # ^ | 0 Why do you think so? •  » » 7 weeks ago, # ^ | 0 I haighly agree.  » 7 weeks ago, # | 0 Hello  » 7 weeks ago, # | 0 Can anyone explain E for noobs?  » 7 weeks ago, # | +3 Why is answer no for even n in C? •  » » 7 weeks ago, # ^ | +3 s, s + 1, ..., s + (n — 1) are sums. So s * n + n * (n — 1) / 2 = 2n * (2n — 1) / 2, so s = (3n + 3) / 2 => n % 2 == 1 •  » » » 7 weeks ago, # ^ | +3 Looks like I need to get some sleep. Thanks tho •  » » 7 weeks ago, # ^ | +2 s, s + 1, -- s + n — 1suppose they are sum of pairs as given in problemif we puts + s + 1 + s + 2 — = 1 + 2 -- 2nwe getn * s + n * (n — 1) / 2 = n * (2n + 1) we gets + (n — 1) / 2 = 2n + 1s = 3 / 2 * (n + 1)for s to be integer n + 1 should be even •  » » 7 weeks ago, # ^ | 0 you can calculate the first sum is (3*n+3)/2 if it is a int ,it is impossible for even •  » » 7 weeks ago, # ^ | -8 see this patterns if n=6, then 1 12=13 2 10=12 3 8=11 4 11=15 5 9=14 6 7=13 two of them are the same but we need distinct integers after pairing all of them if n=8, then 1 16=17 2 14=16 3 12=15 4 10=14 5 15=20 6 13=19 7 11=18 8 9=17 same here 1st and the last values are the same so ans is no   » 7 weeks ago, # | +4 An unbalanced round. I got ABC very quickly, but couldn't come up with a fast enough solution for D in time and didn't attempt further problems. I won't say that the problems were bad because they weren't (C was just guessing a pattern, didn't like it that much; others were good). I just think that there should've been a 1600-1800 rated problem between C and D. But the round was still nice. •  » » 7 weeks ago, # ^ | +3 yea, I agree. Maybe A,B,C could've been made slightly harder to ease up the gradient.  » 7 weeks ago, # | 0 very fast ratings update.  » 7 weeks ago, # | 0 Actually had more trouble with C than F haha.  » 7 weeks ago, # | +3 solved D during the contest, but forgot that modular arithmetic template takes$O(\log n)$to calculate$2^n$... So got TLE couple of minutes before the end after simply rewriting formula I got on paper :(contest submission: https://codeforces.com/contest/1788/submission/192959799upsolve submission: https://codeforces.com/contest/1788/submission/192968394  » 7 weeks ago, # | +3 Great contest with good problems , thanks!  » 7 weeks ago, # | ← Rev. 2 → 0 Empty  » 7 weeks ago, # | 0 Great contest, and super fast rating changes, wow! Absolutely loved all the problems that I read (A-E)!Also, while I understand the need to have tight TLs on D, as$n^3$solutions were to be rejected, I'm slightly irked by the fact that my Java submission failed despite being$n^2log(n)$. Anyway, that was to be expected since I was using TreeMaps, and Binary Search is understandably faster. So yeah, happy to have learned one more thing :)  » 7 weeks ago, # | +4 Great contest with very clear statements!  » 7 weeks ago, # | ← Rev. 3 → 0 ok thanks •  » » 7 weeks ago, # ^ | 0 The product of the array can go up till pow(2,1000) which is way too large to even fit in long long  » 7 weeks ago, # | 0 MakaPakka ranked? yeah very credible lol  » 7 weeks ago, # | ← Rev. 3 → +8 AC submissions at the last second Ac submissions at the last second is very nice , but i am pretty sure that last second submission of problem D by gsmdfaheem is copied. i have seen exact same code that is leaked at just 10 minutes before the contest end.he just changed the variable names. Channel Leaked-Code His submission at last second  » 7 weeks ago, # | +7 In B if i print 1 as 01 it consider it wrong but both are equivalent integers and no intructions are provided regarding leading zero .stupid testing got WA 2 times.  » 7 weeks ago, # | 0 According to me my E is working but my solution gets WA on test 5 can anyone please help me where i am lagging https://codeforces.com/contest/1788/submission/192944044 •  » » 6 weeks ago, # ^ | 0 Take a look at Ticket 16725 from CF Stress for a counter example. » 7 weeks ago, # | 0 # help For problem A, why are the prefix and suffix methods giving me WA?! I was multiplying pre and suf values and then checking for every position i if pre[i] == suf[i+1] (For i=1 to n-1) or not. I Got WA this way. •  » » 7 weeks ago, # ^ | 0 well, if i understand you correctly you multiply numbers in the array which may give you overflew since assume if n = 1000 and all elements will be 2 then you have 2 power 1000 which way too large to store in c++ •  » » » 7 weeks ago, # ^ | 0 yes, i had quite a hard time solving this but i figured that i could change this into a prefix sum problem instead. i was able to solve it using prefix sums by converting each 1s to 0s and 2s to 1s. truth be told it was not efficient. good luck to us next time!!!  » 7 weeks ago, # | 0 Problem D:First I identified what are all the possible co-ordinates that all dots can end at. This is a set containing the mid point of every possible dot pair of array. Now we just need to find out in how many subsets each point in the set can appear. I found this using binary search.Implementation of D  » 7 weeks ago, # | 0 GOT AC LAST SECOND  » 7 weeks ago, # | ← Rev. 3 → +12 D just 3 seconds before!!  » 7 weeks ago, # | +3 The time limit of F is too tight. I wrote the correct solution but got TLE on pretest 58. I think it's better to decrease the value of$n,q\$ to 1e5 or increase the tl to maybe 5 secs.
 » 7 weeks ago, # |   0 Problems are fun! thanks to authors :)
 » 7 weeks ago, # |   0 i am depressed, what time can i get a color name.
 » 7 weeks ago, # |   0 Can someone give a small test case on which my solution 192923926 fails?
•  » » 6 weeks ago, # ^ |   0 Take a look at Ticket 16724 from CF Stress for a counter example.
 » 7 weeks ago, # |   0 Very very very standard problem E and F. I cannot accept that.
 » 7 weeks ago, # |   -10 Weak testcase in B no. In the statement, given 1<=n<=1e9. Unconciously, I used int(as datatype) and passed the pretest. After the contest I noticed my mistake and expected to get wrong answer. But, after final judgement , my solution passed all the testcase :)192907426
•  » » 7 weeks ago, # ^ |   0 What do you think range int has in GNU C++17 7.3.0 (your used compiler)?You can always check in Custom Invocation smth like this: #include #include using namespace std; int main() { using IntLimits = numeric_limits; cout << IntLimits::min() << ' ' << IntLimits::max() << endl; return 0; } 
•  » » » 6 weeks ago, # ^ |   0 My bad. I knew, int support around 10^6. But, I'm wrong. Thanks for your kind information.
 » 7 weeks ago, # |   0 Problem C. Using the formula for the sum of an arithmetic progression, we found that the sum of the first pair is (3n+3)/2. Now how do we restore all pairs? Thank you.
 » 6 weeks ago, # |   0 Great contest! you can find the video editorials for problem C and D here .hope this helps you! happy coding!
 » 6 weeks ago, # |   0 Hello! I submitted two implementations of treap in E, and the "faster" version works 5 times longer! Can anyone explain it? "slower": 193052447 "faster": 193052503 I know that "faster" gets TL on a test with a = {0, 0, 0, ..., 0}, but I can't realize the reason of O(n) height of a treap.
 » 6 weeks ago, # |   0 hopeforces
 » 6 weeks ago, # |   0 Problem B. Sum of Two Numbers ***** my solution get wrong answer on test case 8, my solution is true and that makes me sure that I take this code copy and submit it again and get accepted, plz check it for my. the solution which gets wrong answer during the contest the same solution gets accepted after the contest !!!
 » 6 weeks ago, # |   0 Lately I receive a message that my submission 192896600 is same as 192935411.I cheked it and find that his solution to the problem is different from mine.I guess may be comments at the end of the code is the reason why two submissions is thougt as same.In addition, I can give evidence that I used this template before him. mine:188824606 his:189071540[user:KAN][user:MikeMirzayanov][user:azberjibiou]
 » 6 weeks ago, # |   0 Today I receive a message that my submission dusanesaksham14/ 192925696 is same as sakshamsdusane/ 192924170.I checked it and i think the the basic algorithm used in both the codes are same which might be used by many one. It is just a coincidence and nothing else. My template used in every question is same and that can be noticed. This might be happened due to ideeone.com as you have already mentioned. I have submitted code for B wo time, → 192925185 & → 192925696 , and both time you can see i have used same template. This is just a coincidence and nothing else. If needed i can give more evidences to validate my code.please do needfulThank you
 » 6 weeks ago, # |   0 About coinciding the solutions: Sorry about that. Both 2020331034_Jahid and Quintessential are my handles. The first one I use for academic purposes and the second one is for practice purposes.
 » 6 weeks ago, # |   0 About coinciding the solutions: Sorry about that. Both 2020331034_Jahid and Quintessential are my handles. The first one I use for academic purposes and the second one is for practice purposes.