### Karavaev1101's blog

By Karavaev1101, history, 3 months ago,

1388A - Captain Flint and Crew Recruitment

Idea: Denisov

Tutorial
Solution (Karavaev1101)

1388B - Captain Flint and a Long Voyage

Idea: Karavaev1101

Tutorial
Solution (Karavaev1101)

1388C - Uncle Bogdan and Country Happiness

Idea: Karavaev1101

Tutorial
Solution (Karavaev1101)

1388D - Captain Flint and Treasure

Idea: Denisov

Tutorial
Solution (Denisov)
Solution (Karavaev1101)

1388E - Uncle Bogdan and Projections

Idea: perekopskiy

Tutorial
Solution (perekopskiy)

• +245

 » 3 months ago, # |   +60 Thanks for the quick editorial!
 » 3 months ago, # | ← Rev. 4 →   +207 Feel free to downvote, but this is my honest opinion; Personally, I think that the grammar of problem C made it abit annoying to understand.
•  » » 3 months ago, # ^ |   +12 Agreed. If not for the notes, I probably would have wasted a lot of time understanding the statement.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +17 Yup, I don't mean to complain, but statements similar to these felt somewhat distracting-> "Every person has its own mood: somebody leaves his workplace in good mood but somebody are already in bad mood."
•  » » » » 3 months ago, # ^ |   +32 Totally disagree. You can of course point out a few subtle grammar mistakes, but they don't obscure the general idea.
•  » » 3 months ago, # ^ |   +40 was writing " was made it a bit annoying" on purpose? If so, it's funny. If not, it's sad XD
•  » » 3 months ago, # ^ |   +6 Lengthy background but interesting problems.
•  » » 3 months ago, # ^ |   +26 I agree. you know most of the participants mother language isn't english and they can't get the statement easily, when you make the statement hard to understand, it will be really hard for them and sometimes they just skip the problem and lose it points because they can't understand the statement, and that will give them a really bad point at the contest. so please take more care for the statements.
•  » » » 3 months ago, # ^ |   +5 Yes, I totally agree with you. As I am not a native English speaker or a native Russian speaker(I am Chinese), for some problems the statement is very difficult to understand(QAQ) and extremely complicated, although the statement itself is quite easy.
 » 3 months ago, # |   +37 Lol I was in bad mood after reading the long statement of C. Missed it by one case
•  » » 3 months ago, # ^ |   +17 do yoga it will help you
 » 3 months ago, # |   0 For problem D--can anyone please explain or give a test case where my solution is going wrong. The testcases in problem are too big to debug. Here is the link to my submission.I am bascially making a directed graph where an edge from u to v denotes that operation on u-th element must be done before v-th element of the array a. Then I am running a dfs on transpose of this graph and updating all elements(suppose v-th and w-th index element needs to be operated before u-th element, then updating a[u]=a[v]+a[w]) and adding those to answer while maintaing this order.
•  » » 3 months ago, # ^ |   +26 Your solution fails on that test case: test36 -5 12 3 -1 Answer91 2 3Your solution works that way because after doing some operations $a_{b_i}$ can become positive and you can improve other $a_j$ using that $a_{b_i}$
•  » » » 3 months ago, # ^ |   0 Oh okay! Got it. Thanks a lot :)
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +18 How to solve D if we remove additional constraint ( if Cycle is there ) ?
 » 3 months ago, # |   +4 Would anybody help me with Question D?My submission --> 88521832.Approach: I made a 2D array of row size n to see whether there is any index that must be ahead than index i(0<=i
•  » » 3 months ago, # ^ |   +5 I'm sorry that my English is not very well.There's a situation in the process of Adding $a_i$ to $a_{b_i}$ that it may change $a_{b_i}$ from negative to positive.In this situation,if $b_{a_{b_i}}$ doesn't equal to $-1$,it should be also ahead some than some index.But it seems that you didn't manage to do this.Note that there's a principle that no matter what $b_i$ is,we should always put the index with $a_i > 0$ ahead of the index with $a_i < 0$.there's a sample that your algorithm makes mistakes:Input3-2 -1 4-1 1 2Output83 2 1But your output is:51 3 2Hope my reply could help you.
•  » » » 3 months ago, # ^ |   0 Thanks man! I got it now.
 » 3 months ago, # |   -42 Video solution of the whole problemset
•  » » 3 months ago, # ^ |   +8 hoping it won't let us down
 » 3 months ago, # |   -42 [unbalanced]
 » 3 months ago, # | ← Rev. 2 →   0 Why dont topological sort works in D?88526038
•  » » 3 months ago, # ^ |   +3 I solved this problem using topological sort. You can check my submission.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +2 here's my AC submission with topological sort -> 88536305
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Can You Explain it.How are you maintaining the last sequence ? UPD: I got it.
•  » » 3 months ago, # ^ | ← Rev. 3 →   +6 Performing the operation on any ai < 0 before any aj > 0 may decrease the maximum sum, right?That's why you have to perform the operation on those positions at last (from bottom to top in topological order, so that it won't affect any ai < 0 too), so that it won't affect the maximum sum.My submission using topsort
•  » » 3 months ago, # ^ |   +5 In fact,the solution by Karavaev1101 is topological sort,though it's hard to tell.
•  » » » 3 months ago, # ^ |   0 You're right
 » 3 months ago, # |   +8 It's my 2nd contest.I solved a no. problem.But still no rating given.How long does it take to get ratings after a contest is finished?
•  » » 3 months ago, # ^ |   0 Hey, The ratings have arrived. You can see them if you want.
•  » » » 3 months ago, # ^ |   +12 Yeah!I got 242 plus ratings!
•  » » » » 3 months ago, # ^ |   +3 Greattt!!! Keep going mate...
 » 3 months ago, # | ← Rev. 2 →   -52 I am sorry but Problem B was just Horrible. Why the fuck am I sorry, It was fucking' horrible. Yuck.
•  » » 3 months ago, # ^ |   0 Maybe you could have put your opinion in a constructive manner
•  » » » 3 months ago, # ^ | ← Rev. 3 →   -44 not really in the mood man... somedays you just wanna let out...but I mean no hate...
 » 3 months ago, # |   +2 In my humble opinion problem set was amazing, but problem B was made a lot obvious by the example input, it could have been swapped with problem A if problem A constraints were made a bit tighter and brute force was not allowed.
