### flamestorm's blog

By flamestorm, 7 weeks ago,

We hope you enjoyed the contest!

1791A - Codeforces Checking

Idea: flamestorm

Tutorial
Solution

1791B - Following Directions

Idea: flamestorm

Tutorial
Solution

1791C - Prepend and Append

Idea: flamestorm

Tutorial
Solution

1791D - Distinct Split

Idea: SlavicG

Tutorial
Solution

1791E - Negatives and Positives

Idea: SlavicG

Tutorial
Solution

1791F - Range Update Point Query

Idea: flamestorm

Tutorial
Solution

1791G1 - Teleporters (Easy Version)

Idea: flamestorm

Tutorial
Solution

1791G2 - Teleporters (Hard Version)

Idea: flamestorm

Tutorial
Solution

• +77

 » 7 weeks ago, # |   -6 wow tutorial comes out so fast!
•  » » 7 weeks ago, # ^ |   +21 wow comment comes out so fast!
•  » » » 7 weeks ago, # ^ |   +9 wow reply comes out so fast!
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   -10 !
•  » » » » » 7 weeks ago, # ^ |   +8 wow i am not fast
•  » » » » » » 7 weeks ago, # ^ |   -6 wow my reply comes so fast
•  » » » » » » 7 weeks ago, # ^ |   0 wow i am not so fast than you
•  » » » » » » » 7 weeks ago, # ^ |   0 wow my net works so fast during the contest
•  » » » » » » » » 7 weeks ago, # ^ |   0 6666
•  » » » » » » » » » 7 weeks ago, # ^ |   0 wow you are so fast
•  » » » » » » » » » 7 weeks ago, # ^ |   -22 话说666是不是只有中国有
•  » » » » » » » » » 7 weeks ago, # ^ |   -22 确实
•  » » » » » » » » » 7 weeks ago, # ^ |   -17 确实
•  » » » » » » » » » 7 weeks ago, # ^ |   0 Why many people vote "I don't like it"?Is it because I used Chinese?
•  » » » » » » » » » 7 weeks ago, # ^ |   +3 i'm so slow
•  » » » » » » » » » 7 weeks ago, # ^ |   -17 可能因为他们看不懂，hhh
•  » » » » » » » » » 7 weeks ago, # ^ |   0 Even i am also fast
•  » » » » » » » » » 7 weeks ago, # ^ |   -6 笑死了，发个中文被踩了10次（
•  » » » » » » » » » 7 weeks ago, # ^ |   0 My contribution drops so fast!
•  » » » » » » » » » 7 weeks ago, # ^ |   -6 我从+1掉到-1了。。。
•  » » » » » » » » » 7 weeks ago, # ^ |   0 问题不大，分不掉就行（
•  » » » » » » » » » 7 weeks ago, # ^ |   +3 I'm slow
•  » » » » » » » » » 6 weeks ago, # ^ |   0 I am average
•  » » » » 7 weeks ago, # ^ |   +1 Wow reply to a reply comes out so faist!
•  » » » » » 7 weeks ago, # ^ |   0 wow the series grows so fast
•  » » » » » » 7 weeks ago, # ^ |   0 wow you can type so fast
•  » » » » 7 weeks ago, # ^ |   +1 wow my rating drops so fast!
•  » » » » » 7 weeks ago, # ^ |   0 wow what a thread
 » 7 weeks ago, # |   +3 Kudos for the fun round and the near instantaneous posting of the tutorial.
 » 7 weeks ago, # | ← Rev. 2 →   0 can someone help me understand why my code for problem G1 doesn't work? https://codeforces.com/contest/1791/submission/192028236EDIT: nvm i figured it out, using a set will remove duplicates siiiiggghhhhhhhhhhhhhhhhhh
•  » » 7 weeks ago, # ^ |   0 I think you should read the question again and Test case explanation also.
•  » » 7 weeks ago, # ^ |   0 Did the same thing on my first submission. Multiset or a sorted vector would’ve worked
 » 7 weeks ago, # | ← Rev. 2 →   0 For problem F we can also use a segment tree where the nodes have the max value in the subtree. If the maximum value in any subtree is less than 10 then we shouldn't update that subtree and can skip it. Complexity wise it should be the same as the editorial solution. Implementation 192043154
•  » » 7 weeks ago, # ^ |   0 Bro can you please tell me what is wrong in this implementation of seg tree? Code
•  » » » 7 weeks ago, # ^ |   +1 Take a look at Ticket 16708 from CF Stress for a counter example.
•  » » » » 7 weeks ago, # ^ |   0 Bro Thank you very much. I found my mistake. Also you shared a nice website. Thanks a lot
 » 7 weeks ago, # |   +8 Perfect div 4 round IMO. Every problem was solvable by div 4 people, with 1 problem that would push most div 4 people and another problem that would really push most div 4 people but still was solvable
