Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### 127.0.0.1's blog

By 127.0.0.1, history, 4 weeks ago, translation,

Thank you for participating!

• +116

 » 4 weeks ago, # |   +34 Thanks for the fast editorial!
•  » » 4 weeks ago, # ^ |   0 I am having a little problem in D. Its working on nearly all the test cases and logic is to point. But I think there is some problem with modulus and its giving wrong answer on one test case-v 179 1000000000000000000 Can any body help I cant seem to figure it our. This is my code where maxi is modulus ll l,r; cin>>l>>r;ll te=l; ll ans=0; while(te<=r) { ll p=log2(te); ll up; // if(p==63) // up=r; // else up=min((ll)(pow(2,p+1)-1LL),r); //cout<up) break; ct=(ct+1)%maxi; te=nx; } if(up==r) break; te=up+1;} cout<
•  » » » 3 weeks ago, # ^ |   0 I had kinda similar problems, try using unsigned long long instead if you're not using that
•  » » » » 3 weeks ago, # ^ |   0 Ohhh...Ok thanks a lot
 » 4 weeks ago, # |   0 Why the approach for F with euler tour+Lazy prop is giving tle on tc 21? here is the code-https://codeforces.com/contest/1891/submission/230589277any help will be appreciated.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I think the problem is that you are passing the adj vector to dfs not by reference
•  » » » 4 weeks ago, # ^ |   0 vector*adj means we are passing vector adj[n] by reference.Thanks for responding but i got AC by using unordered_map instead of map.
•  » » » 4 weeks ago, # ^ |   0 what is a problem in this solution? https://leetcode.com/problems/maximum-points-after-collecting-coins-from-all-nodes/submissions/1086929050/
•  » » 4 weeks ago, # ^ |   0 i used your approach but it is memory limited, can you help :( my submission: https://codeforces.com/contest/1891/submission/230760871
•  » » » 4 weeks ago, # ^ |   0 oh i forgot to pass 'g' by reference in dfs function, so dumb
 » 4 weeks ago, # |   +5 I came up with the author's solution F, but I didn't have enough time to debug((
 » 4 weeks ago, # |   +16 F can be solved without reversing the queries. It is offline though.
•  » » 4 weeks ago, # ^ |   +12 It would be online if the final tree was known beforehand. Otherwise — yes, the online solution would be quite nasty with maybe some link-cut trees or treaps.
•  » » 4 weeks ago, # ^ |   +2 What do you mean by reversing the queries? I just run on the queries and update to 0 when adding a node
 » 4 weeks ago, # |   0 What does the "transition" mean in D?
•  » » 4 weeks ago, # ^ |   0 nvm, got it
•  » » » 4 weeks ago, # ^ |   0 I did not. Can you explain?
•  » » » » 4 weeks ago, # ^ |   0 indexes i where g[i] != g[i+1]
 » 4 weeks ago, # |   0 For the B problem what i did was that i just added condition that any element in x should be taken one time but according to the editorial this condition can fail in some cases.So is my code correct https://codeforces.com/contest/1891/submission/230580104
•  » » 4 weeks ago, # ^ |   0 But still you can have at most 30 distinct operations which can include the useless ones but it won't change the array and time complexity remains linear, so it works.
 » 4 weeks ago, # |   +3 achha contest
 » 4 weeks ago, # |   0 nice round for a beginner like me!!
 » 4 weeks ago, # |   0 In C problem I did as proposed in editorial, but in one test case answers differ. Here is sequence of 14 hits from my implementation: [1, 1, 2, 5, 6, 6] =1h small stack=1 0/6 =2h small stack=1 1/6 =4h small stack=2 2/6 =6h big stack=5 4/6 crushing 6/6 =7h -> [3, 6] combo=0 [3, 6] =10h small stack=3 0/6 crushing 3/6 =11h -> [3] combo=0 1 stack with 3 left. hit by 1 [3]=14h Can someone provide a sequence to win with just 13 hits?
•  » » 4 weeks ago, # ^ |   0 On the final stack of 6 use the combo at the end (2 small attacks (4) -> combo(-1)) instead of doing combo(3) -> 3 small attacks(0).
•  » » » 4 weeks ago, # ^ |   +11 Thanks. Premature use of combo is the root of evil
 » 4 weeks ago, # |   0 How to avoid tle for C https://codeforces.com/contest/1891/submission/230581501
