This is my first attempt at writing an editorial, so please correct me if there are any errors and suggest improvements.
General Comments about the Contest:
There
were 5 problems in all. I felt that the problems were arranged in the
increasing order of difficulty (as can also be seen by the final rank
list). The conduction of the contest was not so good as the server
crashed multiple times throughout the competition.
U can
download the complete Problem Set here:
icpcquestions.docx
For solutions to the problems, i have used my C++ Competition Programming Template which u can find
here. I have not included them in the solutions posted here for the sake of simplicity.
The Problems:
A: Pair Socks
Given
a string containing a series of characters 'R', 'G', 'B' and 'W'
representing red, green, blue and white socks, find if each of these can
be grouped in pairs of same colour.
Solution:
A
very trivial problem. Count the number of occurrences of each character.
If all of the counts are divisible by 2, then it is possible - print
'YES'. Otherwise print 'NO'.
int main()
{
int t,r=0,g=0,b=0,w=0;
string s;
t=GI;
while(t--)
{
r=0;g=0;b=0;w=0;
cin>>s;
REP(i,0,s.size())
{
if(s[i]=='R') r+=1;
if(s[i]=='G') g+=1;
if(s[i]=='B') b+=1;
if(s[i]=='W') w+=1;
}
if(r%2==0 && g%2==0 && b%2==0 && w%2==0)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
B: Sticks
You
have N sticks - the length of the ith stick being L[i]. You also have M
3-dimensional boxes - the length, breadth and height of the jth box
being A[j], B[j] and C[j]. What is the maximum number of sticks which
can fit in the boxes? A stick can be fit in a box if it can be placed
within it without bending or cutting it. A box can hold any number of
fitting sicks (assume that the sticks do not intersect each other).
Solution:
Again
a trivial problem, but had a small trick in the implementation. Since a
box can hold any number of fitting sticks, we can just take the largest
box and check whether we can put each of the sticks into it oriented
across the body diagonal (ie) from (0,0,0) to (A[i],B[i],C[i]). The
trick in this problem is that A[i]*A[i] + B[i]*B[i] + C[i]*C[i] would
overflow if u were using integer values. So if u declare them as
long/long long u will be fine.
int main()
{
int t, n, m, cnt;
LL l[100005],x,y,z,val;
t=GI;
while(t--)
{
cnt=0;val=0;
n=GI; m=GI;
REP(i,0,n)
{
l[i]=GI;
}
REP(i,0,m)
{
x=GI; y=GI; z=GI;
val = max(val,x*x+y*y+z*z);
}
REP(i,0,n)
{
if(l[i]*l[i]<=val)
cnt++;
}
printf("%d\n",cnt);
}
return 0;
}
C: Sum Range
You
are given N numbers a[1..N] and 2 other integers L and H. Count the
number of tuples (i,j,k) satisfying i < j < k and L <= a[i] +
a[j] + a[k] <= H.
Solution:
Probably the
trickiest problem of them all (not toughest), both to implement as well
as to understand why the complexity of the solution is O(n^2) inspite of
having three nested for loops.
Firstly, we can see that order of
the original array does not matter (since even if the order is changed,
the three elements can be rearranged to match their order in the
original array so that the i<j<k condition is satisfied). So we
sort the original array. Now, we can reduce the problem statement to
iterating across all possible i and k (ie) from left and right ends of
the array and finding the number of possible j indices for each of them.
This might sound like an O(n^3) solution, but we avoid that by
maintaining the lowest value j can take and the highest value j can
take - this reduces the complexity to O(n^2).
A simpler solution to this problem in O(N^2logN) is also possible using binary search, which also passed the time limit.
int main()
{
int t, n, l, h, a[1005],j,p;
LL cnt;
t=GI;
while(t--)
{
cnt=0;
n=GI; l=GI; h=GI;
REP(i,0,n)
a[i]=GI;
sort(a,a+n);
REP(i,0,n-2)
{
j=i+1;
p=i+1;
for(int k=n-1;k>i+1;k--)
{
for(;j<k;j++)
{
if(a[i]+a[j]+a[k]>=l)
break;
}
for(;p<k;p++)
{
if(a[i]+a[p]+a[k]>h)
break;
}
if(p>i+1)
p--;
if(a[i]+a[j]+a[k]>=l && a[i]+a[p]+a[k]<=h && j<=p && j>i)
cnt+=(p-j+1);
}
}
printf("%lld\n",cnt);
}
return 0;
}
D: Team Division
Given
a list of teams and their perceived rival team list, find the number of
ways that u can divide them into two groups such that no team is in the
same group as its rival team.
Solution:
There was a
small confusion in the statement "The rivalry relation is not
symmetric". It means that in the given input data, a is a rival of b
doesn't mean that b will be a rival of a. However, when we assign teams
we need to make sure that if either a is a perceived rival of b or b is a
perceived rival of a, both shouldn't be in the same site. This can be
handled by simply adding a to b's list of rivals and b to a's list of
rivals if either one perceives the other as a rival.
Then, we can
perform a DFS on all the nodes to separate them into bipartite
components (ie) components in which one group should be in a different
site than the other. The answer would then be 2^(number of components).
When performing the DFS, if we see that such a bipartite division is not
possible, then no division is possible. So we can output '0' in that
case.
int a[20005],b[20005],cnt,num,val;
pair<int,int> top;
set<int> v[20005];
bool seen[20005];
LL mod_exp(int cnt)
{
if(cnt==1)
return 2;
if(cnt%2==0)
{
LL temp=mod_exp(cnt/2);
return (temp*temp)%MOD;
}
else
{
LL temp=mod_exp(cnt-1);
return (2*temp)%MOD;
}
}
int main()
{
int t, n;
t=GI;
while(t--)
{
memset(a,-1,sizeof a);
memset(b,-1,sizeof b);
memset(seen,false,sizeof seen);
cnt=0;
n=GI;
REP(i,0,n)
v[i].clear();
REP(i,0,n)
{
num=GI;
REP(j,0,num)
{
val=GI;
if(v[i].find(val)==v[i].end())
v[i].insert(val);
if(v[val].find(i)==v[val].end())
v[val].insert(i);
}
}
REP(i,0,n)
{
if(seen[i]) continue;
seen[i]=true;
cnt++;
a[i]=cnt;
stack<pair<int,int> >s;
TR(it,v[i])
{
s.push(mp(*it,1));
}
while(!s.empty())
{
top=s.top();s.pop();
if(seen[top.first]) continue;
seen[top.first]=true;
TR(it,v[top.first])
{
if(seen[*it]) continue;
if(top.second==0)
{
if(a[*it]!=-1)
{
printf("0\n");
goto next;
}
s.push(mp(*it,1));
b[*it]=cnt;
}
if(top.second==1)
{
if(b[*it]!=-1)
{
printf("0\n");
goto next;
}
s.push(mp(*it,0));
a[*it]=cnt;
}
}
}
}
printf("%lld\n",mod_exp(cnt)); // second time
next:;
}
return 0;
}
E: Sequence
Given
a sequence S of '0' and '1' of length N, a subsequence of S is obtained
by omitting some elements of S without changing the order of the
remaining elements of S.
Given a subarray of a sequence S starting
from some position 'a' and ending at some position 'b' (1 <= a <=
b <= N), both inclusive, denoted by S(a,b), you have report the
length of longest non-decreasing subsequence of S(a,b). By
non-decreasing, we mean that a '0' never appears after a '1' in the
subsequence.
1<=Number of elements in the array<=10000, 1<=Number of queries<=100000.
Solution:
This
problem required the use of a data structure called a segment tree. A
segment tree is a data structure which allows u to do range queries like
maximum, sum, frequency etc. in an interval in O(logN) time with O(N)
pre-processing. Read the description of how to construct this here -
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
Now, the solution of the problem.
Maintain three things in the segment tree - a, z and o.
a - length of longest subsequence in an interval
z - number of zeros in an interval
o - number of ones in an interval
We can combine the segments as follows during initialization:
a[n] = max(a[2*n] + o[2*n+1], z[2*n] + a[2*n+1])
z[n] = z[2*n] + z[2*n+1]
o[n] = o[2*n] + o[2*n+1]
Similar query function.
#define MAXN 1000000
struct rsq
{
int a;
int o;
int z;
}tree[MAXN];
string s;
void init(int n, int b, int e)
{
if(b==e)
{
if(s[b]=='0') tree[n].a=tree[n].z=1,tree[n].o=0;
else tree[n].a=tree[n].o=1,tree[n].z=0;
}
else
{
init(2*n,b,(b+e)/2);
init(2*n+1,(b+e)/2+1,e);
tree[n].o = tree[2*n].o + tree[2*n+1].o;
tree[n].z = tree[2*n].z + tree[2*n+1].z;
tree[n].a = max(tree[2*n].a+tree[2*n+1].o,tree[2*n].z+tree[2*n+1].a);
}
}
rsq query(int n, int b, int e, int i, int j)
{
if(i<=b && j>=e)
return tree[n];
int mid=(b+e)/2;
if(j<=mid)
return query(2*n,b,mid,i,j);
if(i>mid)
return query(2*n+1,mid+1,e,i,j);
rsq x,y,ans;
x = query(2*n,b,mid,i,j);
y = query(2*n+1,mid+1,e,i,j);
ans.o = x.o + y.o;
ans.z = x.z + y.z;
ans.a = max( x.a+y.o, x.z+y.a );
return ans;
}
int main()
{
int n,q,t,x,y;
t=GI;
while(t--)
{
n=GI;
REP(i,0,n+1) tree[i].a=tree[i].o=tree[i].z=0;
cin>>s;
s=" "+s;
init(1,1,n);
q=GI;
REP(i,0,q)
{
x=GI; y=GI;
printf("%d\n",query(1,1,n,x,y).a);
}
}
return 0;
}
Feel free to leave any comments, suggestions, alternative solutions in the comments below.
![x := \sum_{i} a_i \frac{N}{n_i} \left[\left(\frac{N}{n_i}\right)^{-1}\right]_{n_i}](http://upload.wikimedia.org/math/7/9/0/7900728a23224d40167ad92714699ac2.png)