•  » » 3 months ago, # ^ |   -13 Hey I think prob A was very easy...I mean just look at the code, it's basic brute force... ll n; cin >> n; if(n<=30) cout << "NO" << endl; else { if((n-30)==6 || (n-30)==10 || (n-30)==14) { cout << "YES" << endl; cout << 6 << " " << 10 << " " << 15 << " " << (n-31) << endl; } else { cout << "YES" << endl; cout << 6 << " " << 10 << " " << 14 << " " << n-30 << endl; } } 
•  » » » 3 months ago, # ^ |   0 Yeah isn't B also a relatively basic observation.
•  » » » » 3 months ago, # ^ |   +1 Yeah sure but I missed a very important line NOTE resulting in my WA twice and then I was able to get it right...XDBecause of that I missed problem C.
•  » » » » » 3 months ago, # ^ |   0 hello, in problem B if I have n = 5 then the number must be 9 9 9 9 9 in binary : 1001 1001 1001 1001 1001 but after removing last 5 digits then it become 1001 1001 1001 100- ---- which makes it a 4 digit number, so making that 5 digit number I need to make it all 0s : 1001 1001 1001 1000 0000 but this doesn't the case. Can anyone help me with that ?
•  » » » » » » 3 months ago, # ^ |   0 Why do you think 0's binary is considered 0000? Why not 0000000000000 or anything else? Answer this and you'll get your answer as well.
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Hey,The number must be 99988 for n=5 because you have to select the minimum possible number. It's binary form is1001 1001 1001 1000 1000Now, you might select 99980 as minimum but I made the same mistake for the first time and then I read the note given in the Que saying that 1000 is greater than 0000 so you have to select the greater bit possessing but lower value having number so 99988 is correct.Now removing the last 5 bits, we get 1001 1001 1001 0100 which makes it 9994 which is the maximum number possible. Got my point?
•  » » » » » » » 3 months ago, # ^ |   0 yes, got it thank u
 » 3 months ago, # |   +55
•  » » 3 months ago, # ^ |   +9 did u know, you wasted 61 seconds in this counting!! lol :>
 » 3 months ago, # | ← Rev. 2 →   0 what kind of error is it "wrong output format Unexpected end of file — int32 expected" ? i did not see before . 88520911
•  » » 3 months ago, # ^ |   0 The grader was expecting more numbers(int32) in the output, but your solution did not print them. Check if you are printing the required output in the specified format. You can check my submission for more clarity.
 » 3 months ago, # |   +22 Great round, guys!
 » 3 months ago, # | ← Rev. 3 →   +8 In problem C How can (av+hv)/2 count the number of people in a good mode?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +6 suppose X are the people that were happy at city A and Y were the people that were not happy at the same city. Then X+Y = total citizens that visited the city(total citizens in subtree of that city). X-Y = (happy-sad) given for city. Add both equations and get the value of X which is same as described in the editorial.Hope you understand.Edit- by happy i mean good mood as in problem statement.
•  » » » 3 months ago, # ^ |   0 Thanks!
•  » » » 3 months ago, # ^ |   0 can you please tell me why my c submission gives wrong answer https://codeforces.com/contest/1388/submission/88556004
•  » » 3 months ago, # ^ | ← Rev. 2 →   +2 Honestly I didn't solve it like that, but I'll explain.Think that moods are G good and Y bad, in a city with P people. Do you agree that P == G + |Y|? Do you agree that H = G — |Y| ?Then P + H = G + |Y| + G — |Y| = 2G, and we are done.
•  » » » 3 months ago, # ^ |   0 Thanks!
•  » » 3 months ago, # ^ |   +3 let gv be the number of people in a good mood that passes through node v, and bv the number of people in a bad mood. With that we can write the following system of equations: gv-bv = hv and gv+bv = av. If we sum the both equations we get 2gv = av + hv and thus gv = (ah+hv)/2
•  » » » 3 months ago, # ^ |   +2 Thanks!
 » 3 months ago, # |   -7 Me to the second question :: WHy you do this to me????? :(
 » 3 months ago, # |   0 https://codeforces.com/contest/1388/submission/88510199 whats wrong with this submission for C?
 » 3 months ago, # |   0 https://codeforces.com/contest/1388/submission/88534351 What is wrong in this submission of C? I think I have considered all the cases but still, it is failing test 4. Great Contest, thanks!
 » 3 months ago, # |   0 I don't understand, in problem E — isn't there an easier way to calculate the projections? I don't know what the Convext Hull Trick is, but I mean, you have the angle and you have the height, that should be enough. Is the problem the fact that there could be error in the calculation and you will get a wrong result?
•  » » 3 months ago, # ^ |   0 It's a problem that you can't project every segment for every angle because it takes too much time, so we need to find the rightmost and leftmost projections quickly
•  » » 3 months ago, # ^ |   +3 If you calculate the projection of $O(n)$ vectors for each possible angle (there are $O(n^2)$ of them) the complexity becomes $O(n^3)$.
•  » » » 3 months ago, # ^ |   0 Ahhhh never mind I completely missed something. I thought the "no go" zones make a full range [theta1,theta2], and then you are left with only 2 angles to check. I understand now that there could be many options.
•  » » » 3 months ago, # ^ |   +8 By merging overlapping angle segments, it is possible to pass the time limit via this brute force method.88545255
 » 3 months ago, # |   0 Here I am generating a ton of primes and trying to do sliding window 3 sum with prefix sum to solve 2A and still couldn't. :( RIP rating. I'm sad.
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 I also had a sad story but it turned out ok.At first I read the problem as "multiple" instead of "sum". I solved it though xDYou just need the prime factorization and you need to pair up 3 pairs of different primes. (8 * 3 * 5 * 7 ==>> 2*3, 2*3, 2*5). (That made me 15 minutes behind :| )Edit: I need to start making it a priority to look at the god damn sample cases to verify I read the problem correctly.
 » 3 months ago, # |   +3 My video solutions to problems A, B, C, D. Enjoy watching.https://youtu.be/0ExktAwScLc
•  » » 3 months ago, # ^ |   0 thanks a lot!!
•  » » » 3 months ago, # ^ |   0 Wow, that's weird, why your rating started from 0? (Normally it starts from 1500)Did I miss some updates?
•  » » » » 3 months ago, # ^ |   0 Unfortunately, I couldn't find the blog for you. but yes, new account ratings start from 0 now.
•  » » » » » 3 months ago, # ^ |   0 Thanks :)
•  » » » » 3 months ago, # ^ |   0 You missed this
•  » » » » » 3 months ago, # ^ |   0 Oh, thanks!
 » 3 months ago, # |   +3 Didn't got AC at C be cause I was using python. Rewrote it in C++ and got AC. Don't use python in recursion problems...
