FLAGS - Editorial

dpraveen · June 23, 2014, 12:47am

PROBLEM LINK:

Practice
Contest

Author: Konstantin Sokol
Tester: Tasnim Imran Sunny
Editorialist: Praveen Dhinwa

DIFFICULTY:

CAKEWALK

PREREQUISITES:

simple combinatorics.

PROBLEM:

Given following 5 patterns of a flag.

112233
112233
112233

111111
222222
333333

112222
112222
113333

122223
111333
144443

111222
333222
333444

Your need to count the number of different well-painted flags. We call a flag well-painted if it’s made according to the following algorithm:

Pick up one of the flag patterns considered above;
Paint each connected component in an color encoded by an integer from 1 to N. Different colors are encoded with different integers.
If two different connected components share a common side(not corner), than they must be painted in different colors.
In any other case they can be painted in both equal and different colors.

QUICK EXPLANATION

For each flag, we can find out the number of different well painted flags. The flags are given in such a way that no two flags in the 5 flags
will be similar to each other. So you can solve the problem independently for each flag.
For a single flag, find number of ways of painting that flag using N colors.

EXPLANATION

For each flag, we can find out the number of different well painted flags independently because the shape of the flags are in such a way
that no two flags in the above given 5 flags will be similar to each other in any possible painting.
So you can solve the problem independently for each flag.

Flag 1
112233
112233
112233

We can use minimum 2 colors to make the flag well painted.
112211
112211
112211

So here we can paint the first connected component by using any of the N possible colors. Then for second connected component, total possible
colors available will be N - 1 because we can not use the color of first connected component. Then for third connected component, total
possible colors available will also be N - 1 because we can not use color of second connected component.

Hence number of ways = N * (N - 1) * (N - 1).

Flag 2
111111
222222
333333

We can use minimum 2 colors to make the flag well painted.
111111
222222
111111

So here we can paint the first connected component by using any of the N possible colors. Then for second connected component, total possible
colors available will be N - 1 because we can not use the color of first connected component. Then for third connected component, total
possible colors available will also be N - 1 because we can not use color of second connected component.

Hence number of ways = N * (N - 1) * (N - 1).

Flag 3
112222
112222
113333

We can use minimum 3 colors to make the flag well painted.
112222
112222
113333

So here we can paint the first connected component by using any of the N possible colors. Then for second connected component, total possible
colors available will be N - 1 because we can not use the color of first connected component. Then for third connected component, total
possible colors available will also be N - 2 because we can not use color of first and second connected component.

Hence number of ways = N * (N - 1) * (N - 2).

Flag 4
122223
111333
144443

We can use minimum 3 colors to make the flag well painted.
122223
111333
122223

So here we can paint the first connected component by using any of the N possible colors. Then for second connected component, total possible
colors available will be N - 1 because we can not use the color of first connected component. Then for third connected component, total
possible colors available will also be N - 2 because we can not use color of first and second connected component. Then for the fourth connected
component, total numbers of colors available will be N - 2 because we can not use first and thrid connected component.

Hence number of ways = N * (N - 1) * (N - 2) * (N - 2).

Flag 5
111222
333222
333444

We can use minimum 3 colors to make the flag well painted.
111222
333222
333111

So here we can paint the first connected component by using any of the N possible colors. Then for second connected component, total possible
colors available will be N - 1 because we can not use the color of first connected component. Then for third connected component, total
possible colors available will also be N - 2 because we can not use color of first and second connected component. Then for the fourth connected
component, total numbers of colors available will be N - 2 because we can not use second and thrid connected component.

Hence number of ways = N * (N - 1) * (N - 2) * (N - 2).

Final answer

For flag 1: N * (N - 1) * (N - 1).
For flag 2: N * (N - 1) * (N - 1).
For flag 3: N * (N - 1) * (N - 2).
For flag 4: N * (N - 1) * (N - 2) * (N - 2)
For flag 5: N * (N - 1) * (N - 2) * (N - 2)

Pseudo code

long long n;
read n
long long ans = 2*n*(n-1)*(n-1) + n*(n-1)*(n-2) + 2*n*(n-1)*(n-2)*(n-2);
print ans

Complexity
We just need constant amount of addition and multiplication operations. Hence the time complexity will be O(1).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

skysarthak · June 23, 2014, 12:54am

i reduced the sum of the equations and did like this but i keep getting WA although the test cases run fine. can anyone tell me my mistake here

#include<iostream>
using namespace std;

int main()
{
    long int n,t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cout<<n*(n-1)*(2*n*n - 5*n + 4)<<endl;
    }
    return 0;
}

karankapoor · June 23, 2014, 1:01am