•  » » 7 weeks ago, # ^ |   0 Ah man, I'm kinda disappointed with myself tho I only managed 3 questions :/
 » 7 weeks ago, # | ← Rev. 4 →   0 Did anyone else solve f with DSU? My solution: https://codeforces.com/contest/1791/submission/192000576Basically if i and i-1 are < 10, we can put them the same set. If a query has an l and r in the same set, we don't need to do anything
•  » » 7 weeks ago, # ^ |   0 Yes. I did the same. F with DSU.
 » 7 weeks ago, # | ← Rev. 2 →   0 I solved problem F with segment tree (lazy propagation), where I keep track of each update range [l, r] to know the number of times a certain index i [l <= i <= r] also ensuring when the number x <= 9 to break the loop (:)committed 2 WAs initially because of this). Code192028574
•  » » 7 weeks ago, # ^ |   0 Bro can you please tell me what is wrong in this implementation of seg tree? 192042203
•  » » 7 weeks ago, # ^ |   0 unfortunately i solved it using lazy propagation segtree too. I had a feeling it's not needed since it's a div 4 round, and the solution without it is nice. Segtrees sure are powerful though
•  » » 7 weeks ago, # ^ |   0 It can be solved using square root decomposition which i used during the contest
 » 7 weeks ago, # |   +6 A great problemset. btwi can see myself on the first page of official standing xD
•  » » 7 weeks ago, # ^ |   +3 Congrats!
•  » » » 7 weeks ago, # ^ |   0 Thank you 😄
•  » » 7 weeks ago, # ^ |   +1 I want this kind of flex
 » 7 weeks ago, # |   0 Wow, the tutorial came out so fast. Searched for useful data structures online for problem F and found that using binary indexed tree works.
•  » » 7 weeks ago, # ^ |   0 nice,thanks to you i found out lazy propagation is possible with BIT
 » 7 weeks ago, # |   0 Short and succinct solutions. Love it 👏
 » 7 weeks ago, # | ← Rev. 2 →   0 Very cool that F can be solved with set and DSU. I got stuck on BIT implementation because I don't have a template for it and have only solved a few CSES problems using it. Forgot about the limitation of 3 change operations. Thought G2 would be DP, but the binary search solution is quite elegant. 10/10 problemset overall.
 » 7 weeks ago, # |   0 Solved E with DP. Also for the first time I have used segment tree lazy propagation in a live contest (problem F) :)
•  » » 7 weeks ago, # ^ |   0 Can you show me your code for E? i spend an hour to find that a O(n) solution.And i just know if i use dp to solve E i will be TLE.
•  » » » 7 weeks ago, # ^ |   0 sure ll n; cin>>n; ll ara[n+1]; for(ll i=1; i<=n; i++) { cin>>ara[i]; } ll dp[n+1][2]; memo(dp,0); dp[1][0] = ara[1]; dp[1][1] = -ara[1]; for(ll i=2; i<=n-1; i++) { dp[i][0] = max(dp[i-1][0] + ara[i], dp[i-1][1] - ara[i]); dp[i][1] = max(dp[i-1][0] - ara[i], dp[i-1][1] + ara[i]); } dp[n][0] = max(dp[n-1][0] + ara[n], dp[n-1][1] - ara[n]); cout<
•  » » » » 7 weeks ago, # ^ |   0 Nice! I was trying with dp too but couldn't make it AC with dp. 191959517
 » 7 weeks ago, # |   +1 Everywhere i go i see "In queue"
 » 7 weeks ago, # |   0 I wonder what role mesanu and Mike had in preparation of this round given that all problem ideas were by Slavic and flamestorm. Maybe they helped prepare the test data or something.
 » 7 weeks ago, # |   0 Thanks to y'all for amazing contest!
 » 7 weeks ago, # |   0 For those who solved F with segment tree/fenwick tree, etc., Um_nik's 2nd and 3rd bullet point from this comment is highly relevant 😁
•  » » 7 weeks ago, # ^ |   0 Everyone is not Um_nik. May be they tried to think of not using Fen-wick but did not get idea of binary search As a last resort they might have used fen-wick
•  » » 7 weeks ago, # ^ |   0 yeah true, but gotta do what you gotta do if it's the only solution you came up with
 » 7 weeks ago, # | ← Rev. 3 →   0 Can anyone hack my G2? I think it is not correct even I passed the pretest. 192031288
•  » » 7 weeks ago, # ^ |   +8 Okay~ I hacked myself and other four Unfortunate guys
•  » » » 7 weeks ago, # ^ |   0 Legend
•  » » » 7 weeks ago, # ^ |   0 orz
»
7 weeks ago, # |
0

DISTINCT SPLIT plz tell why my code doesn't work. If possible, plz mention the test case where it fails as well.

