MUJ IEEE CODEATHON (Official)

Solution for CHOSR:
CODE:https://pastebin.com/RNS0rY1s

As the sweetness of first chocolate has to be smaller than or equal to second chocolate so this
gives us an idea to sort the chocolates.
Here you can sort the chocolate by the first parameter that is the sweetness.
Next condition says that if a chocolate,say A,B where A’s sweetness <= B’s sweetness then we can pick these two chocolates if A’s richness< B’s richness.
So by sorting and then applying greedy will not work,solution is to find the Longest Increasing Subsequence after sorting the chocolates by their first parameter(sweetness) and then find LIS by second parameter that is richness.As the constraints are 10^5 so O(nlogn) LIS approach will work.

Solution for GUNSHOT:

When the gunman fires two bullets it can only hit two distinct houses,the gold number of both the houses will get reduced by 1.So if a bullet is hit at a house infinte times the gold value of it will become smaller than zero,that we don’t want.So now we need to think of a case where we have all houses with goldnumber as zero,That happens when two conditions are matched.

  1. The sum of goldnumber of all the houses should never be odd.You can try it with few small examples.
  2. The goldnumber of every house has to be <= sum/2.

Now if this is possible then answer is yes,you can make gunman happy.

This is an observative problem.

Solution:
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
ll n,m,i;
cin>>n;
ll arr[n];
ll sum=0;
for(i=0;i<n;i++)
{
cin>>arr[i];
sum=sum+arr[i];
}
if(sum%2!=0)
{
cout<<“NO”;
return 0;
}
for(i=0;i<n;i++)
{
if(arr[i]>sum/2)
{
cout<<“NO”;
return 0;
}
}
cout<<“YES”;
return 0;
}

Solution for CHOZOZA:

It’s easy to calculate how many Toblerone they will buy:a=(n+m)/2.

Also it’s optimal to transfer Toblerone such that the remainder modulo k of the receiving part will turn to be exactly zero.

So the answer is ⟨a,min(k−(n%k),k−(m%k))⟩.
Thats it!!

Solution:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll x,y,z;
cin>>x>>y>>z;

ll cnt=0;
cnt=x/z;
x=x-(z*cnt);
cnt=cnt+y/z;
ll d=y/z;
y=y-(d*z);

ll a=0;
if(x+y>=z)
{
	a=min(x,y);
	ll d=x+y;
	d=d-z;
	cnt=cnt+(x+y)/z;
	cout<<cnt<<" "<<a-d<<endl;
}
else
{
    cout<<cnt<<" "<<0<<endl;
}

return 0;

}

Solution for SACOWS:
CODE:https://pastebin.com/jnWpAf9H

Actually, it is not necessary to enumerate all possible pairs of 1 = i<j = N. The only
cows that can form a sacred pair with cows i, is cow ai. Therefore, it is enough to just
enumerate all 1 = i = N, then count the ones that satisfy aai = i. Note that in this approach
each sacred pair is counted twice, thus we have to divide the count by 2 to obtain the final
answer. The time complexity of this approach is O(N), which will be within the time limit
even when N = 10^5.

Solution for MOVIES:
CODE:https://pastebin.com/YqaCvUhy

You can try to fill the seats in any order and observe that if you add an extra seat
the hall row is now circular and it reduces to a simple combinatorial observation. Now the number of ways such that n+1-th seat becomes empty is the answer.
For each seat there is
((2*(n+1))^m * (n+1-m))/n+1
ways such that this seat becomes empty.
The above formula can be calculated using exponentiation and remeber to output the answer in the given modulo.