•  » » 4 weeks ago, # ^ |   0 If you want to stick to this approach, try using std::deque, erase() from the beginning of vector is expensive operation. Or take a look how beautifully contest leaders solved it.
 » 4 weeks ago, # |   0 Here is an alternative solution for F, using Fenwick Tree.
•  » » 4 weeks ago, # ^ |   0 Same, I think this is more direct.
•  » » 4 weeks ago, # ^ |   0 What's the logic?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +12 I believe that my solution 230576374 is the same as in this comment, so I'll describe it.Let's build our tree and for each vertex save its creation time and updates with current time and value.What is answer for some vertex? It's sum of all requests which were made on this vertex or any of parents LATER than creation time of current vertex. So let's create BIT for sum of requests by time and dfs our tree. We perform updates before getting ans and rollback them before dfs exit thus for each vertex only relevant updates remain: dfs(u, p): for (time, value) in updates[u]: bit.update(time, value) ans[u] = bit.get(createdAt[u], n) for (int v: g[u]): if v != p: dfs(v, u) for (time, value) in updates[u]: bit.update(time, -value) Each update is made exactly twice, so it's $O((n + q) \log(n))$
•  » » » » 4 weeks ago, # ^ |   0 Thanks for the explanation! Very creative solution. I like that you no longer need range updates, only point updates and range queries.
 » 4 weeks ago, # |   +108 What was the reasoning for putting problem F at that position?
 » 4 weeks ago, # |   0 Anyone have an answer for D in python?
 » 4 weeks ago, # |   +21 This is probably the easiest F I've ever seen :(
 » 4 weeks ago, # | ← Rev. 5 →   +5 C can be implemented not using two pointers. But during the contest i forgot to check if n == 1 and a[i] == 1 :\ void solve() { scanf("%lld", &n); int s = 0; for (int i = 1; i <= n; i ++) { scanf("%lld", &a[i]); s += a[i]; } if (n == 1 && a[1] == 1) { puts("1"); return; } int sp = s / 2; sort(a + 1, a + 1 + n); int ss = 0, cnt = 0; for (int i = n; i >= 1; i --) { ss += a[i]; cnt ++; if (ss >= sp){ break; } } printf("%lld\n", cnt + s - s / 2); } 
 » 4 weeks ago, # |   0 I have a problem on C . In 230619057 the code id accepted , but in 230619275 , the code is wrong . The only difference between them is merely in "lower_bound(pres,prew+n+1)" or "lower_bound(pres+1,pres+n+1)" . But the pres is the prefix sum of a which indicates that the sum divided by 2 (floor,except for n = 1) must be positive . So "+1" should not make a difference to my solution . I am quite confused . Please help we .
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I reverse the order , sorry . The former one is wrong , while the latter one is correct .
 » 4 weeks ago, # |   +36 I think swap E and F is a good idea
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 #
•  » » » 4 weeks ago, # ^ |   0 because sorting of array takes O(nlogn)
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 oh okaybut i sill didnt get solution. I also tried similar logic but in some test case like : 1 1 2 5 6 6it is not working. My Solution
•  » » » » » 4 weeks ago, # ^ |   0 I wrote some comments on it. Hope it will help you! 230751313
•  » » » » » » 4 weeks ago, # ^ |   0 Thanks for giving time.
 » 4 weeks ago, # |   0 Can someone please tell me why is my submission for Problem D giving TLE? Code#include using namespace std; #define ll long long #define nl '\n' #define all(v) v.begin(), v.end() #define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll const mod = 1000000007; ll inf = 1000000000000000000; int iter = 0; ll binexp(ll a, ll b){ ll ans = 1; while (b){ if(b % 2){ if(ans>inf/a) return inf+5; ans = (ans * a); } if(a>inf/a) a = inf+5; else a = (a*a); b /= 2; } return ans; } ll LOG(ll x, ll p=2){ if(p == 1) return 0; for(ll t=1, i=0;; t*=p, i++){ if(t > x) return i-1; if(t > inf / p) return i; } } ll func(ll x){ ll res = 0, L = 4, R, p, val; while(L <= x){ p = LOG(L); val = LOG(L, p); R = min({(1ll<<(p+1))-1, binexp(p, val+1)-1, x}); // cout << L << ' ' << R << nl; res += (val * ((R - L + 1) % mod)) % mod, res %= mod; L = R+1; } return res; } void Heisenberg(){ ll q; cin >> q; while(q--){ ll l, r; cin >> l >> r; cout << (func(r) - func(l - 1) + mod) % mod << '\n'; } } signed main(){ auto begin = std::chrono::high_resolution_clock::now(); IOS Heisenberg(); auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; } 