# include

using namespace std;

int main(){ long i; cin>>i; while(i--){ long a; cin>>a; long first = 0; long mid = a; string te; cin>>te; unordered_map<char,long> temp; for(long i = 0; i<a; i++){ if(temp[te[i]]==0){ temp[te[i]]++; first++; } else{ mid = i; break; } } long second = 0; unordered_map<char,long> temp1; for(long i = mid; i<a; i++){ if(temp1[te[i]]==0){ temp1[te[i]]++; second++; } } cout<<first+second<<endl; } return 0; }

 » 7 weeks ago, # |   0 can someone help me understand why my code for problem F gives tle? https://codeforces.com/contest/1791/submission/191999834
•  » » 7 weeks ago, # ^ |   0 The else case of a[x] < 9 allows for repeatedly applying fun(9).
•  » » » 7 weeks ago, # ^ |   0 thanks bro got it
 » 7 weeks ago, # |   -29
•  » » 7 weeks ago, # ^ |   +4 enough?
 » 7 weeks ago, # | ← Rev. 4 →   +5 This is my first contest on this platform and it's really great.For G2, Editorial solves in O(nlogn) after sort but I solve in O(n) + O(logn) after sort.https://codeforces.com/contest/1791/submission/192046876
•  » » 7 weeks ago, # ^ |   0 thats the same complexity sir
 » 7 weeks ago, # |   +3 My screencast with explanations. The problems were very interesting. Thanks for the contest.
 » 7 weeks ago, # |   0 It seems that the problem writers like binary indexed tree. Both F and G2 can be solved by binary indexed tree.
 » 7 weeks ago, # |   0 did someone do the g2 question using priority queue?
•  » » 7 weeks ago, # ^ |   0 I tried, but it ended up highlighting how muddy my idea of picking the first from-left move was... rather than sorting that out (perhaps by literally sorting), I got lost in the weeds of popping and replacing per case/situation and then deleting/rewriting messes.
 » 7 weeks ago, # |   0 good round!
 » 7 weeks ago, # |   0 I think the F problem can also be solved with segment tree. https://codeforces.com/contest/1791/submission/192019842
•  » » 7 weeks ago, # ^ |   0 Bro, What did you do?? Can you explain me please...
 » 7 weeks ago, # |   0 Btw there is also fenwick/segment tree solution for problem F. That is even really simple to implement it.
 » 7 weeks ago, # |   0 Nice contest, and thanks for fast editorial.
 » 7 weeks ago, # |   0 There's a sqrt decomposition solution for F, for a range of size sqrt(n) save the number of updates on this rsnge‌ as cnt of that range, and then for the queries which they want you to print the value of an index, add cnt of that index + cnt of the range which it belongs to (let sum of these be $K$) and find the $K$'s digit sum for that index's number, here's the code :. 192059676
 » 7 weeks ago, # | ← Rev. 2 →   0 Can someone explain this part in problem F to me on example: 1 l r — search for the smallest active index at least l (since the list is sorted, we can do it in O(logn)). Afterwards, update that index (replace ai with S(ai)), remove it if it's no longer active, and binary search for the next largest active index in the sorted list, until we pass r.
 » 7 weeks ago, # |   0 Is it possible to solve the problem F using Segment tree algorithm concept?? Can anyone help me with this solution using Segment tree...
•  » » 7 weeks ago, # ^ |   0 Solved it using segment trees but got TLE in tc 4
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 Precompute the sum of digits till there remains one digit. It helps me in fighting with TLE on 4.192204290. I use bit.
•  » » » » 7 weeks ago, # ^ |   0 i did it but still got TLE
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 The edu section has a guide to such segment tree
•  » » 7 weeks ago, # ^ |   0 Sure, it can. You need simple tree with 'modification on interval' and 'single element access' operations. Check out this blog for implementation details https://codeforces.com/blog/entry/18051
 » 7 weeks ago, # |   0 For problem E, "if the count of negative numbers is odd, we must have one negative number at the end How can i prove this?
•  » » 7 weeks ago, # ^ |   0 here u can shift negative sign to any elements like if i have -2 3 -1 4 -6 5 then it can be easily changed to 2 -3 -1 4 -6 5 then 2 3 1 4 -6 5 still u have one negative now shift that negative sign to 3 index (1 based)
•  » » » 7 weeks ago, # ^ |   0 I understand that negative signs can be shifted anywhere.What im asking is how do we know that there is no sequence of operations such that no negative numbers remain (in the odd case)?
•  » » » » 7 weeks ago, # ^ |   0 in one operations either u remove two negative sign or no negative signs see there are three cases when both are negative :- make both positive, 2 neg signs removed when both are postive : no needed , 0 neg signs removed when one is neg and one is positve : still no neg sign removed so every time numbers of neg sign removed is multiple of 2 hence it count is odd one sign always remains
 » 7 weeks ago, # |   0 Why my code fail at testCase 3 in F.
