Coding GC | 25th Jan | Saturday

[Sushant]

Dear All,

The Web and Coding Club (WnCC) of the Students' Technical Activities Body
(STAB) is organizing the 5th competition in the series of competitions for
the Technical General Championship (Tech GC).

Following are the details of the competition :
Competition type : Programming Contest (ACM-ICPC format)
Date : 25th Jan 2014, Saturday
Time : 09.00 PM - 12.00 AM
Venue : New Software Lab
Reporting Time : 08.30 PM

Each hostel can send at max 3 teams comprising of 3 members each.

Students interested in participating in the competition  contact your
respective hostel tech Councilors or Secretaries. For further details
about the competition contact the undersigned.

Sushant Hiray,
Manager WnCC

[pathankhan salman]

Can you make the questions public? To outside Insti once the GC is over?

Thank you,

Salman Khan,

+919971036594.

My details : About me

--
--
The website for the club is http://stab-iitb.org/wncc
To post to this group, send email to wncc...@googlegroups.com
 
---
You received this message because you are subscribed to the Google Groups "Web and Coding Club IIT Bombay" group.
To unsubscribe from this group and stop receiving emails from it, send an email to wncc_iitb+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Piyush Kumar]

@salman : The contest will be held on SPOJ, and problems will be made publically available after the contest. Also, editorials will be posted on this thread.

Regards,

Piyush Kumar

[Shantanu Thakoor]

Are freshies allowed to participate in this?
Or is it going to be too advanced for us to have a chance of getting?

[Piyush Kumar]

Questions are of various difficulty level, knowledge of CS 101 would suffice for the easy ones.

Only constraint is that maximum 9 people (3 teams) can come from each hostel.

Regards,

Piyush Kumar

[Shantanu Thakoor]

Okay, thanks :)
H15 doesn't really have a proper tech council, is there anyway I could register online or something? I have a team of 3 ready.

[Guna Prasaad]

Even during the discussion meet of the GC, we did not have representatives from hostel 15. I am not very well informed about the status of hostel 15 council. Try to find out from your hostel management by Thursday. Otherwise contact me (+91-9920147551) We'll register your team separately.  

[Chandra Maloo]

Hey Shantanu,
Already few teams from H15 have given their names for GC.
If you want to go with a team contact any of the Tech Co.s
Btw there is already a post regarding it on hostel group:
https://www.facebook.com/groups/670306766330802/

Regards,
Chandra Maloo,
Computer Science and Engineering Dept.
IIT Bombay.
Contact No. +919028313958

[Piyush Kumar]

The contest problems are available on SPOJ

http://www.spoj.com/problems/RLSIGNQ/

http://www.spoj.com/problems/RLCAT/

http://www.spoj.com/problems/RLCIPHER/

http://www.spoj.com/problems/RLTOUR/

http://www.spoj.com/problems/RLTHREE/

The winners were Aamod, Nisheeth and Hardik (only team that solved all problems), second place went to Balaji, Bijoy and Shashwat (4 problems) and third place to Aditya, Nikunj and Omkar (4 problems).

Editorials :

Robert Langdon & Sign Queue

Difficulty : Cakewalk

Category : ad-hoc, implementation

Solution :

Total amount of signatures that he needs to do it the sum of attendance at each signing. Call this sum S. If a refill can sign for K people, then number of refills needed are ceil(S/K), where ceil(N) denote smallest integer larger than or equal to N.

Robert Langdon & Cipher

Difficulty : Easy

Category : Simple Maths

Solution :

If the number is already negative, cannot subtract any more.

If the number is >=0, then here are worked out answers for a few values

0 -4

1 -3

2 -2

3 -4

4 -4

5 -3

6 -4

7 -4

8 -4

9 -4

Note that we have four consecutive values 6-9 for which answer is minimum possible (-4). For any number >9, since only 3 or 4 is subtracted, we will definitely pass through the range 6-9 (if you are not convinced then prove by induction with base cases 6 -9). Hence for numbers >9 you can always get to -4.

Robert Langdon & Florence

Difficulty : Easy-medium

Category : Sorting

Solution :

Consider the last value in array C (number of dolls before this that can contain this). For the last doll, this will be the number of dolls that are bigger than or equal to this doll "among all dolls" (because all other dolls are before it). Thus we can find the doll that must be at the last position in the beautiful arrangement (C[n]+1 th largest doll).

Then remove this doll from the list of dolls and do the same for (n-1)th position.

Hence complexity O(N^2). This was sufficient to get accepted.

Optional :

But it can be further improved to O(N log(N)) using the data structure called Segment Trees.

