Will be helpful if someone gives the solution for this problem
Code
'''Author- Akshit Monga'''
t=int(input())
for _ in range(t):
a,b,c=map(int,input().split())
sum=a+b+c
if sum%3==0:
val=sum//3
if a<=val and c<=val:
ans=val
elif max(a,c)>val and min(a,c)<=val:
b-=(val-min(a,c))
b=max(0,b)
ans=(b+max(a,c))//2+(b+max(a,c))%2
else:
ans=min(a,c)
elif sum%3==1:
val1=(sum-1)//3
val2=val1+1
if max(a,c)<=val2 and min(a,c)<=val1:
ans=val2
elif max(a,c)>val2 and min(a,c)<=val1:
b-=(val1-min(a, c))
b=max(0,b)
ans=(b+max(a,c))//2+(b+max(a,c))%2
else:
ans=min(a,c)
else:
val1=(sum-2)//3
val2=val1+1
if a<=val2 and c<=val2:
ans=val2
elif max(a,c)>val2 and min(a,c)<=val2:
b-=(val2-min(a, c))
b=max(0,b)
ans=(b+max(a, c))//2+(b+max(a,c))%2
else:
ans=min(a,c)
print(ans)
It can be shortened but I’ve kept every case different because it is easier to analyze it in that way.
If you’re unable to understand any case, ping me.
Edit:
Shortened Code
'''Author- Akshit Monga'''
t=int(input())
for _ in range(t):
a,b,c=map(int,input().split())
sum=a+b+c
val1=(sum)//3+(sum%3>1)
val2=(sum)//3+(sum%3>0)
if max(a,c)<=val2 and min(a,c)<=val1:
ans = val2
elif max(a, c)>val2 and min(a,c)<=val1:
b-=min(b,(val1 -min(a, c)))
ans=(b+max(a,c))//2+(b+max(a,c))%2
else:
ans=min(a,c)
print(ans)
@akshitm16
Thanks for providing the code but I was looking for the logic and the procedure for solving the problem. Tell me what’s the Logic behind it and I think I can implement it by myself.
I just scanned the problem statement and found out keywords such as "divide into groups " with some conditions ofc. I also saw that contraints are’nt that tight. In cases like these its beneficial to think in terms of dp and more specifically if its a “divide into groups” type of problem, its much better to straight away think of knapsack. Obviously you should modify it according to constraints but the inherent basic idea remains same
Okay the logic goes here-
No restrictions
sum=a+b+c
ans= \lfloor \frac{sum}{3} \rfloor + (sum \% 3>0)
Case1
In case sum is divisible by 3, we’ll just divide it into three equal parts.
ans = \dfrac{sum}{3}
Case2
In case the sum leaves a remainder 1 when divided by 3, the distribution will be x, x, x+1 where sum= 3 \cdot x+ 1.
ans=x+1
Case3
In case the sum leaves a remainder 2 when divided by 3, the distribution will be x, x+1, x+1 where sum=3 \cdot x + 2.
ans=x+1
With restrictions
Now, we have restrictions that a type students and c type students shouldn’t be together.
Case1
So, first case is sum is divisible by 3. Our first goal would be to distribute the sum evenly among the three groups. So, we’d try to put \dfrac{sum}{3} students in each class.
Case1.1
Let’s denote val = \dfrac{sum}{3} .
If a<=val and c<=val. We will keep al a's together in one room and all c's together in another room and and flexibly distribute b in such a way the count in each room sums upto val.
So, ans is this case is nothing but val.
Case 1.2
Let’s denote val = \dfrac{sum}{3} .
Say, one of a or c is greater than val and the other one is less than or equal to val.
Formally, max(a, c)>val and min(a,c)<=val .
For demonstration, a>val and c<=val. Now since c is less than or equal to val, we will keep all c's together and we’ll still have some space in c's room. So, we will put maximum b's in c's room as much as we can. We can put (val-c) b's in c's room. Now, if the value of b< (val-c) . Then the max b's we can put in c's room is b itself.
Formally, b-=min(b,(val -c))
Now, we are left with 2 rooms. Students of type c are allotted and we are left with a+b students and 2 rooms and we have no restrictions now since c's have already been separated. We will divide evenly a+b in two rooms.
Formally, ans=\lfloor \frac{a+b}{2} \rfloor+(a+b) \% 2 .
In case b>=(val-c), ans=\lfloor \frac{a+b}{2} \rfloor+(a+b) \% 2 = val.
Else, ans=\lfloor \frac{a+b}{2} \rfloor+(a+b) \% 2 > val.
Case 1.3
Okay, now the case is a>val and c>val. In this case take the min(a,c) and put in separate class and distribute (max(a,c)+b) evenly in 2 rooms.
Formally, ans=min(a,c)
It can be easily proven that even distribution of max(a,c) and b in 2 rooms will always be less than val and hence the max out of three would be min(a,c) only. I’ll leave the proof to you. It’s just basic in-equations.
Cases 2 and 3 with restrictions is very similar to Case 1 with restrictions and hence I’ll leave that to you.
1 Like
Thanks, buddy …for your effort.
1 Like