•  » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16719 from CF Stress for a counter example.
 » 7 weeks ago, # |   0 what is the proof of greedy for G1. I thought of it like knapsack but constraints were big so i did greedy but I dont know why greedy is working. shouldn't it fail for the same reason where greedy doesnt work for knapsack ?
•  » » 7 weeks ago, # ^ |   0 Knapsack has a value and weight. If there is only a value your can use greedy.
 » 7 weeks ago, # | ← Rev. 2 →   0 Thought that each number could only have 3 states for F. This is so sad
 » 7 weeks ago, # |   0 Guys, pls, explain F
 » 7 weeks ago, # |   0 I used sweep line on F, I haven’t seen anyone talk about it yet. Store the queries and the index they appear and start the sweep line on the array from left to right. Add active elements(index of the query) when it reaches l in an order set and remove them after it reaches r+1. The first 3 values indicate the minimum index to achieve that state. Can be optimized to o(n)
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Used the same Alg and got HACKED. Possibly TLE.
•  » » » 7 weeks ago, # ^ |   0 You have to process all the queries beforehand
•  » » » » 7 weeks ago, # ^ |   0 I actually realized what you did here (Checked your solution). At first, it was uneasy to comprehend because of Java, but you did a mixed sweep line with the ordered set. That was a great one and to check them 0,1,2,3 for later is great.
•  » » » » 7 weeks ago, # ^ |   0 But if consider a problem with 10 states, it will consume memory. [Though Imma PY coder XD]
•  » » » » » 7 weeks ago, # ^ |   0 Hack... Was able to hack my solution to about over half the memory and time available with Java. So it does consume a lot of memory but it is possible to reduce the amount of memory and time used by not storing the states the numbers can transition. So about n+4q memory.
•  » » » » » » 7 weeks ago, # ^ |   0 Great one at hack and further possibilities. You got this. :))
•  » » » » » » » 7 weeks ago, # ^ |   0 Thanks :)
•  » » 7 weeks ago, # ^ |   0 Nvm about o(n) still o(nlog(q)+q)
 » 7 weeks ago, # |   0 192071106 I'm stuck wondering why this code is not working. Not sure if I misunderstood the problem.
•  » » 7 weeks ago, # ^ |   0 Iterate forward and backward separately. you will see a pattern.
•  » » 7 weeks ago, # ^ |   0 Try this testcase: 1 8 bcaffggf Expected output:7
 » 7 weeks ago, # |   0 Got my precious 2 solution Hacked due to Arrays.sort(JAVA) so much pain this days :-(
•  » » 7 weeks ago, # ^ |   0 Yeah, that and unordered sets are really annoying hacks.
 » 7 weeks ago, # |   0 In problem G2, why is it wrong to take the first portal as portal having minimum overall cost? Can you give a failing test case?-
•  » » 7 weeks ago, # ^ |   +1 If I understood your question, it's because that minimum could be taken with an even lower cost.For example for $n=3$, $a = [17, 8, 2]$ and $c = 13$ we can get use second and third teleporter but not if I go to the third one first.
•  » » » 7 weeks ago, # ^ |   0 Thanks! Got it
 » 7 weeks ago, # | ← Rev. 3 →   0 On problem D I stumbled upon a very weird thing:When I test my code on my computer, all the test input returns correct answers. However, when I submit this code, I get an error on string "paiumoment". I have no idea how to debug this, because on my machine the answers are all correct. Does anybody know what is the issue?My g++ version is 12.2.0. I stried both versions 17... and 14.6.4.0 when I submitted the code.Here's the link to my code: https://codeforces.com/contest/1791/submission/192076794P.S. I have a feeling that it does something to do with g++ versions, because on different versions the incorrect answers are different values. But how exactly does it work? I never came across such a problem before
•  » » 7 weeks ago, # ^ |   0 You never initialized cnt which causes undefined behavior because the values of cnt do not start at 0.
•  » » » 7 weeks ago, # ^ |   0 Oops, that's an awkward mistake... Thanks a lot!
•  » » » » 5 weeks ago, # ^ |   0 would not have happened in java
 » 7 weeks ago, # |   0 Wow tutorial comes out so fast!Can problem F be solved with a segment tree?
 » 7 weeks ago, # |   0 I can't figure out what is wrong with my code for problem 1791D — Distinct Split. Can anyone help me out? #192086640
•  » » 7 weeks ago, # ^ |   0 Try this testcase: 1 8 bcaffggf Expected output:7
 » 7 weeks ago, # |   0 I solved the F with a segment tree over a difference array
