FLAGS - Editorial

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

4 Likes

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

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

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

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

1 Like

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

1 Like

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;

}

1 Like

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

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

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

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…

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

#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 :confused:

@dpraveen :diamonds::diamonds: understood my mistake…thanx…

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

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

understood my mistake @drpraveen … thanx

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

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?

1 Like

hahaha lucky you

1 Like