•  » » 3 months ago, # ^ | ← Rev. 3 →   +10 Look at my solution, I use this "boostrap" decorator that someone posted a while back (I use it all the time and it always works), that replaces the recursion.It looks like this: The bootstrap decoratorfrom types import GeneratorType def bootstrap(f, stack=[]): def wrappedfunc(*args, **kwargs): if stack: return f(*args, **kwargs) else: to = f(*args, **kwargs) while True: if type(to) is GeneratorType: stack.append(to) to = next(to) else: stack.pop() if not stack: break to = stack[-1].send(to) return to return wrappedfunc  My DFS@bootstrap def dfs(v,pa,adj,p,h): s = 0 num = p[v] for u in adj[v]: if pa == u: continue x,y = yield dfs(u,v,adj,p,h) if x == -1: yield -1, -1 num += x s += y if (h[v] % 2 != num %2) or (h[v] < s-p[v]) or (h[v] >num) or (h[v] < -num): yield -1,-1 yield num,h[v] Just notice — To make the recursive call, you have to use yield. When you call recursively, you can't do 'if yield dfs(..)' or stuff like that, you have to first save the value with 'x = yield dfs(...)'. When you want to return something, you have to use yield (i.e., 'yield 5'). At the end of the function, if you return nothing, you have to use 'yield' with nothing after. THIS IS THE MOST IMPORTANT POINT. if you forget this you will spend eternity debugging. Thank me later.
•  » » » 3 months ago, # ^ |   -8 Can we implement it in c++
•  » » » » 3 months ago, # ^ |   0 Well, you don't need it in c++... 10**5 recursion works fine for you.
•  » » » » » 3 months ago, # ^ |   -8 I just wanna try, how to replace the *args thing what is that??
•  » » » » » » 3 months ago, # ^ |   -11 Lol you will literally not be able to do that, You have to implement a generator and I have no idea how you could do that in cpp.There's a reason python exists. One of those reasons is that you can do stuff like this in less than 1000 lines of code.
 » 3 months ago, # |   0 Can someone help me find the missing case here in my submission of problem C? I am unable to find the corner case here:My SubmissionThanks in advance
•  » » 3 months ago, # ^ |   0 Your variables are not initialized: ll pos,neg; You don't need to check case n == 1 separately. It's better to check the whole value for mod 2: (sum-abs(h[ind]))%2==0 https://codeforces.com/contest/1388/submission/88541430
•  » » » 3 months ago, # ^ |   0 Got it... Thanks Again
•  » » » 3 months ago, # ^ |   0 https://codeforces.com/contest/1388/submission/88555906 Can you please check my code, It fails on test case 3 and I am unable to find actual test case
•  » » » » 3 months ago, # ^ |   0 Can't see where you are using condition: "If person is in bad mood he won't improve it."
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 grey Can you please see where I am going wrong. My submission. Thanks in advance god[i] is number of good people in city i into[i] is number of people who pass through city i
•  » » » » » 3 months ago, # ^ |   0 Thanks, I miss that case
 » 3 months ago, # |   0 I had the same idea as the tutorial for problem no C, don't know where I messed up. :(
•  » » 3 months ago, # ^ |   0 same happended with me i just missed an edge case ..it feels bad
 » 3 months ago, # |   0 My friend who got into coding tried CF for first time and he received RE on both of his solutions, while locally it worked. As I'm not familiar with python, can somebody explain what is wrong? Thanks
•  » » 3 months ago, # ^ |   0 'input' doesn't work like that. First of all, input is a function, so it should be 'input()'.Second of all, it only reads one line.To get a line with an int you do int(input()).To get a list you do [int(x) for x in input().strip().split()] or list(map(int,input().strip().split())) or some other way.
 » 3 months ago, # | ← Rev. 3 →   +3 Can anybody please tell me where am I going wrong. Thanks in advance here B, G is no.of people in a bad and good mood respectively Codebool pos = true; pair dfs(int u, vectoradj[],int *p, int *h,vector&vis){ vis[u]=1; int B=0,G=0; for(auto v : adj[u]) if(!vis[v]){ pairx=dfs(v,adj,p,h,vis); B+=x.second;G+=x.first; } if(h[u]==G+p[u]-B) return {G+p[u],B}; else if(h[u]==G-B-p[u]) return {G,B+p[u]}; else pos =false,cout<>t; while(t--){ int n,m; cin>>n>>m;pos=true; int p[n],h[n]; FOR(i,0,n) cin>>p[i];FOR(i,0,n) cin>>h[i]; vectoradj[n+1],vis(n+1,0); FOR(i,0,n-1) { int x,y; cin>>x>>y; x--,y--; adj[x].push_back(y);adj[y].push_back(x); } dfs(0,adj,p,h,vis); if(pos) cout<<"YES\n"; else cout<<"NO\n"; } } Update : I am dumb
•  » » 3 months ago, # ^ |   0 Use spoiler for posting your code
•  » » 3 months ago, # ^ |   0 you if conditions are wrong recheck them
•  » » » 3 months ago, # ^ |   0 Kudos on -50 contribution Abhayp001
•  » » » » 3 months ago, # ^ |   +6 (ಥ﹏ಥ) thyyaanxx
 » 3 months ago, # |   -11 Check out the video editorial of Problem D
 » 3 months ago, # |   0 for problem c, i checked if(abs(h[i])>count[i] || count[i]%2 != abs(h[i])%2 ) then its not possible where count[i] = number of people visiting that node and h[i] = happiness value of i node.the second condition ensures that for a node with count = 5,the possible hvalues are -5,-3,-1,1,3,5 only.can anyone tell me why is it wrong? https://codeforces.com/contest/1388/submission/88539137
•  » » 3 months ago, # ^ |   0 You have only checked the upper limit i.e. abs(h[i])>count[i]. There will be a lower limit as well. suppose there are 2 cities i and j with i being the parent of j. now, let count be the number of people visiting j. Then let x be the the number of people with good mood and y be people with bad mood. Clearly , x+y=count and x-y = h[i].From here you can get x and y. Now , for the city i, the range would be [x-y,x+y].Because, There must be atleast x people with good mood. If you want the sol , refer to — 88508137
 » 3 months ago, # |   +1 Can someone please explain why in Problem D we reverse the second array ( the array with -ve elements ).
•  » » 3 months ago, # ^ |   0 So that negative values don't add up at any vertex.
 » 3 months ago, # |   +13 For problem E, the leftmost/rightmost segments can be handled in a similar manner as the "feasible angles" approach, by sequentially "trimming" the ranges where each of the $n$ segments is the leftmost/rightmost one.Code (sorry for too few newlines)
 » 3 months ago, # |   +1 Can anyone please tell me? In solution of C, how g[v]=(a[v]+h[v])/2 ?
•  » » 3 months ago, # ^ |   0 g[v](which is total good mood persons passes through vertex v)...................... calculate it through this given happiness index and no. of people passes. now the happiness index will be (acc. to question) (g[v]-(a[v]-g[v])),where (a[v]-g[v]) is sad people passes. hope u got it
•  » » 3 months ago, # ^ |   0 let $b_v$ be the number of people who visited city $v$ in a bad mood then $h_v = g_v - b_v,\,a_v = g_v + b_v$, and $\frac{a_v + h_v}{2} = \frac{g_v + b_v + g_v - b_v}{2} = g_v$
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Thanks a lot!! :D Got it!
 » 3 months ago, # |   0 I tried C with a little different approach. I calculated the number of people who travelled through a particular node with dfs and then applied bfs to check if the sum of unhappy people in children should be more than or equal to the number of unhappy people who travelled through the ancestor. I cannot figure out my error. A little help will go a long way. Code