i used the code below… but i could not store the value of the large integer generated… what to do ? i have marked the error in form of comments…

	#include<stdio.h>
	int fact(int x)
	{
	 int f;
	 if(x==1)
		return 1;
	 else
		f=x*fact(x-1);
	 return f;
	}
	main()
	{
	 int t,n,i;
	 long long int y;
	 scanf("%d",&t);
	 if(t>=1&&t<=10000)
	 {
		for(i=0;i<t;i++)
		{
		 scanf("%d",&n);
		 if(n>=1&&n<=10000)
		 {
			if(n==1)
			{
			 printf("0\n");
			}
			else if(n==2)
			{
			 printf("4\n");
			}
			else if(n==3)
			{
			 printf("42\n");
			}
			else if(n==4)
			{
			 printf("240\n");
			}
			else
			{
			 y=(fact(n)/(fact(4)*fact(n-4)))*240+(fact(n)/(fact(3)*fact(n-3)))*42+(fact(n)/(fact(2)*fact(n-2)))*4;
			 printf("%lld\n",y);  // error is here..!!
			}
		 }
		}
	 }
	 return 0;
	}

skysarthak · June 23, 2014, 1:02am

why long long n…even int n should work…won’t it ?

itachiuchia · June 23, 2014, 1:04am

Here are two soln’s that are almost same…

1 is ac :-- http://www.codechef.com/viewsolution/4128188 …

nd other shows wa :-- http://www.codechef.com/viewsolution/4129571 …

the one that shows wa is built with respect to constraints…
the constraints that shows max value of n as 10000 is wrong(i suppose correct me if i m wrong)…

Plz tell me the error in my code it cost me 3 WA’s

Thnx for ur help

dpraveen · June 23, 2014, 1:07am

if you use int, then don’t forget to typecast the right expression in line "long long ans = "

mon95 · June 23, 2014, 1:08am

It doesn’t print the right answer for large n(say, 10000 or 5000). Do check.

Here is the correction. ( Explicit type conversion to long long int is needed)
Hope it helps.

#include
using namespace std;

int main()
{
long int n,t;
cin>>t;
while(t–)
{
cin>>n;
cout<<(long long int)n*(n-1)(2nn - 5n + 4)<<endl;

}
return 0;

}

dpraveen · June 23, 2014, 1:09am

“the constraints that shows max value of n as 10000 is wrong(i suppose correct me if i m wrong)…”

You are wrong. Constraints are correct.

dpraveen · June 23, 2014, 1:09am

plz write a bruteforce check with setters solution and figure out yourself

azix6 · June 23, 2014, 1:11am

Since 1<=n<=10000, long int will not suffice the range. You need to do it either long long or unsigned long long.

skysarthak · June 23, 2014, 1:13am

i had the same prob…i tried to submit the code 4 times with int n, WA each time, now when i submitted the solution with long long int n in the practice sec it gives correct ans…

dpraveen · June 23, 2014, 1:24am

@skysarthak, you can get WA if you use int n, See the editorial last section.

tt22 · June 23, 2014, 1:42am

#include<stdio.h>

int main()
{
int t;
int n;
long long int ans;
scanf("%d",&t);
while(t–)
{
scanf("%d",&n);

           ans= n*(n-1)*(n-1)*2 + n*(n-2)*(n-1) + n*(n-1)*(n-2)*(n-2)*2;
           printf("%lld\n",ans);
 }
 return 0;

}
^this was my code not accepted

this is my code which has got ACed
#include<stdio.h>

int main()
{
int t;
long long int n;
long long int ans;
scanf("%d",&t);
while(t–)
{
scanf("%lld",&n);

           ans= n*(n-1)*(n-1)*2 + n*(n-2)*(n-1) + n*(n-1)*(n-2)*(n-2)*2;
           printf("%lld\n",ans);
 }
 return 0;

}
cost me the whole cook off

skysarthak · June 23, 2014, 1:46am

@dpraveen understood my mistake…thanx…

skysarthak · June 23, 2014, 1:54am

@tt22 i did the same blunder 2day…the prob is that when you pass ‘n’ as only int in the expression, it evaluates to generate an int ans. This works for small cases but for n=10,000 the ans evaluated will be much bigger…if you had typecast the result of expression as long long int then even your first solution sould have worked…

skysarthak · June 23, 2014, 1:56am

@tt22 in the 2nd solution as n is already passed as long long int the expression is evaluated to long long int and hence it works…

itachiuchia · June 23, 2014, 2:02am

understood my mistake @drpraveen … thanx

bhuvanrawal · June 23, 2014, 4:22pm

Hi,
can anyone tell me why my code gave WA? its exactly same as authors submission and other submissions…
link: http://www.codechef.com/viewplaintext/4128079

ruddradev · June 24, 2014, 6:14pm

I Managed to get all the counts wrong. And fortunately for me, the polynomial for the answer was same as mine. That was embarrassing, but lucky me. :D.

My Answer- Flag 1=n(n-1), 2=n(n-1), 3=n(n-1)(n-2), 4=n(n-1)(n-1)(n-2) 5=n(n-1)(n-1)(n-2)

Polynomial= (n^2-n)(2n^2-5n+4)

What are the chances of that happening?

ayushtomar · June 24, 2014, 7:55pm

hahaha lucky you