•  » » 4 weeks ago, # ^ |   0 You recalculate intervals every time you run "func" function. Doing it once and storing it somewhere could help. My solution working as I said: 230684869
•  » » » 4 weeks ago, # ^ |   0 Yeah, I got that later. Even this solution is correct if I directly calculate from L to R rather 1 to R and 1 to L.
 » 4 weeks ago, # |   -15 This round was too easy, though people still couldn't solve problems, I don't know why. I managed to solve D in time and saw my rank go way up. A handful of 20 minutes was still left for the contest but I convinced myself I wouldn't be able to solve E. I saw E later after the contest ended and it was the easiest Division 2 E I've ever seen.
 » 4 weeks ago, # |   +2 Mathforces
•  » » 4 weeks ago, # ^ |   +4 Nope SpoilerI guess most of the questions are implementation-based!
 » 4 weeks ago, # |   +13 why is E is much difficult than F. Or why is F much easier than E.
 » 4 weeks ago, # |   0 Maybe the simplest implementation for C: sort(a+1,a+1+n); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]; int tmp=(sum[n]+1)/2; int c=0; for(int i=1;i<=n;i++) if(sum[i]>tmp) c++; printf("%lld\n",tmp+c); 
•  » » 4 weeks ago, # ^ |   0 can you explain the reason behind this approach?
•  » » 4 weeks ago, # ^ |   0 Please explain your solution!
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Lets call $A$ = total number of monsters.Suppose we make $s = ceil(A/2)$ moves of type-1 (killing single monsters). Then at the end we will have accumulated total power of $(A - s)$. This much power is certainly enough to kill all the remaining hordes of monsters, no matter what they might be. Making more than $s$ moves of type-1 is certainly wasteful.Now, it only remains to use the accumulated power, intelligently. Which is simply to kill the biggest hoardes. (since cost of killing small hordes is also $1$.)(Also, making lesser than $s$ moves of type-1, cannot lead to a better answer, atleast not in a single step. And if we do multiple rounds, like some recursive solution that could lead to a better solution, then the values could be simply added to the initial answer straightaway. So, there is no-real benefit of doing multiple rounds.)
 » 4 weeks ago, # | ← Rev. 2 →   0 can anyone explain why the greedy solution works in C? also for the case when i==j and the last number is an odd number and x=0, then there is no way we can use the 2nd method on this horde
•  » » 4 weeks ago, # ^ |   0 It's possible to use 2nd method when there is only 1 horde left with odd size and x = 0.For example left horde size = 7 and x = 0 Use 3 attacks of first type. After that horde size = 4 and x = 3. Use second type (ultimate) attack. After that horde size = 1 and x = 0. Use 1 attack of first type. After that horde size = 0.So it takes 5 attacks to destroy horde size including second attack. Without second attack it would take 7 attacks.
•  » » » 4 weeks ago, # ^ |   0 thanks, and it was my bad, I took the 2nd method as it can be used only when there are exactly x monsters left in a horde :-(it's also clear now why the greedy solution works
 » 4 weeks ago, # | ← Rev. 2 →   0 I came up with using offline query in problem F. My idea is first save the query and build the completed tree which is presented in the end. Then, I just need to loop from q to 1 and update normally using Euler's tour when type 2 is meet otherwise if type 1 is the current query, output it's node value. But unfortunately, I got WA immediately at 2nd test case although this idea is kind of nature (or maybe it's wrong in some case), anyone suggests me why am i wrong here?My submissions: 230648660
 » 4 weeks ago, # |   0 can anyone help in f...getting wa on 2..230657380
