VP proposals as CP questions
Disclaimer: This is a work intended for fun, if you are looking for the actual VP proposals you’ll get them here. We are working on our proposal critiques and they shall be available at your disposal pretty soon.
A wise person once said,
“Anything is a CP question if you are brave enough”
And we at TSA, are obviously way too brave enough for our own comfort and thus we wanted to check the truth value of the above statement by converting a few VP proposals into competitive programming questions. Of course, we all are washed-up programmers so don’t expect the constraints to be right, but do expect the questions to be exceedingly fun.
Do note that the proposals might be severely modified to get them into CP context, so if you guys want to know the accurate details of the proposals go ahead to https://gymkhana.iitkgp.ac.in/elections/candidates/. We’d also release proposals critiques pretty soon so make sure you stay tuned for that as well. So without further ado let’s get right into it.
Setting up fire extinguishers (Based on Aryansh’s Proposal 1 part 2)
After the fires that happened at Tech Market, it has become quite clear that fire safety is slightly overlooked on our campus. To solve this issue, VP Candidate A has come up with a system to strategically place fire extinguishers throughout campus.
The road network of IIT KGP can be as a graph with a road junction being a node and each road being an edge connecting two junctions. A region on the graph is considered to be unsafe if there is no fire extinguisher for every 25 meters (simplified from 25 square meters as mentioned in point 5(i) of Annexure of proposal 1). You are given the cost of placing fire hydrants at each junction. Note that the road may be longer than 25 meters in which case you can place fire extinguishers in between the road for a fixed rate of X rupees. Your task is to find the minimum cost of setting up fire hydrants while making sure that the entire campus is safe.
Input:
The first line contains three integers N M and X, the number of junctions, roads and the cost for placing fire extinguishers in between roads
The next line contains N integers each representing the cost of placing a fire extinguisher in node i.
The next M lines contain three integers each x,y,w representing a road between junctions x and y and w being the length of the said road.
Output:
A single integer denoting the minimum cost required to make our campus safe(as described in the statement).
Constraints:
N < 43993
M < 3080
W < 1e9
Note:
Aryansh Singh’s proposal can be obtained at https://gymkhana.iitkgp.ac.in/election/19HS20011.pdf.
Rest between Tests (Based on Brahmjot’s Proposal 2)
Every year, the placement batch is put forth with a large number of tests before they finally get a chance at interviews. These weeks are usually cramped with an ungodly amount of tests in which the candidate usually has a tough time keeping track of them. Noticing this situation VP candidate B has come up with a Logistic Calendar which shall solve this problem by tracking the companies the student has applied for and making sure they never miss a deadline.
As someone could potentially use this calendar in the near future, you understand that there are two things that you shall lose when placements are near. Hope and Sleep. While the first one doesn’t have a solution (other than git gud) the second one can be solved with the help of the calender.
Given the time list of tests for the companies that you’ve applied for, and with an assumption that you are allowed to sleep whenever there isn’t a test determine the maximum amount of sleep you’ll get in HOURS:MINUTES format.
Input:
The first line contains two integers D and N, denoting the number of days tests take place and the number of tests you’ve applied for.
The next N lines contain information in the below format
d HH:MM HH:MM
Where d is the day in which the test shall be held and the next two strings indicate the start time and end time of the test.
Constraints:
D < 100
N < 1e5
0 <= HH < 24
0 <= MM < 60
Output:
In the format of HH:MM enter the maximum amount of sleep you shall get.
Editorial (cause less lazy):
It’s always beneficial to convert HH:MM format to minutes elapsed from the beginning of day 0, thus allowing easy data handling. From here sort the time intervals and find if there is any overlap in intervals, if there are merge them. Then proceed with subtracting the end time of an interval from the start time of the next interval and sum up all such values.
The checker shall also accept a blank output of zero(0, zerO, zErO, ZErO etc).
Note:
Brahmjot Singh’s proposal can be obtained at https://gymkhana.iitkgp.ac.in/election/19GG20008.pdf
Note before possible controversy:
We understand that Aryansh has something similar namely CDC process sorter, but this curated problem just makes it so that we have a place dedicated for each candidate (one problem made for one candidate-pls understand me is human too thx).
Mental health queries (Based on Gaurav’s proposal 4):
This is an interactive problem.
Declining mental health has been a severe problem and Corona is now at an all-time low. VP Candidate G upon understanding this situation has come up with a series of steps to combat and improve the mental health condition on campus.
In this problem, you are the Faculty advisor of the student and at the start of the semester, you call upon your students to hear their concerns. You are aware that during a semester, there is a certain point where the mental health becomes absolutely worse so you plan to organize your next meeting with your students during that time. This point is the same for all students.
To every student, you can ask one question, on what they guess their mental health situation shall be after x days to which the candidate shall reply with a yes or a no. If you ask more questions about the date the student might not get time to discuss their concerns.
Input:
One line contains two integers N and D meaning the number of students to whom you are the faculty advisor and the number of days in a semester respectively.
Constraints:
N < 12
D < 100
Interaction:
Post a single integer representing the day in a semester. You’ll receive a single string which shall either be “yes” or “no”.
Find the optimum day for scheduling the next meeting (the first “no” day). Make sure you clear buffer after each output by flushing the stream.
Your solution will get “Idleness Limit Exceeded”, if you don’t print anything or forget to flush the output, including the final answer.
To flush you can use (just after printing a query and line end):
- fflush(stdout) in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
- flush(output) in Pascal;
For other languages see documentation.
Note:
Gaurav Garg’s proposal can be obtained at https://gymkhana.iitkgp.ac.in/election/19EX20015.pdf.
Final notes:
Hope you guys enjoyed the questions, do share possible solutions and do make sure you attend the SOAP box and make informed decisions!