Each segment will contain number of dolls in this range that are alive. Using this information, the C[i]+1 th doll that we were earlier finding in O(N) operations can now be done in O(log(N)) operations, hence making the total algorithm O(N log(N))

Robert Langdon & The Rule of Three

Difficulty : Medium

Category : Maths

Solution :

Refer to a coordinate point as binary string : becomes easier to explain that way.

First of all note that distance between two binary strings S1 and S2 (denote by dist(S1,S2)) as the number of positions where they differ. You can observe this in 3D space (length 3 strings); general proof can be done by induction on the dimension.

Now, call the three input strings to be A,B and C. Let S be a solution string, then dist(A,S) = dist(B,S) = dist(C,S).

First note that flipping A[i], B[i] and C[i] for any i will not change the number of solutions, it is like flipping ith bit in all the solution strings. Using this we can make A to be completely 0 (string of n zeros).

Now 4 cases arise for any i : (A[i], B[i],C[i]) = (0,0,0), (A[i], B[i],C[i]) = (0,0,1), (A[i], B[i],C[i]) = (0,1,0) and (A[i], B[i],C[i]) = (0,1,1).

In first case, the ith bit of solution string S can be both 0 or 1, the condition dist(A,S) = dist(B,S) = dist(C,S) will still hold.

For a solution string S, let a0 to be number of indices in range [1..n] such that S[i]=0 and (A[i], B[i],C[i]) = (0,0,1); and let a1 be number of indices such that S[i]=1 and (A[i], B[i],C[i]) = (0,0,1).

Similarly define b0 and b1 for case (A[i], B[i],C[i]) = (0,1,0) and c0 and c1 for case (A[i], B[i],C[i]) = (0,1,1).

Then dist(S,A) = a1+b1+c1

dist(S,B) = a1+b0+c0

dist(S,C) = a0+b1+c0

Using dist(A,S) = dist(B,S) = dist(C,S) we get

a0-a1=b0-b1=c1-c0 = d, for some d in range [-n .. +n].

Try all possible values of d. For any particular d, we know a0-a1 = d and a0+a1 = number of i such that (A[i], B[i],C[i]) = (0,0,1). So we know a0 and a1. Similarly b0, b1, c0 and c1 can be obtained. Then the number binary strings for this d are (a0+a1,a1)*(b0+b1, b1)*(c0+c1,c1)*2^(number of i such that (A[i], B[i],C[i]) = (0,0,0)). Sum that for all d to get the answer.

Robert Langdon & Class Attendance

Difficulty : Hard

Category : DP, data structures

Solution :

Consider the following O(N^2) solution first : For every position we can find how far can this pen go, ie, largest index j<=n such that all i+1<=k<=j, A[i]-D <= A[k] <=A[i]+D. Let S[i] be minimum number of pens required for subarray A[i..n].

Then S[i] = 1+max(S[i+1..j])

The main part was to reduce this to N log(N) because of the input constraints.

Consider a segment tree such that its segment [i..j] stores the value {max S[k], i<=k<=j}. That will make updating S[i] and finding max S[i..j] for any range [i..j] a log(N) task.

Now to find the largest j such that pen of ith student can go upto jth student, ie, i+1<=k<=j, A[i]-D <= A[k] <=A[i]+D. This can be broken down into two problems : largest j1 such that i+1<=k<=j1, A[k] <=A[i]+D; and  largest j2 such that i+1<=k<=j2, A[i]-D <= A[k]. Then j=min(j1,j2).

To find largest index such that values A[k] <= V for some fixed V:

Consider a segment tree such that each segment [i..j] of the tree contains {max A[k], i<=k<=j }.  The children of segment [i..j] in the tree are going to be [i..(i+j)/2] and [(i+j)/2 + 1 .. j].

Then there are two cases : If {max A[k], i<=k<=j } <= V, then whole segment has values <=V ans answer is j.

Else if the left child has maximum value >V, then surely largest such index is in the left child, else answer is in the right child.

There are a few boundary cases that need to be handled : like leaf node in the tree, or largest index being end point of the left tree, etc. But overall complexity is log(N).

This way we can get j1. Similarly we can find j2. Thus we get j for every i in log(N) complexity. (Remember definition of j : largest index j<=n such that all i+1<=k<=j, A[i]-D <= A[k] <=A[i]+D).

Hence total solution to the problem comes to be O(N log(N)).

Solutions : Sample solutions are attached below. Since the problem are put in main problem-set on SPOJ, and SPOJ discourages copy-pasting of solutions, so solutions are coded in Pascal (compiler fpc), makes it easier to find and disqualify copy-pasted solutions. Pascal is just like pseudocode that you find on Wikipedia, is easy to understand.

Regards,

Piyush Kumar