•  » » 7 weeks ago, # ^ |   0 Can you explain your approach?
 » 7 weeks ago, # |   0 I don't know where is wrong about my D code ?I need help !!! #include using namespace std; void solve() { int n; string s; cin>>n>>s; mapp; int x = 0; for(int i = 0;i < n;i ++ ) { p[s[i]]++; if(p[s[i]]==2) { x = i; break; } } string ss; for(int i = x;i < s.size();i++) ss+=s[i]; int sum = 0; sort(ss.begin(),ss.end()); for(int i = 0;i < ss.size();i ++ ) { if(ss[i]!=ss[i+1]) sum++; } cout<>t; while(t--) solve(); return 0; } 
•  » » 7 weeks ago, # ^ |   0 Try this testcase: 1 8 bcaffggf Expected output:7
 » 7 weeks ago, # | ← Rev. 2 →   0 I know some people used a seg tree over a difference array, but did anyone else have the same idea but do it with a fenwick tree? https://codeforces.com/contest/1791/submission/192095662
 » 7 weeks ago, # |   0 Can anyone please tell me why this code is giving wrong ans on testcase 2 For the F problem https://codeforces.com/contest/1791/submission/191982272
•  » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16718 from CF Stress for a counter example.
 » 7 weeks ago, # | ← Rev. 2 →   0 In G1, what I understand, there is no port in point 0. So, according to the problem, I cannot teleport back to 0 from 0. But if I consider there is no port at point 0, I get WA. To get AC, I had to consider that there could be port at 0. Why? Also the explanation for testcase 1 is given considering the array is 0 indexed. But while explaining testcase 2, we are considering the array is 1 indexed. I am having confusion. Please help me!
•  » » 7 weeks ago, # ^ |   0 Array is 1 indexed every where , maybe you're misreading the sample tests. And also ,there is no port at 0
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Oh I thought 0 index is 0 point. My bad
 » 7 weeks ago, # |   0 // cur += min(1, cnt[i]) + min(1, p[i]);In the editorial why are we taking the minimum of frequency of a character in a and b ?
•  » » 7 weeks ago, # ^ |   0 I am sorry I didn't mention this doubt is from problem D
 » 7 weeks ago, # |   0 Can somebody explain why set solution is working in F while map solution giving TLE;Here is my map Solution giving TLE; https://codeforces.com/contest/1791/submission/191980859
 » 7 weeks ago, # |   0 Problem E solution using DP in O(n). Refer here
 » 7 weeks ago, # |   0 Please help me I am not able to recognize my mistake Please help me think i fault in my logic for problem D I am stopping my iteration in string at the point where I find a duplicate character for example : if string is ppzs the two string according to my algorithms should be p + pzs
•  » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16714 from CF Stress for a counter example.
•  » » » 7 weeks ago, # ^ |   0 @variety-jones how do u use CF stress do u have a paid subscription?? thank u for ur help
•  » » » » 7 weeks ago, # ^ |   0 I'm the creator of the website. Yes, if you'd like to use it for yourself, you will need to purchase a subscription.
•  » » » » » 7 weeks ago, # ^ |   0 yeah the website is really very cool
 » 7 weeks ago, # |   0 Problem F can also be solved by binary indexed tree, which is much easier to implement than segment tree if you didn't come up with the tutorial solution. #include #define MAXN 200005 using namespace std; int n,q,arr[MAXN],diff[MAXN],opera; int lowbit(int x) { return x&(-x); } void add(int x,int v) { for (int i=x;i<=n;i+=lowbit(i)) diff[i]+=v; return; } int ask(int x) { int ans=0; for (int i=x;i>=1;i-=lowbit(i)) ans+=diff[i]; return ans; } int main () { int T; cin>>T; while (T--) { cin>>n>>q; for (int i=1;i<=n;i++) { cin>>arr[i]; diff[i]=0; } for (int i=1;i<=q;i++) { cin>>opera; if (opera==1) { int x,y; cin>>x>>y; add(x,1); add(y+1,-1); } else if (opera==2) { int x,y; cin>>x; y=min(ask(x),3); int ans=arr[x],temp; for (int j=1;j<=y;j++) { temp=0; while (ans) { temp+=ans%10; ans/=10; } ans=temp; } cout<
 » 7 weeks ago, # |   0 Can anyone explain to me how to solve G2? Thanks in advance.
 » 7 weeks ago, # | ← Rev. 2 →   0 Problem F can be solved with simple seg tree. On each nodes of seg tree we store the count of times that range has been updated by first type of query. Then for the second type of query, we keep adding the nodes value until we reach the desire x. If the total no. of count is >=3 then we simply output our precalculated value for index x till 3,(you can see this precalculation in my solution, its too easy to explain). Other wise output precalculated[count][x].You can refer to my solution for more clarification 192045935
 » 7 weeks ago, # | ← Rev. 2 →   0 Great contest! I love it! Hope I can get specialist this time.
 » 7 weeks ago, # |   0 Can someone help me understand why my submission https://codeforces.com/contest/1791/submission/192109277 for G2 is giving WA on test 3