•  » » 3 months ago, # ^ | ← Rev. 2 →   +1 It is not not necessary that sum of unhappy people in children should be more than or equal to the number of unhappy people who travelled through the ancestor because some of the unhappy people might live in the ancestor city.
 » 3 months ago, # | ← Rev. 2 →   0 Can someone plz give me an example in problem c where 3rd condition is not satisfied and other 2 condition are satisfied.
 » 3 months ago, # |   0 Thanks for the tutorial. I really need this to improve myself.
 » 3 months ago, # |   0 Why do i see variables written twice in B ?
 » 3 months ago, # |   0 ok, during contest my solution for B was correct but now its showing TLE but if i submit it again it got accepted what is happening, here are both submissions TLE submission AC submission
•  » » 3 months ago, # ^ |   +1 I am not sure but it has something to do with dynamic strings you are using, in first submission you code might have encounter memory issues. like you are making a string of size (maxN). when ever you push a char into it. string needs a contiguous free space to instert if it is not there then string will move the whole string to a place where memory is available. and this operation takes O(n) time to execute.that means complexity of your code could have crossed $N^2$ in this way on multiple occassions.look at this submission : https://codeforces.com/contest/1388/submission/88556412 code#include using namespace std; typedef long long int lli; typedef double db; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); lli t; cin>>t; while(t--){ lli n; cin>>n; string s(n, '9'); lli tm=n/4; lli tp=n%4; for(lli i=0;i=1){ s[n-tm-1]='8'; } cout<
•  » » » 3 months ago, # ^ |   0 yeah but time limit was 2 sec. i get the point that it is O(N*N) because i am coping the string every time like s=s+'9' every time s is copied here in right side of operator. and also after the contest same code at test case 7 run in around 600ms and the other TLE solution(same code during contest) run for >2000ms thats what i am asking i mean why is this happening just to be safe from next time. and btw thanks for reply.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 so s = s + '9'; this statement can run in either $O(1)$ time or $O(n)$ time. if memory is available it will run $O(1)$ time, but if mmemory not available in contiguous manner in memory this statement will take $O(n)$ as i said it will copy the whole string to a place in memory where is avalable.so it is not truly $O(n^2)$.it depends on the collsions (when contiguous memory is not available and compiler will perform $O(n)$ operation.) and your code at the time of contest got more collisions than when you ran it after contest.it might have something to do with may be that memory is under more demand during a contest in comparison to after contest.if your code's string get assigned a memory place from which a contiguous space which required is available in that your code will run in 30ms.If you want to be safe from next time then becareful while using dynamic memory allocations. and reserver memory before hand as much required in one statement. like most common mistakes like these are using unordered_map. link. https://www.geeksforgeeks.org/unordered_map-reserve-in-c-stl/i have a friend who uses char arrays instead of string to be extra safe.
 » 3 months ago, # |   +3 Nice problems.. Short solutions... quick editorial.. :)
 » 3 months ago, # |   0 This link is my submission to question C of yesterday's contest. Could someone please help by pointing out where am I going wrong?Thanks in advance
 » 3 months ago, # |   +10 In Problem C, you guys gave the necessary conditions with simple proofs, but what is the proof that these conditions are sufficient??
 » 3 months ago, # |   0 For problem C i checked for each node whether the number of happy people in that city is less than or equal to its parent node.Can someone tell why this approach is giving wrong answer?
•  » » 3 months ago, # ^ | ← Rev. 3 →   +4 You should check sum of happy people in all children of a parent is less than or equal to happy people of parent as happy people cannot increase.But in your approach happy people can increase.Take example A is parent and B,C,D are children. Happy at A=6, Happy at B=5, Happy at C=5, Happy at D=5. In this case your all conditions are satisfied and answer should be yes according to you but answer is no.In this situation you see that happy people at parent is 6. But moving ahead happy people increases it becomes 5*3=15 at children. It means bad mood people are decreasing that is not the answer to this question.That is why your answer is giving wrong answer.
•  » » » 3 months ago, # ^ |   +1 Got it.Thank you for helping.
•  » » » » 3 months ago, # ^ |   0 Yeah its fine bro. I also did similar mistake hence i thought to reply as its a learning platform and we can learn only by helping others and taking help from others.
 » 3 months ago, # |   0 https://codeforces.com/contest/1388/submission/88555647can anyone help me with this solution for problem D?
 » 3 months ago, # |   +6 C question was awesome, it helped me revise all concepts of dfs.
•  » » 3 months ago, # ^ |   0 Then try D with dfs. I liked it better.
 » 3 months ago, # | ← Rev. 2 →   0 For question D, the dfs solution given in the editorial doesn't always work, since the starting point is random with straightforward dfs. It seems to fail for — 3 1 -5 6 -1 3 2 expected — 9 given — 8
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 no it is not. we are only starting from the leaves. and that is the logic.Explain how is your expected result is 9?
•  » » » 3 months ago, # ^ |   0 The editorial solution (dfs) doesn't seem to enforce the condition that we should start from leaves. Like in the example that I have given, I ran it and the output was 8. But if we enforce the condition, it would have been 9.
•  » » » » 3 months ago, # ^ |   0 i don't see how you are getting 9..?
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 because your test case is too small here are possible answers to you test case 1 2 3 = -31 3 2 = 82 1 3 = -32 3 1 = -33 1 2 = 83 2 1 = 8there is no 9.
•  » » 3 months ago, # ^ |   +13 It seems that test test31 -5 6-1 3 2is incorrect because we have cycle $2, 3,2$ and the addition constraint says that the graph doesn't contain any cycle.In my solutition starting point can be any vertex, but I create graph with different from the editorial edges: from $b_i$ to $i$. The solution of Karavaev1101 is written in the same way as editorial.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +5 In Karavaev1101 solution you should change (int sum) to (ll sum) and (int a[N]) to (ll a[N]) and it will pass all the tests.
•  » » » » 3 months ago, # ^ |   +8 Actually, there is #define int long long in his code :)
•  » » » » » 3 months ago, # ^ |   +5 Yeah, sorry, didn't notice that)
 » 3 months ago, # |   0 I have joke for question C but I am not in good mood to tell. :)
•  » » 3 months ago, # ^ |   +4 Go back to the capital we shall then talk
 » 3 months ago, # |   0 Great Contest Great Editorial! thanks, everyone!
 » 3 months ago, # |   0 In problem B, the number we are expected to find should be as small as possible, and r, as big as possible. So if the input is say 11, should the answer not be 99999999800 instead of 99999999888?
