Lily's Blog

Mobile Application Development and Competitive Practice Problems

Why Haskell?

9. October 2015 Administrator (0)


An interesting debate sparked on the forums of Hacker News: what are the benefits of coding in Haskell and why should we use it?

Here are the main points:

* Haskell is (very) strongly and statically typed and Python isn't. Haskell's type system can prove the correctness of many functions at compile time. In contrast, Python usually waits until runtime to throw exceptions, even for something obvious like a syntax error.

* Because the types are known, there's an incredibly powerful testing framework called QuickCheck that is capable of e.g. generating tens of thousands of valid inputs and seeing if it can automatically disprove your assertions about your code. Python's typing is insufficient for this.

* Qualitatively, writing Python feels like writing instructions for computing something, and writing Haskell feels like simply describing what something is, and the system works out how to compute it for you. It often feels compelling and magical.


Medium Problem: Game Count

9. October 2015 Administrator (0)
Tug of war is a sport that directly puts two teams against each other in a test of strength. During school days, both Chef Shifu and Chef Po were champions of tug of war. On behalf of restaurant's anniversary, Chef Shifu and Chef Po have decided to conduct a tug of war game for their customers.

Master Chef Oogway has decided the following rules for the game.

  1. Let N be the number of players participating in the game. All of these players would stand in a circle in clock wise direction.
  2. There are an infinite number of long ropes available. When a rope is held by exactly two players, it is termed as bonding.
  3. At least one bonding is necessary to conduct a game.
  4. A player can play against multiple people simultaneously i.e he can have more than one bonding at the same time.
  5. Both members of a pair of players that have a bonding must have the same number of total bondings. That is, if the player A makes bonding with the player B, then the number of total bondings of the playerA must be the same as that of the player B.
  6. Bondings should be created in such a fashion that ropes must not intersect each other.
  7. The number of bondings of every player must be no more than K.

Now Master Chef Oogway asked Chef Shifu and Chef Po to find out the number of possible games. Your task is to help them find this number. As this number might become huge, you've to find it modulo (10^14+7). Two games are different iff there is some bonding that is present in only of them.

Input

First line contains T, the number of test cases. Each of T lines contain 2 positive integers N and K separated by a space.

Output

For each test case, output the number of ways to conduct the game modulo 100000000000007 (1014+7) in one line.

Example

Input:
3
3 2
4 0
2 1

Output:
4
0
1
Explanation: For the 1st case, there are 3 players. Let's call them p1, p2, p3. Different games possible are:
Game 1: p1-p2 (numbers of bondings of p1, p2 are 1 ≤ K = 2)
Game 2: p1-p3 (numbers of bondings of p1, p3 are 1 ≤ K = 2)
Game 3: p2-p3 (numbers of bondings of p2, p3 are 1 ≤ K = 2)
Game 4: p1-p2, p1-p3, p2-p3 (numbers of bondings of p1, p2, p3 are 2 ≤ K = 2) For the 2nd test case, we cannot form the game, because K = 0 and hence no player is allowed to make any bonding. As any game must have atleast one bonding, no game is possible here. For the 3rd case, only possible game is:
Game 1: p1-p2 (number of bondings in p1, p2 are 1)

Constraints

1 ≤ T ≤ 10000 0 ≤ N ≤ 10000 0 ≤ K ≤ N

Source: Codechef.com

Algorithms: Traffic Control

9. October 2015 Administrator (0)
There are N cars entering a one way road having two lanes. There is a divider between lanes so once a car enters a lane, it can't change. Also lanes are narrow so overtaking is not possible and hence a car might have to slow down to avoid bumping in the car in front of it. Each car has a maximum speed which is given to you. A car driver is happy if his car doesn't need to slow down and can drive at its maximum speed.

You're the traffic policeman and it is your job to assign certain cars to lane 1 and remaining to lane 2. Within a lane order of cars is same as their initial order. How should you assign lanes to each car so that maximum drivers are happy?

Source:
Problem written by Pradeep George Mathias , Rudradev Basak and Nikhil Garg, used in 2nd team selection test at IOI training camp for Indian team, 2012.

ACM Style Competitions

9. October 2015 Administrator (0)
Here's some important information from this site (http://mcicpc.cs.atu.edu/) that depicts the essential aspects of ACM style events.

An except below:

Competition/practice overview

In the contest (and practices!), you get to bring any book/paper references you like.  I was really impressed by the student that brought his favorite book with physical tabs added to locate the most important parts.  Your team of three people is presented with one computer and 6-10 problems on paper.  Each problem generally has 1-2 page specifications, showing sample input and output data, and requiring 10-120 line of code beyond the standard I/O setup (if you are concise – which is not exactly necessary).  Some are very easy, and a good team will bang out such a problem first in 10-20 minutes.  Others take much longer, figuring out an appropriate algorithm, and covering and coding all the special cases.  Problems are non-interactive and follow the simple pattern:  read data from the input file, process data, output data to standard output.  Input data will always have a count at the beginning or a sentinel at the end, making it easy to construct a main loop without worrying about end-of-file conditions.