•  » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16713 from CF Stress for a counter example.
 » 7 weeks ago, # |   0 I have a strong data for problem F, but I forget to try it when open hacking,but it can successfully hack one of my friends's code,I left it here but I'm so sorry for that it's a chinese website,but I have tried my best to explain how to use it,you can just download data at the bottom of the website. here: https://www.luogu.com.cn/problem/U279041
•  » » 7 weeks ago, # ^ |   0 I'm so sorry for don't konw how to upload file on codeforces.
 » 7 weeks ago, # |   0 can anyone explain why i am getting tle one test case 3 on problem F- Spoilerll testcases=1; cin>>testcases; while(testcases--) { ll n,q; cin>>n>>q; vectorarr(n,0); setst; for(int i=0;i>arr[i]; if(arr[i]>=10) { st.insert(i); } } while(q--) { ll type; cin>>type; if(type==1) { ll l,r; cin>>l>>r; l--; r--; while(true) { if(st.empty()) { break; } auto it=st.lower_bound(l); if(it==st.end()) { break; } if((*it)<=r) { ll temp=arr[(*it)]; ll curr=0; while(temp) { curr+=(temp%10); temp/=10; } arr[(*it)]=curr; if(curr<10) { st.erase(it); } l=(*it)+1; } else{ break; } } } else{ ll ind; cin>>ind; ind--; cout<
 » 7 weeks ago, # |   0 E using DP "Memoization" Code
 » 7 weeks ago, # |   0 Can somebody please explain the binary search section of G2?I did similar approach up to it, then used modified inbuilt upper_bound function. It was my logical error. But I still cant understand from the editorial.
 » 7 weeks ago, # |   0 Can someone tell me why this code get TLE in F mySubmission
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 You using SegmentTree, so when you update range [l, r], you update from [l, r]. If we have 1E5 query (1 1 n), your code has time complexity is O(n * 1E5 * log(n)) => TLE. This is my opinion about your code.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 I think as i know, in the segment tree the one query takes log(n), and hence the queries over all test cases won't exceed 2e5 so the total complexity will be the number of queries multiplied by the time per query plus the construction of the tree (build function) so we can say: O(2e5 * log(2e5) + 2e5) = O(C * 1e6) where C is a constant so why TLE?
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Segment Tree update 1 element in log(n), but you update the range from l to r, so it takes O(log(n) * (r — l + 1)) in 1 query, not log(n)
•  » » » » » 7 weeks ago, # ^ |   0 So you want to say that we can't solve it using segment tree, can we?
•  » » » » » » 7 weeks ago, # ^ |   0 In my opinion, I think it can't.
•  » » » » » » 7 weeks ago, # ^ |   0 I think you don't totally understand how segtree works.Segtree is for optimizing "range" operation, and if you see your code again, you will find it only updates in the leaves, which means the segtree doesn't kick in.Maybe you can change it to record every element's updation count to make segtree functional.Sorry, my English is not good.
•  » » » » » » » 7 weeks ago, # ^ |   0 I know the concept of segTree and solved introductive problems by it. btw I'll try again thanks
 » 7 weeks ago, # |   0 Does someone have good blogs/material about square root decomposition technique for problems like F?
 » 7 weeks ago, # | ← Rev. 5 →   0 PROBLEM 4: shouldn't the output of the 5th test case be 4 ? aazz -> az az -> 2+2 ( SORRY I UNDERSTOOD IT WRONG )
•  » » 7 weeks ago, # ^ |   0 You can only split the original string into 2 strings with non-zero lengths. Given the input aazz, you can split the string to a and azz aa and zz aaz and z. There was an explanation for your concern in the contest's notification. Happy coding ^^
•  » » » 6 weeks ago, # ^ |   0 Thanks . I just joined 20 minutes before the contest ended. I think I missed that notification.
 » 7 weeks ago, # |   0 Hi guys, I am confused. This is my first contest. Why does it show unrated on my profile? I thought I should get a rating as I am a newbie. Thanks
•  » » 7 weeks ago, # ^ |   0 Every contest shows unrated before the ratings come out.
 » 7 weeks ago, # |   0 I have a doubt about my submission for F. My code is similar to the one provided in the editorial, the only difference being that I simply moved the iterator to the next element in the set after first setting the iterator to the lower bound of l. But it gives TLE on test case 18. To my knowledge, wouldn't it be better to just move the iterator to the next element in the set as it is already sorted rather than using a binary search to get the next valid index at every iteration? Here's my code -> https://codeforces.com/contest/1791/submission/192143264
 » 7 weeks ago, # |   0 Subject: Need Help for G2 In tutorial it is said we will need to do BS over all the values by taking it as our first problem. While solving I thought that if we took min out of all the starting costs it would be enough. In case of equality between 2 such values I took the one with greater cost from back. It is showing WA at test case 828 expected 2 output 1; what is wrong in my reasoning ?