•  » » 3 months ago, # ^ |   0 by adding 0's at last you are not agreeing with the maximum possible value for r , You can do better with adding 8 instead !Try it out on paper
•  » » » 3 months ago, # ^ |   0 The zeros are not included in r, those bits are only considered in the number k. If we had to maximise k, I understand, and would have made all the 0's as 8 in my number x. But if we are able to achieve a smaller value of the number x, with the same number of digits as expected, while keeping r maximum, then it does not make sense to make 99999999800 as 99999999888, right?
•  » » » » 3 months ago, # ^ |   0 This would work if we wrote a 0 in decimal as "0000" when making k. But, in the problem statement it is given that there should be no leading zeros while appending the binary of a number in k. For eg: Consider n=2: if x =98, k = 10011000 if x = 90, k = 10010 Adding zero will result in addition of a single digit in k. But if you add 8, you will add 4 digits and therefore r will be bigger. Hope this helps :)
•  » » » » » 3 months ago, # ^ |   0 "This would work if we wrote a 0 in decimal as "0000" when making k"Understood where I was wrong right after I read that line, thank you @AbishekSeshen .
•  » » 3 months ago, # ^ |   0 Remember that each digit will be converted to binary first and only then we remove N binary digits from the resulting string.So the idea is to maximize the number of binary digits, that's why we only use number 8 and 9 in our answer, because they are the only decimal digits that, when converted to binary, have 4 digits (1000 and 1001, respectively).
•  » » » 3 months ago, # ^ |   0 Thank you.
 » 3 months ago, # |   0 i am not able to understand if "4p-3" digits are removed what does this mean?
 » 3 months ago, # |   0 Can someone help me out with the Problem C, here is my solution, I used the similar idea as described in the tutorial, but used a different approach for implementaion. My approachInstead of using a single DFS, I made 2 dfs calls, one for updating the visitedPersons array for each node, then updating the happyPersons in each city and side by side checking the first two conditions. Then made another DFS call for the third condition.I dont know where I messed up. Can someone please help. My submission
 » 3 months ago, # |   +1 So many contests in the contest list but no div3 :(I am eagerly waiting for a div3 after so many difficult contests. Just to gain some confidence :)
 » 3 months ago, # |   0 can someone suggest a test case where my solution fails 88565587
 » 3 months ago, # |   +5 In problem C, if I am not incorrect, $to_1, to_2, …, to_k$ for city $v$ are the cities belonging to the subtree of the node which city $v$ belongs to. So, the third condition states that among such cities, sum of number of happy people entering each city must be less than or equal to the number of happy people entering the city $v$. Can someone please explain this condition? What I think is that for the happy people getting off at some city $to_i$, they will be counted every time they visit a city which is on their way home. So how is this repetition avoided?
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 Well, I have another approach if anyone is interested.we will have two arrays one of positive count(person who ended up happy in subtree) and one of a negative_count(person who ended up sad in subtree)apply dfs conditionint req = happiness[node] - positive_count_in_subtree; int changeable = negitive_count_in_subtree + persons[node]; if (changeable < abs(req) || changeable % 2 != abs(req) % 2) { ans = false; }  adjustYou cannot change the positive_count(because they are happy in the subtree and should be happy at this node also) but you can change the mood of a person in negitive_count and persons that ended up at this node.When You are at a node then sum the number of positive_count and negative_count in the subtree. check the condition (it is possible to get the required happiness at this node) and if it is possible then adjust the value and update the positive and negative count at that node.code 88577713
•  » » 3 months ago, # ^ |   0 Exactly, it didn't make sense to me,too
•  » » » 7 weeks ago, # ^ |   0 It's only for immediate children. They are not considering all the children in the subtree.
•  » » 3 months ago, # ^ |   0 Nobody cares what a pupil thinks, but i'll drop it anyway. I say you are correct, we are counting duplicates as well, but here's my thinking. Consider a number of happy people in node i. Now from node i, consider we can move down to three nodes, i+1,i+2,i+3. Now, the child nodes will have a "subtree sum" of their own. now assume this to be some s1,s2,s3. Now, how did we get these many people in those subtrees? It is only because they travelled through the parents node, i. So now we can see that when you add the sum of good people from all three subtrees, to the parent node, It should be strictly greater than the sum of the individual subtree sum of their chidlren. (since that node must have 0 or more happy people) so s>=s1+s2+s3.
 » 3 months ago, # | ← Rev. 3 →   0 Can someone please help why am I getting a WA on problem D on test-7. Link to my submission Thanks in advance :)UPD- I got the mistake.
 » 3 months ago, # |   0 If anyone need Detail Explanation(not a video tutorial) of C Here
 » 3 months ago, # |   0 Can anyone explain the solution of E in tutorial? I see most of the solution use trisection search. Is the tutorial also use the trisection search? Forgive my terrible understanding of the code in tutorial.
 » 3 months ago, # |   0 how max can be max achieved by removing 4.p — 3 digit from the end acc to tutorial can some one please explain
•  » » 3 months ago, # ^ |   0 In Problem B
 » 3 months ago, # |   0 In Problem A: It is said to print "4 different positive integers", but why one of those 4 positive integers can not be zero ('0')? Where is the range is mentioned? Please help me to understand the constraint. Thank you.
•  » » 3 months ago, # ^ |   0 Because 0 is not positive? :|
•  » » 3 months ago, # ^ |   0 In the question, There is the constraint of the numbers being positive.
 » 3 months ago, # |   0 Auto comment: topic has been updated by Karavaev1101 (previous revision, new revision, compare).
 » 3 months ago, # |   0 C was such a good problem even though I participated virtually and solved it 10 minutes after the contest. I did not read the question properly and missed the point that once the person becomes sad cannot become happy again.It would have been better (easier) C if this was not the condition.
•  » » 3 months ago, # ^ |   +3 How stupid, I missed that point even it was in Bold.
 » 3 months ago, # |   0 i didnt understand the solution for D. i am fairly new to STL, could anyone help?
 » 3 months ago, # |   0 Can someone please provide an edge test case for problem C. My code is failing test case 3, at only one place. Here is the link to the code : https://codeforces.com/contest/1388/submission/88578851
 » 3 months ago, # |   0 WHAT SHOULD I DO NOT TO GET RATING IN CONTEST?
•  » » 3 months ago, # ^ |   +8 Solve it virtually.
•  » » » 3 months ago, # ^ |   0 but what if i realise during contest that my rating will go down ,then what should i do not to get rating?
•  » » » » 3 months ago, # ^ |   0 Until you submit the solution for any of the problems the contest will not be rated.
•  » » » » 3 months ago, # ^ |   0 If you hit a single submission the round will become rated for u.So, before submitting decide if you want to take the shot.
 » 3 months ago, # |   0 hello, in problem B if I have n = 5 then the number must be 9 9 9 9 9 in binary : 1001 1001 1001 1001 1001 but after removing last 5 digits then it become 1001 1001 1001 100- ---- which makes it a 4 digit number, so making that 5 digit number I need to make it all 0s : 1001 1001 1001 1000 0000 but this doesn't the case. Can anyone help me with that ?