•  » » 4 weeks ago, # ^ |   0 are u wrong answer in 4927th or 799th
•  » » » 4 weeks ago, # ^ |   0 4927
•  » » » » 4 weeks ago, # ^ |   +3 It is wrong in answer of node. Node in tree is different from node in euler tour (my english is bad sry about it)
•  » » » » » 4 weeks ago, # ^ |   0 sorry for being such stupid....replaced a[i] with a[tin[i]] and accepted....thanks
 » 4 weeks ago, # | ← Rev. 2 →   0 #
•  » » 4 weeks ago, # ^ |   0 sorting is $O(n \log n)$ :unamused:
•  » » » 4 weeks ago, # ^ | ← Rev. 4 →   0 allright i got it .but i sill didnt get solution. I also tried similar logic but in some test case like : 1 1 2 5 6 6it is not working. My Solution
•  » » » » 4 weeks ago, # ^ |   0 It's exactly the same thing I missed, see discussion above https://codeforces.com/blog/entry/121876?#comment-1081838
 » 4 weeks ago, # |   0 Can someone give a simple idea about F? Also may I know what are the prerequisites to learn to solve problem F?
•  » » 4 weeks ago, # ^ |   +19 Queries are offline, you already know how your tree will look like Can you solve this problem if first queries are always making the tree and other queries are adding (I mean, try solve this: you have a tree and $q$ queries add some $value$ on subtree, how solve this?)
•  » » » 4 weeks ago, # ^ |   0 Thank you :)
•  » » » 4 weeks ago, # ^ |   0 I guess there are multiple ways of doing the 2. one you have mentioned. Can you suggest which method is good to opt.
•  » » » » 4 weeks ago, # ^ |   +10 You can do $dfs$ and go down from root to leafes. If in node $x$ you get some sum from above, you also get same sum into all nodes in $x$ subtree.
•  » » » » » 4 weeks ago, # ^ |   0 ok thank for your valuable idea.
•  » » 4 weeks ago, # ^ |   +6 Prerequisites: "offline" approach, DFS pre-order, fenwick tree (range add/point get interpretation)
•  » » » 4 weeks ago, # ^ |   0 ok thank you for your valuable reply.
 » 4 weeks ago, # |   0 Is there any online solution for F?
•  » » 4 weeks ago, # ^ |   0 Maybe sqrt?
 » 4 weeks ago, # |   0 In problem D and on each segment there are at most O(logn) transitions shouldnt there be like at most 2 transitions per segment because if we make 3 transitions that would mean jump to next segment?
 » 4 weeks ago, # |   0 My logic is similar to one in editorial but I am having issues with MOD. What changes should be done in my code ?https://codeforces.com/contest/1891/submission/230655160Also what are some good sources for topics like modular arithmetic and other topics that will help me remain stable expert. Thanks
 » 4 weeks ago, # |   0 Hi Codeforces, this was my second ever contest and this time i was able to solve problem A my submission: 230544275 i found this to be interesting because it was difficult for me to comprehend what the question was asking, then i just read the problem and analyzed the sample testcases for about 15-20 mins, I found that if the index that is not sorted (a[i]>a[i+1]) lies in the powers of 2(0,1,3,7,15) then it is possible to sort it otherwise not, I just implemented this and got it through. I was elated after the first submission passed the pretests so my confidence boosted for the second problem, I just implemented a brute force solution 230561923 and it passed the sample cases so I decided to submit it, Obviously it gave a TLE at pretest 3 but overall it was a great experience, looking forward to solving more and growing. Please if possible, share your helpful feedbacks on my solutions. happy coding!!
 » 4 weeks ago, # |   0 For problem C I kept on overthinking that the solution would involve DP, however I did notice that the constraints on $x$ was too big and that it would most probably lead to TLE. However, can anyone think if DP is feasible for problem C if $x$ was actually some small number?
 » 4 weeks ago, # |   0 Out of curiosity following problem F , how will this problem be solved? Initially i have only one vertex which is numbered 1.There are 1e5 qeuries where in one type of query i can add a vertex to the tree with number sz+1 (sz is the no of nodes in the tree currently).Can i answer other type of query where i need to tell the size of subtree rooted at a given vertex in logn time or what will be the most optimized algorithm for this.