•  » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16712 from CF Stress for a counter example.
•  » » » 7 weeks ago, # ^ |   0 Thanks a lot
 » 7 weeks ago, # |   0 it's good tutorial
 » 7 weeks ago, # |   0 I participated in this contest but its not showing my profile in the official ranking, even though i am a newbie and my rating is below 1400 so i should be eligible. Can someone explain to me why its not showing my profile in official ranking.
 » 7 weeks ago, # |   0 Why does this solution give the wrong answer? question (1791E) http://pastebin.ubuntu.com/p/TrRV4gSKG5/
 » 7 weeks ago, # |   0 In problem E (Negative and positives), I write my comparator function for sorting, but why does this solution give runtime on test case 24? Can anyone explain? 1791E - Negatives and Positives 191930201
•  » » 7 weeks ago, # ^ |   0
 » 7 weeks ago, # |   0 Can anyone help in finding the test case in which my algorithm is failing in problem F. Range Update Point Query . submission Link
•  » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16717 from CF Stress for a counter example.
 » 7 weeks ago, # | ← Rev. 2 →   0 Attention!****My solution 191999829 for the problem 1791C significantly coincides with solutions 0rirobin0/191999829, rakat27/192015958 are not almost similar! We are not copied each other. ****Coincidentally our code ended up being structurally similar but the variables we took didn't match! here in 0rirobin0/191999829 i used test case variable as 't' and in rakat27/192015958 he took 'a' as a variable in test case!****If you check the submission time you will see I submitted my code at first than rakat27 and i didnt copied him! please rejudge my proof and kindly bring my rating back! regards 0rirobin0 code screenshot link below ->
 » 7 weeks ago, # |   0 Here is an alternative solution for problem G2 (Python): https://codeforces.com/contest/1791/submission/192216076It is quite fast and in my opinion easier and faster than the original solution.Obviously it is still nlog(n) because of the sort.
 » 7 weeks ago, # |   0 I had done the same implementation also got accepted during contest but now it's showing tle in https://codeforces.com/contest/1791/submission/192033550. I don't know what's wrong with it. Please have a look
•  » » 7 weeks ago, # ^ |   0 solutions gets judged with pretests before actual tests, only after the open hacking phase (12hrs) that they judge solutions with all testcases
•  » » » 7 weeks ago, # ^ |   0 set s; it= s.lower_bound(a); it= lower_bound(s.begin(),s.end(),a); whats the difference between two
•  » » » » 7 weeks ago, # ^ |   0 sets and maps uses random access iterator and has their own lower_bound method that works in O(logN), but if you use lower_bound() on sets and maps, it works in linear time, meaning O(N)
 » 7 weeks ago, # |   0 Great Problem G2
 » 7 weeks ago, # |   0 In the problem G2, I am not getting how are they handling the case when the portal we are considering is included both times as the initial portal and in the minimum cost prefix. And in the tutorial's code what this piece of code is doing? int now = mid+1; if(mid > i) { price-=a[i].fr; now--; } can anyone help me out?
•  » » 7 weeks ago, # ^ |   0 So , i+1 here is the first index you went to from index 0 That is why , we subtract a[i].sc from c. Now , we have the prefix sums of costs which were sorted . So we do BS.During BS, we are at index midif we are at mid what it means is Our first step was to index i+1 And we are currently at index mid (we could have come from 0 or n to mid)mid could be > i or <=iNow what happens to price alias pref[mid] when i < mid ? pref[mid] = sum of a[index].fr for index from 1 till index mid But we already visited index i+1 (which is <=mid) . Because it was our first index! So we do not need to add a[i].fr again. Thats why we subtract a[i].fr from price if i < midNow coming to the number of teleporters you visit. If i >= mid: 1 2 ... mid-1 mid mid+1 .... i i+1 Your first visit was to index i+1 and then you visited all indices from 1 to mid In total 1 (index i) + mid(1 till mid) Thats why now is mid+1Now what if i < mid?1 2 ... i i+1 .. mid mid+1 ... You already visited index i+1 Now you visit till index mid — BUT SKIP INDEX i+1 So , you visit just mid number of indices But you initialised now to mid+1 So subtract 1 from now.
•  » » » 6 weeks ago, # ^ |   0 still the index i should be included in the ans because it also comes under visited list but doing a now-- excludes that from the visited list???
 » 7 weeks ago, # | ← Rev. 2 →   0 Can someone help me figure out why this solution:192214278 for F 1791F - Range Update Point Query is giving WA. Thanks. Edit:- I was able to come up with a test case where the solution gives an unexpected answer: Testcase13 699998 999999997 9991 2 21 2 21 2 22 12 22 3