In all problems exact input and output formats are specified.  The judge’s input data is generally much more thorough than the sample input data you are given.  Your program is run with the secret judge’s input data.  It should produce the exact right output to the screen, or your submission is wrong.  Little information is given back to you if you make an error – one of 5 categories is checked off.  Unfortunately this complicates finding and correcting bugs for another submission.  File naming conventions must be followed exactly.  there is a base name for a given problem, say “juggler” for instance.  Then the input file must be “juggler.in”.  Debugging info needs to go  to the standard error stream, not standard output.  The source file name is “juggler” with the appropriate language extension (juggler.cpp, juggler.java).  The base name is generally all lowercase.  If you write in Java, this makes you break the usual Java class naming convention:  the source file name and main class name are all lower case.

The scoring is based first on the number of problems eventually submitted totally correct.  In some competitions, some teams get all the problems (from 150 or so total teams among all local sites).  In some competitions no one team gets all the problems.  Among teams solving the same number of problems, time and incorrect submission penalties determine who is ahead.  For each problem, time is measured from the beginning of the competition to the time of correct submission.  Each incorrect submission for a problem that is ultimately submitted correctly adds a 20 minute penalty to your correct submission time.  Problems that never get a correct submission, no matter how many incorrect submissions, are ignored in scoring.  Note that time is measured on each problem from the beginning of the competition, not the time of the last correct solution.  This means that it is strategic to do the simplest problems first.  Fifteen minutes for one problem solution, followed by 50 more minutes for a second solution would give you 15 + (15+50) = 80 minutes for the two problems. Fifty minutes solving the first problem, followed by 15 more minutes for the second problem would give you 50 + (50+15) = 115 minutes for the two problems – much worse.  If the 15 minute problem was submitted correctly the first time, and the 50 minute problem had two incorrect submissions before the correct submission, the total minutes recorded would be 2*20 = 40 minute more, (120 or 155).

Because of the two very different attributes of scoring, there are different strategies.  Different team members may have different skills, encouraging splitting the problems up and basically working alone.  Pn problems where one team member has a clear idea or is the only one clued in, working alone saves the time of coordinating, and possibly leads to having time to solve an extra problem, which is the most important thing in scoring.  The secondary scoring critieria, time until solutions, encourages working together.  As a simplicication, ignore the time to type into the computer:  If three problems each take 30 minutes for one individual, but can be modularized into three 10 minute portions for each team member, then working together, problems can be submitted after 10, 20, and 30 minutes for a score of 60, but if everyone works separately (and then types instantly) the times would be 30, 30, and 30, for a score of 90.  The overhead of time to communicate plans detracts from the cooperative solving approach.

The most important thing that encourages working together is running out of time.  It is a common point of frustration to have 2-3 problems 90% complete at the end, and then they all count for nothing.  If several are working on problems that require some thinking time and they do not have time to finish, then switch approach:  Agree on one of them that can be split in pieces among several people thinking about distinct pieces, or brainstorming together, and get it done in time!

You get to submit written questions to the judges if anything seems ambiguous to you, and you get a written response back.  Sometimes the questions and answers from other teams are posted for all to see.  

For input in Java use java.util.Scanner. Note that the file names specified are generally in lower case.  For a java source file, that means the main class name needs to be the same lowercase name.  For sample problems with statements see the sample problems.  Note the solutions to Addition for a simple illustration of the basic I/O and naming format.

Favorite topics/algorithms for problems:

  • Translate a simple, straightforward description
  • Shortest or longest paths in graphs
  • Sorting
  • Recursive searches
  • Geometrical output (always text, but graphical ideas for positioning parts are likely to come in).  Java programmers not familiar with two dimensional arrays might want to look at my Java 2-D Array Introduction.
  • Problems involving all combinations, permutations, or subsets.  I have sample code that is also a good review of recursion in recursion.html. 

Be sure to read the excellent, extensive description of language and algorithmic skills desired is at the Mid-Central site http://mcicpc.cs.atu.edu/.

Easy Problem: Missing Triangle

9. October 2015 Administrator (0)

Given any two edge lengths of a right triangle, find the missing third.


Where:


X = length of side 1

Y = length of side 2

Z = length of hypotenuse

_ = blank variable


Your output should be rounded to the nearest three decimals places


INPUT SAMPLE 1

3 _ 5


OUTPUT SAMPLE 1

4.000


INPUT SAMPLE 2

7 _ 10


OUTPUT SAMPLE 2

7.141


Source:

Problem written by IEEE-CS mooshak: http://mooshak.cloudapp.net/~ieeecs/cgi-bin/execute/5400314664188919?login.

Welcome Message & Social Media Sites

4. September 2015 Administrator (0)

Here is where I post information on upcoming projects and practice problems for competitive programming events. 


Follow me on these social media platforms for updates:

Twitter:  https://twitter.com/ltanginator
Facebook:   https://www.facebook.com/groups/1134391123254950/
Game Website: http://thetanginator.azurewebsites.net/