•  » » 4 weeks ago, # ^ |   0 Euler Tour TechniqueNote that you don't need to answer the queries online. So you can create the whole tree and process queries later.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 can you explain a bit more . Like when a node is added i need to change the size of subtree of all the ancestors of the node . How will i do that?
•  » » » » 4 weeks ago, # ^ |   0 https://codeforces.com/contest/1891/submission/230704812here is my solution using exactly the same idea as in the analysis of the contest. maybe it will help you :D
•  » » » » » 4 weeks ago, # ^ |   0 ok got it thanks a lot
•  » » » » 4 weeks ago, # ^ |   0 From the page: Notice that after running dfs, each range [start[i], end[i]] contains all ranges [start[j], end[j]] for each j in the subtree of i. So, to add something to the subtree of i, you just update the values from start[i] to end[i]. This can be done with any range update technique.
•  » » » » » 4 weeks ago, # ^ |   0 ok got it thanks a lot
•  » » » 3 weeks ago, # ^ |   0 what does online means here? I saw it in other comments also but don't know it's meaning
•  » » » » 3 weeks ago, # ^ |   +1 u dont know the queries in advance
 » 4 weeks ago, # |   0 For Problem B, I wrote my code on Python, and I am getting correct answers when I run it on my system, but wrong answers when I run on CF. Here is my code — https://codeforces.com/contest/1891/submission/230716694
•  » » 4 weeks ago, # ^ |   0 It doesn't give the correct answers in system either.
 » 4 weeks ago, # |   0 I understood the editorial algorithm for C, but can someone help me with why the greedy algorithm is correct? I am unable to prove it. Thanks alot!
 » 4 weeks ago, # | ← Rev. 5 →   -7 PROBLEM D
 » 4 weeks ago, # | ← Rev. 2 →   +8 Here is the implementation of sqrt decomposition for F. It is giving TLE as warned by author. Any optimisation in provided code is welcomed.
 » 4 weeks ago, # |   0 For D problem can someone provide me simple explanation ? (Even its implementation is complicated even tried) https://codeforces.com/contest/1891/problem/D
 » 4 weeks ago, # |   +1 is there a way to solve problem c with binary search
 » 4 weeks ago, # |   +1 Can F be solved online?
 » 4 weeks ago, # |   0 https://codeforces.com/contest/1891/submission/230866197can anyone help me with problem F? cant find any error
 » 4 weeks ago, # |   0 I think it is better with spoilers, and code.
 » 4 weeks ago, # |   0 Can someone explain the solution of problem B? I didn't understand the idea of the editorial.
•  » » 4 weeks ago, # ^ |   0 Hello,bro I saw your profile You have solved a good amount of questions but your rating is not increasing because you are not solving/practicing questions of 1200 — 1500 rating you are only solving questions of below 1000 rating use this website https://clist.by/problems/?resource=1 for codeforces question and try to solve more than 1200 rating questions :-) Thank You
•  » » » 4 weeks ago, # ^ |   0 Thanks.
 » 4 weeks ago, # |   +5 Thank you, 127.0.0.1
 » 4 weeks ago, # | ← Rev. 2 →   0 127.0.0.1 I am having a little problem in D. Its working on nearly all the test cases and logic is to point. But I think there is some problem with modulus and its giving wrong answer on one test case-v 179 1000000000000000000 Can any body help I cant seem to figure it our. This is my code where maxi is modulus ll l,r; cin>>l>>r; `ll te=l; ll ans=0; while(te<=r) { ll p=log2(te); ll up; // if(p==63) // up=r; // else up=min((ll)(pow(2,p+1)-1LL),r); //cout<up) break; ct=(ct+1)%maxi; te=nx; } if(up==r) break; te=up+1; } cout<
 » 3 weeks ago, # |   0 https://codeforces.com/contest/1891/submission/231287946[submission:231287946] why i am getting tle in this approach can anyone pls help
 » 3 weeks ago, # |   0 can someone explain for me more about how to solve problem D , please ?
 » 2 weeks ago, # |   0 can someone help me,i am getting WA on test 2 of F https://codeforces.com/contest/1891/submission/232563023
 » 8 days ago, # |   0 Did anyone try (probably the dumbest) solution to F by reversing queries and doing segtree with range updates on the euler tour of the final tree? That's the first thing that comes to mind