Agreed. If not for the notes, I probably would have wasted a lot of time understanding the statement.

was writing " was made it a bit annoying" on purpose? If so, it's funny. If not, it's sad XD

Lengthy background but interesting problems.

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.

do yoga it will help you

Your solution fails on that test case:

Your 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}$$$

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:

Input

3

-2 -1 4

-1 1 2

Output

8

3 2 1

But your output is:

5

1 3 2

Hope my reply could help you.

hoping it won't let us down

I solved this problem using topological sort. You can check my submission.

here's my AC submission with topological sort -> 88536305

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

In fact,the solution by Karavaev1101 is topological sort,though it's hard to tell.

Hey, The ratings have arrived. You can see them if you want.

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;
	}
}

``

did u know, you wasted 61 seconds in this counting!! lol :>

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.

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.

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.

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

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

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)$$$.

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 xD
You 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.

thanks a lot!!

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:

from 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

@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.

1. Your variables are not initialized: ll pos,neg;
2. You don't need to check case n == 1 separately.
3. It's better to check the whole value for mod 2: (sum-abs(h[ind]))%2==0

https://codeforces.net/contest/1388/submission/88541430

'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.

Use spoiler for posting your code

you if conditions are wrong recheck them

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

So that negative values don't add up at any vertex.

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

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$$$

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.

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.net/contest/1388/submission/88556412

#include<bits/stdc++.h>
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<tm;i++){
			s[n-i-1]='8';
		}
		if(tp>=1){
			s[n-tm-1]='8';
		}
		cout<<s<<"\n";
	}
	return 0;
}

in this code i reserved a contiguous memory space of N for my string at very first. and look it only took 30ms to execute while your code did same in ~1000ms.

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.

Then try D with dfs. I liked it better.

no it is not.

we are only starting from the leaves. and that is the logic.

Explain how is your expected result is 9?

It seems that test

is 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 Karavaiev is written in the same way as editorial.

Go back to the capital we shall then talk

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

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).

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

int 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;
}

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

Exactly, it didn't make sense to me,too

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.

Because 0 is not positive? :|

How stupid, I missed that point even it was in Bold.

Solve it virtually.

How will the last digit be Zero. zero has a single digit representation in Binary.

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?

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).

What makes you think 0 can be represented as '0000' instead of straightforwardly as '0' !