CODEPOOL
A quest are given to undertake,hidden,mysterious,with price at stack to demostrate the moster with the (code)pool. Find the solution with a brilliant presentation and keep your cool...
A brain-racking algoritham development competition, the code-pool demands the best of approach and coding skills out of you. The best solution to a given problem in terms of efficiency and speed(technically speaking, time complexity and space complexity) are some of the criteria to judge your powers.The best selected entries shall then have to convience their logic by a presentation supplemented with a program code.
Click here to download the .doc file
Background
The Reporting Committee of Literati is facing a tough challenge due to the careless attitude of the Scheduling Committee Head Prashant The Pirate. Unfortunately, there was no trace left of the Schedule of Events at Literati ’09. Now that the fest is over, the Reporting Committee needs to prepare a detailed report of the events and for the same it needs to find out the chain of events.
For this purpose, Assiduous Abhinav sent his team to collect facts that would help him draw the rough schedule. The team returned with facts, but it was not certain whether the collected facts were true or false.
The facts collected were only of the following three types :
a) Event i finished before event j started
b) Event i finished during event j
c) Event i started during event j
The only help that Assiduous Abhinav received from Prashant The Pirate was regarding the information that at any particular time, only one event either started or finished.
Now the task for Assiduous Abhinav is to determine whether all the facts collected can be used to draw a consistent timeline of the schedule or not. In case the facts are not consistent, he needs to ignore minimum number of facts so as to draw a consistent timeline. While minimizing the number of facts ignored, care should be taken that minimum no. of events should be removed from the timeline.
Input
The first line of input consists of the number of facts collected, integer N [1 <= N < 101]. There are N subsequent lines reporting each fact. Each such line consists of two integers i and j [1 <= i,j < 101] representing the events, followed by one character from the set {a,b,c} representing the nature of the fact as described above.
Output
The first line of output should be POSSIBLE in case Assiduous Abhinav determines that all the facts are consistent. Otherwise, the first line of output should be an integer n representing the minimum number of facts that need to be ignored to draw a timeline, followed by the facts to be ignored in n successive lines.
This should be followed by a blank line followed by the timeline in 2E lines where E represents the number of events for which the timeline has been prepared.
Sample Input Sample Input
7 11 // number of facts recorded
1 2 b 4 2 c // means that Event 4 started during Event 2
3 1 c 1 3 b // means that Event 1 finished during Event 3
3 4 a 1 4 a // means that Event 1 finished before Event 4 started
3 2 c 3 1 c
2 4 a 2 3 c
2 3 b 4 3 c
2 1 c 2 4 b
3 4 b
3 2 b
3 4 a
1 2 b
Sample Output Sample Output
POSSIBLE 1 // minimum no. of facts to be ignored
3 4 a // the fact to be ignored from the given Input
1 started
2 started 1 started // Timeline
3 started 3 started
1 finished 2 started
2 finished 1 finished
3 finished 4 started
4 started 3 finished
4 finished 2 finished
4 finished
Event Description
1. The event will be conducted in two stages.
2. In the first round, a problem statement will be released, for which your team needs to develop an algorithm, and code the same in C / C++. Teams will be given a maximum of 3-4 days to solve the same.
3. Your algorithm and code must be efficient in time and space to the extent possible.
4. Your code will then be put through a set of test cases, passing which you shall qualify for the on-site presentation round.
5. In the presentation round, each qualifying team shall have to present their algorithm to the judges, and justify the strength of your algorithm on the basis of the time and space complexities.
Rules and Regulations
1. Teams of upto two members only. A team can consist of students from different colleges.
2. There is no requirement for pre-registration.
3. The coded solution must be submitted along with a text file describing your algorithm’s approach.
4. Mail in your entries to codepool.literati09@gmail.com latest by 7pm on Friday, April 17, 2009.
5. While mailing in your entries, do mention your contact details as well as the institution you belong to.
6. There is no entry fee / registration charges for this event.
7. Judges’ decision will be final and binding.
Selected teams would be required to give a presentation of their solutions on Monday, April 20, 2009 on-site.
For queries,contact:
Akhil Gupta 09416371568
Pulkit Agrawal 09996448532
Abhigyan Mundhra 09896110721
Or mailto: literati09@gmail.com with SUBJECT “CODEPOOL”
Click 