•  » » 3 months ago, # ^ |   0 How will the last digit be Zero. zero has a single digit representation in Binary.
•  » » » 3 months ago, # ^ |   0 okay but why should be 8 ?
•  » » » » 3 months ago, # ^ |   0 could you elaborate a bit .
•  » » » » » 3 months ago, # ^ |   0 because we want a number with 4 bit binary representation. That way, our number will be maximum. We have only two options for this. 8 or 9.
•  » » » » » » 3 months ago, # ^ |   0 why not nine ? I got that 0 cannot be the answer but not getting that how 8 (1000) fixes in the answer ? can you please explain the above example n = 5?
•  » » » » » » » 3 months ago, # ^ |   0 Because if we have 9 then the number won't be minimum anymore. we want the smallest number which can achieve the highest value after the erase.and if the number is going to be erase then why not let it be 8 rather than 9.
•  » » » » » » » » 3 months ago, # ^ |   0 okay I get it thank u
•  » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Why not nine? because 99...8 is smaller than 99...9 Read the problem again, They both give same answer unless n%4=0 for n=5 1001 1001 1001 1001 1001 Why not your logic? 1001 1001 1001 100,1 1001 You're gonna remove everything after the comma. So if you're gonna remove it anyway, you might as well make it as small as possible. 1001 1001 1001 100,0 1000 Notice that in this way, all digits are still 4 bit and it is also smaller than all 9's
•  » » » » » » » » 3 months ago, # ^ |   0 great explained thank u
 » 3 months ago, # |   0 Can anyone explain to me why I am getting the wrong answer on test case 3? Here's my code. Please note that n1 is for good people and n2 is for bad people. For every city, I am checking whether the number of good and bad people are greater than 0. Can anyone give to me a counterexample? Thanks in advance.
 » 3 months ago, # | ← Rev. 2 →   +1 I have an alternate solution for problem D . First transform the array b into a forest of directed trees with all edges away from the root by drawing edges from vertex x to b[x] when b[x]!=-1 (the nodes with b[x]= -1 will be the roots of the respective trees of the forest). Now, run a dfs from the root of each tree and for every node x, calculate a value say sum[x] such that sum[x] is equal to (sum of max(sum[z],0) for all children z of x) plus a[x]. The sum of sum[x] for all nodes of the forest is the required answer.Also construct an auxiliary graph such that if sum[x]>0 draw a directed edge from x to b[x], otherwise draw an edge from b[x] to x(provided b[x]!=-1) . Sort the vertices in this graph topologically to get the permutation. 88585416
 » 3 months ago, # | ← Rev. 3 →   0 I solved C a bit differently. I used the name $liv$ instead of $p$ to indicate resident number of a node. For every node $v$, I maintained a range $[L_v, R_v]$ in which it's happiness index must lie. Thus, $L_v\leq h_v\leq R_v$ For a leaf, the range is $[-liv_v, liv_v]$. Now, a node $v$ returns a different range for the residents of $v$ who started the journey from $par_v$. Notice that this range will be $[h_v, R_v]$, because if happiness in $v$ is $h_v$, then it was at least $h_v$ on its parent, with the possibility that it might be as high as $R_v$ ( Mind that one's mood gets bad only on the road AND the unhappy people never improve their mood ). Also, $R_v-h_v$ has to be even, by the definition of happiness index.For an intermediate node $u$ and $v$ $\epsilon$ $children(u)$, $[L_u, R_u] = [-liv_u+\sum_{}L_v, liv_u+\sum_{}R_v]$. Because the lower limit for $u$ can be as low as "everyone's" lower limit, including itself. Same goes for the upper limit. Return the range $[h_u, R_u]$ with appropriate checking as mentioned above. if you get a valid range at the root, it's ok. Otherwise the machine has error and print NO.My submission 88504884
 » 3 months ago, # | ← Rev. 2 →   0 For problem C, can someone provide a test case where my solution fails.I have added appropriate comments to my code for better readability.Please help! Spoiler#include #define MOD 1000000007 #define PR 998244353 #define INF INT_MAX #define endl "\n" #define newl cout<<"\n" #define mp make_pair #define mt make_tuple #define pb push_back #define ff first #define ss second #define vi vector #define pll pair #define vpi vector > #define shot(p) sort(p.begin(),p.end()) #define ulta(ord) reverse(ord.begin(), ord.end()); #define lli long long int #define sz(a) int((a).size()) #define pat(i, l, r, a) for (i = l; i < r; ++i){cout< r; --i) #define forl(i, l, r) for (i = l; i < r; ++i) #define forl(i, l, r) for (i = l; i < r; ++i) using namespace std; #include using namespace __gnu_pbds; inline lli gcd(lli a, lli b) { if(a2*pto[p] || b>2*pto[p]) { flag=1; return 0; } a>>=1;b>>=1; lli sum=0; for(auto x : v[p]) { if(!vis[x]) { sum+=dfs2(x); } } if(sum>a) { flag=1; return 0; } return (a+sum); } int main() { std::ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); lli t,a,b,c,q,h,i,j,k,n,n1,n2,n3,start,mid,end,pos,ind,min1,min2,max1,max2,lsb,sum,tot,rem,ans,prod,diff,count,flag1,temp,temp1,temp2; lli mod=1000000007, inf=LLONG_MAX , pr=998244353; for(cin>>t;t--;newl) { cin>>n>>k; flag=0; forl(i,1,n+1) cin>>pop[i]; forl(i,1,n+1) cin>>hp[i]; forl(i,1,n) { cin>>a>>b; v[a].pb(b); v[b].pb(a); } dfs1(1); forl(i,1,n+1) vis[i]=0; temp=dfs2(1); if(flag) cout<<"NO"; else cout<<"YES"; forl(i,1,n+1) { v[i].clear(); vis[i]=0; pto[i]=0; } } } 
•  » » 3 months ago, # ^ |   +1 I think your definition of $a$ and $b$ in $dfs2$ function is wrong. In $pto_v$, you have basically the number of people that have ever passed node $v$, right? Then what does pto[p]+hp[p] even mean?
•  » » » 3 months ago, # ^ |   0 pto[p] is what you have said. hp[p] is the given happiness of the city (i.e given as input).Even the tutorial has this formula. I cannot understand what is wrong with pto[p]+hp[p].Can you please elucidate a bit more?
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +1 I see. Your code comment was misleading. $a$ and $b$ were $2$ times of happy and sad people respectively, though it will eventually be true a little later. Anyways, in that case, I'd want to ask you, what does your dfs2 actually do? What I think is that it returns how many happy people have reached some node. In that case, you should return $a$, not $a+sum$ ! The $sum$ is needed to check any discrepancy at the children, but it shouldn't be added. In fact, I just submitted your code with return a; in dfs2 and got AC. Maybe you were "too lucky" to get past this many testcases.
•  » » » » » 3 months ago, # ^ |   0 Yes, I forgot to mention that a and b are twice of happy and sad people respectively (usual stupidity that I do, sorry)I was not able to enforce the necessary conditions in dfs1, so I wrote dfs2 to declutter my code.Extremely grateful to you for going through my code and pointing the error. Now, I understand what was wrong with my code.Thanks a lot again.
 » 3 months ago, # |   0 Help please Problem D https://codeforces.com/contest/1388/submission/88590473 checkler log is showing sequence have duplicates.