•  » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16716 from CF Stress for a counter example.
•  » » » 7 weeks ago, # ^ |   0 Cool!! but the code is giving the expected output for the provided test cases:
•  » » » » 7 weeks ago, # ^ |   0 One possible reason is undefined behavior in your code resulting in RTE across systems. (Looks like you are doing itr++ as part of loop increment after you have deleted/invalidated your iterator.
•  » » » » » 7 weeks ago, # ^ |   0 Yeah..I got it
 » 7 weeks ago, # | ← Rev. 2 →   0 Can someone help figure out why 192415650 (G2) gives WA?
 » 7 weeks ago, # |   0 Why my code get TLE on test 18 for problem G1? I used qsort to sort the array. https://codeforces.com/contest/1791/submission/192238361
 » 7 weeks ago, # | ← Rev. 4 →   0 Can someone help me figure out why 192601940 gives WA? https://codeforces.com/contest/1791/submission/192601940
 » 7 weeks ago, # |   0 In problem F: why am I still getting TLE, despite keeping the how many times updated a[i]? Can someone explain it to me,
 » 7 weeks ago, # |   0 Can anyone explain why this code is failing this test case?https://codeforces.com/contest/1791/submission/192817422
 » 7 weeks ago, # |   0 How to write the dp of the E question？
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 https://codeforces.com/blog/entry/112282?#comment-1000597 Codell n; cin>>n; ll ara[n+1]; for(ll i=1; i<=n; i++) { cin>>ara[i]; } ll dp[n+1][2]; memo(dp,0); dp[1][0] = ara[1]; dp[1][1] = -ara[1]; for(ll i=2; i<=n-1; i++) { dp[i][0] = max(dp[i-1][0] + ara[i], dp[i-1][1] - ara[i]); dp[i][1] = max(dp[i-1][0] - ara[i], dp[i-1][1] + ara[i]); } dp[n][0] = max(dp[n-1][0] + ara[n], dp[n-1][1] - ara[n]); cout<
•  » » » 4 days ago, # ^ |   0 thank you!
 » 6 weeks ago, # |   0 love G2 .....!!
 » 6 weeks ago, # |   0 Wow I'm seeing this editorial late
 » 5 weeks ago, # |   0 G1 test case explanation is wrong
 » 5 weeks ago, # |   0 Can Someone help for which case i am getting the Wrong Answer in Problem 1791G2.Here is my code link https://codeforces.com/contest/1791/submission/194376164
 » 4 weeks ago, # |   0 I have a doubt in problem G1? Won't the answer depend on the index of the teleporter. For ex if the smallest teleporter placed at some index value which is too high and reaching there isn't possible i.e index of smallest teleporter > c coins given to us. But at the some time there exist a teleporter(not the smallest teleporter) whose { index + teleporting point <= c coins } . Is my question valid? Please help me out asap.
 » 4 weeks ago, # |   0 another easy way for easy version of teleporters 194870644
 » 4 weeks ago, # |   0 I am a beginner... problem E, help... find the largest sum... if we have: 6 1 1 -1 2 -2 -2 -1 -1 -1 2 -2 -2 -1 1 1 2 2 2 result is 8... I'm wrong, it kills me the doubt help.... because if we have 5 0 5 -5 1 4 0 -5 -5 1 4 0 5 5 1 4 result is 15 help please what am I doing wrong... 
 » 3 weeks ago, # |   0 i want to be a grandmaster
»
10 days ago, # |
0

quetions NO.D where is mistake my code I don't know if you know or find mistake in my code please pin your massage ~~~~~ Your code here...

# include<bits/stdc++.h>

using namespace std; int main(){ int t; cin>>t; while(t--){ int n,res=0,sum=0; cin>>n; int count=0; string s; cin>>s; sets1; sets2; sets3; for(int i = 0; i<n; i++){ s3.insert(s[i]); } if(s3.size()==1){ cout<<"2"<<endl; } else{

for(int i =0; i<n-1; i++){
if( s[i]==s[i+1]){
count = i+1;
}
if(i==n-2){
sum=i;
break;
}
}

if(sum==n-2){
for(int j = 0 ; j<n-1; j++){
if((s[res]==s[j+1]) && (res!= (j+1))) {
count = j+1;
}
else{
if(j==n-2){
res++;
j=0;
}
}
}

}

for(int k = 0; k<count; k++){
s1.insert(s[k]);
}
for(int  g = count; g<n; g++){
s2.insert(s[g]);
}
cout<<s1.size()+s2.size()<<endl;
}
}
return 0;

} ~~~~~