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'.
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.
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.
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.
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.
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: SticksYou 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 RangeYou 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 DivisionGiven 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: SequenceGiven 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.
No comments:
Post a Comment