•  » » 3 months ago, # ^ |   0 In the 'else' in the 'while', you need to lower the indegree of brr[ind] (not only inside the if, but also in the else).
•  » » » 3 months ago, # ^ |   0 Thank You very much. You have saved me a lot of time. Thanks again
 » 3 months ago, # |   0 Can somebody explain me if there were cycles in D, how to calculate the maximum value in the cycle after removing all non cyclic elements? (in O(n))
 » 3 months ago, # |   0 can someone please explain me when will to== ancestor??
•  » » 3 months ago, # ^ |   0 I got my ans. I misunderstood.
•  » » 3 months ago, # ^ |   0 I too have this doubt,what's the use of ancestor,I made a directed graph from u->v whenever u
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 to== ancestor satisfies when we find the parent node As child, in that case we just need to skip that node and continue with next node. Ex. 1 -> 2,3,4 and 2 -> 1,5 When we check for 2 then the child of 2 is 1 which is also parent so we need to skip. For directed graph please show me your code.
•  » » » » 3 months ago, # ^ |   0 Got it.Thanks,for the explanantion.for directed graph just realised u->v will not work as root might be connected to a node with greater value which in turn can be connected to a smaller value node like 1->5->2.I was presuming it to be connected in increasing order and then forming a graph.
 » 3 months ago, # | ← Rev. 3 →   0 comment deleted by the user
 » 3 months ago, # |   0 Not able to figure out why my C submission for test case 4 is giving wrong answer. code. Can someone please help in this.
 » 3 months ago, # |   0 Can someone please explain the editorial for problem C ?
 » 3 months ago, # |   +3 Congratulations to adedalic for amazing coordination of this round!
 » 3 months ago, # |   0 Please help me clarify my doubt:In the second question (B) since we are asked to output the smallest value of x such that r is maximized after removing last n digits, so why the answer is not like this if n = 5 then x minimum x can be 99980 but the correct output is 99988 the value of k will be the same in both cases k = 100110011001100 and 99980 less than 99988 then why the answer is 99988. please explain to me if I am wrong or the question is cause i was stuck on second problem and then i lost hope and stopped attempting further.
•  » » 3 months ago, # ^ |   0 What makes you think 0 can be represented as '0000' instead of straightforwardly as '0' !
•  » » » 3 months ago, # ^ |   0 but if we cannot use zero still then our answer can end with one like for n = 5, k is same for 99981 and 99988
•  » » » » 3 months ago, # ^ |   0 No, if you use any other digit that 8 or 9 the resulting binary string will be shorter.
•  » » » » 3 months ago, # ^ |   0 Dude, binary of 1 to 7 is three digits, its that straightforward, it can't be greater than 8 or 9.
•  » » » » » 3 months ago, # ^ |   0 No, only the numbers from 4 to 7 have 3 digits in binary.
•  » » » » » » 3 months ago, # ^ |   0 My bad. The point was though that as we have to maximize 'r' we have to take digits with longest binary and 1 to 7 are only upto 3 digits in long binary, so we choose 8 and 9.
•  » » » » » » » 3 months ago, # ^ |   0 thank you guys I got it now.
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Anyway, could you please explain the editorial for problem C ? I am having difficulty in following it.
•  » » » » » » » 3 months ago, # ^ |   0 I explained it in a comment above. The comment right below mine has explanation too. See these 2 and it may answer all your questions.
•  » » » » » » » » 3 months ago, # ^ |   0 Thanks a lot ! It cleared all my doubts.
 » 3 months ago, # |   0 Hi, Would anybody help me with Question C?This is my submission. https://codeforces.com/contest/1388/submission/88520244My way of approaching the problem is the same as the editorial except I calculate number of bad people instead of the number of good people.My submission is wrong at the 27th input of the 3rd Test Case.Thanks for the help.
•  » » 3 months ago, # ^ | ← Rev. 4 →   0 Try this test case 1 3 14 2 4 8 14 4 8 1 2 1 3 The answer is "NO" Because the total sum of good people cities 2 and 3 is 12.amount of good people in city 1 is 8.the statement says that we can't increase the number of good people.(srry if my english is not so good)
•  » » » 3 months ago, # ^ |   +2 My submission is "YES". But I think the answer is "YES" alsoBecause happiness in city 1 is 14 and there is 14 people visit city 1. so number of good people = (14+14)/2 = 14 people. The number of good people leaving city 1 is 12 (14 — 2(people staying in city 1)). The total sum of good people in cities 2 and 3 is 12 which is (=) the number of good people leaving city 1. So the number of good people did not increase. Do I have any misunderstanding on the problem? Thanks for your reply and kindness.
•  » » » » 3 months ago, # ^ |   +1 Try this test 2 5 2 3 -1 3 1 2 Answer must be no. 3 bad and 2 good people at vertex 1. h[1] = -1, OK. 3 bad people will visit vertex 2. h[2] must be -3. Therefor answer is NO
•  » » » » » 3 months ago, # ^ |   0 ok Yes, that's it. I am wrong because I ignore all the vertex that has 1 connected vertex when I consider the 3rd Criteria. (All the leaf of the tree are of the size 1) But I forget that vertex 1 can be size of 1 too. Thanks a lot for your help and kindness.
 » 3 months ago, # |   0 Can anyone please explain, what's wrong with my submission if I use number of unhappy people instead of happy people for the problem C. Here is my code https://ideone.com/x1fXgM
 » 3 months ago, # |   0 Hi tried 4th problem with topological sort, WA on 7th test case. couldn't figure out. Can somebody help Your text to link here...
 » 3 months ago, # |   0 88635193 Can you explain why my code fails? my contest submission was -- 88482149, I know in the contest submission I did a calc error but the idea of my solution was the same, but after rectifying the calc error it's still showing wrong answer. Though it's written if there are multiple answers we can print any of them.
•  » » 3 months ago, # ^ |   0 for condition a==44 you have used 13 as one of the number which is incorrect because 13 is itself a prime number.
•  » » » 3 months ago, # ^ |   0 Yes I thought about it but in the question says Captain Flint guessed an integer n and asked you: can you represent it as the sum of 4 different positive integers where at least 3 of them should be nearly prime.where they said 3 of them should be nearly prime rest can be a distinct integer apart from these 3. Maybe I got the question wrong but the above lines I directly copied from the question.
•  » » » » 3 months ago, # ^ |   0 You submitted code of A in instead of B
•  » » 3 months ago, # ^ |   0 It literally tells you "wrong answer Sum of numbers is not equal to n (test case 4)". Test case 4 is n=36.
•  » » » 3 months ago, # ^ |   +3 88635193 my solution was 15 10 6 5. where 3 of them are nearly prime 15,10 and 6
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Do you know what "Sum of numbers is not equal to n" means?Edit: now I see that n=36 is fixed in that code; you should actually submit it to the correct problem.
 » 3 months ago, # |   0 I feel problem C was easy ,but it's framing was not proper.
 » 3 months ago, # |   0 I tried Problem 3 but even with the help of the tutorial I can't get it. Can someone help me? Submission: 88639704. Also I am just learning so any tips in optimizations / better practices / faster ways to write are all appreciated! Thanks!
 » 3 months ago, # | ← Rev. 2 →   0 .
 » 3 months ago, # |   0 The difficulty of problem C was just higher than expected as in normal div2 rounds bcoz of the question framing
 » 3 months ago, # |   0 Problem C was not the usual Div. 2 problem. How many of you support this!
 » 3 months ago, # |   0 Problem C. Let x be the total number of people crossing a city v. Answer is yes if: Parity of x == parity of abs(h[v]) abs(h[v]) <= x Otherwise no. Why doesn't this work?
 » 3 months ago, # |   0 hello, i am a newbie in coding and I didn't understand how problem D is connected to graphs. Can anyone tell me what's the idea/algorithm behind this question. Should I be knowing something before trying this question??
•  » » 3 months ago, # ^ |   +5 the values of b array were forming a chain(that is b was connected to the index in a and further the value of b in the new index was connected to some other index of a) and to solve such chaining question we can use graphs.
•  » » » 3 months ago, # ^ |   0 thanks, this make sense now!!
 » 3 months ago, # | ← Rev. 2 →   0 Could someone explain why does the following code for problem C gives WA ? I am not able to find any substantial difference between this code and the official solution's code.. In particular, it will be nice to have someone give me a test-case where my code fails. Also please do let me know if anything is unclear in my code; I will explain what I intend to do using that particular instruction. Code//God's Grace //#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long #define endl '\n' #define f(k,a,b) for(int k=(a);k<(b);k++) #define vi vector #define vvi vector > #define vii vector > #define pii pair #define piii pair< pair, int > #define pb(x) push_back(x) const int fix =1e9+7; const int fix_ = 998244353; const int N = 1e5+5; //list adj[N]; vector > adj; bool visited[N] = {}; int parent[N]; queue q; void yes(){cout<<"YES"<b) ? a : b;} int n,m; vi peo; vi h; vi good; bool flag=1; void dfs1(int v){ visited[v] = true; int sum=0; for(int u:adj[v]){ if(!visited[u]){ dfs1(u); sum+=good[u]; peo[v]+=peo[u]; } } if((peo[v]+h[v])%2==1){ flag= 0; } good[v] = (peo[v]+h[v])/2; if(good[v]<0||good[v]>peo[v]){ flag=0; } if(sum>peo[v]){ flag= 0; } } int32_t main(){ int g=1; g=ct(); f(i,0,g){ memset(parent,0,sizeof(parent)); cin>>n>>m; flag=1; peo.pb(0), h.pb(0); f(j,0,n){ int p; cin>>p; peo.pb(p); } f(j,0,n){ int p; cin>>p; h.pb(p); } adj.resize(n+5); good.assign(N,0); f(j,0,n-1){ int p1,p2; cin>>p1>>p2; adj[p1].pb(p2); adj[p2].pb(p1); } memset(visited,0,sizeof(visited)); dfs1(1); if(flag) yes(); else no(); peo.clear(),adj.clear(),h.clear(),good.clear(); } return 0; } `}
•  » » 3 months ago, # ^ | ← Rev. 2 →   +5 Can someone explain me what's the difference in the logic of my submission please? I have been trying to figure it out for a while but am not able to find any difference, so could someone tell me please ? In particular, my code seems to fail on the 27th test case of the 3rd test, but I am unable to view this, so could someone at least tell me what this test case is ?Thanks in advance!UPD: I found the mistake — a really stupid one. Instead of keeping sum <= good[v], I kept sum<= peo[v], a big overlook!Sorry for pestering anyone who intended to help me.
 » 3 months ago, # |   0 https://codeforces.com/contest/1388/submission/88842110 WHATS WRONg WITH ThiS?
 » 3 months ago, # |   0 how can i find answers of all the proplems ?(sorry if my English is bad)
•  » » 3 months ago, # ^ |   +5 if the editorial is not good enough you can check submissions by other competitors
 » 3 months ago, # |   +5 I think in the editorial for problem B it should read "at most 4*p-3" instead of "at least 4*p-3"
•  » » 3 months ago, # ^ |   0 "at least" is correct.
•  » » » 2 months ago, # ^ |   +5 My reasoning was incorrect, you are right. Thanks a lot, nice problem.
 » 3 months ago, # |   0 For problem C, shouldn't this give a wrong answer?? I didn't check if number of people in good mood in a city are non-negative.
 » 3 months ago, # | ← Rev. 2 →   0 What's wrong with my solution? I used BFS two times. 1) Operate on the nodes that are +ve or become +ve while traversal, from top to bottom. Mark them.2) Operate on the remaining negative nodes. From bottom to top
 » 3 months ago, # |   +5 can anyone check and help me understand why memory limit is exceeded in my solution for problem C 89311627
•  » » 3 months ago, # ^ |   +5 Damn, i forgot to clear the global vector
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 yeap )
 » 2 months ago, # |   0 In 1388C — Uncle Bogdan and Country Happiness, consider the 3rd condition:gto1+gto2+…+gtok ≤ gv, where to1, to2, …, tok are the cities where the resident can move out of the city v on the way home.Shouldn't we compare gto1+gto2+…+gtok with number of happy (in good mood) people leaving the city v instead of comparing gto1+gto2+…+gtok with gv (number of people in a good mood who visit the city v = number of people in good mood passing through city v + number of people in a good mood who live in city v), to ensure no one becomes happy during the journey.
 » 6 weeks ago, # | ← Rev. 3 →   +5 Nice problems except for the long essays here
 » 4 weeks ago, # | ← Rev. 2 →   0 So the solution I came up with for C for almost the same as the solution except I used number of people with bad mood instead of good mood for calculations. But, I got WA on test 3. It seems my formula matches with the solution if you replace bad mood with (total people-good mood) etc. Can someone kindly help identify what I'm doing wrong here?Here's my code: 93412641