Travelling Salesman Again !

Problem code: TSPAGAIN

All submissions for this problem are available.

There are N cities numbered from 0..N-1. A salesman is located at city 0. He wishes to visit all cities exactly once and return back to city 0. There are K toll booths. Each toll booth has a certain range of functioning. The parameters for toll k are given as x_k and y_k. If the salesman travels from city i to j, he has to pay 1 dollar toll fee to each toll p having x_p >= i and y_p <= j. Calculate the cheapest way for the salesman to complete his tour.

Input :

The first line contains T the number of test cases. T test cases follow. The first line of each test case contains two space seperated integers N and K. Each of the next K lines contains 2 integers, the ith line containing x_i and y_i (0 <= x_i,y_i < N). A blank line seperates two test cases.

Output :

Output T lines, one for each test case, containing the required answer.

Sample Input :

2
3 2
2 0
0 2

3 4
1 0
2 1
0 1
1 2

Sample Output :

3
6

Constraints :

1 <= T <= 50
2 <= n <= 1000
1 <= K <= 10000

Date: 2010-03-20
Time limit: 8s
Source limit: 50000
Languages: C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS


Comments

Neat problem!  Fun to solve.

pieguy @ 3 Apr 2010 08:23 AM

Neat problem!  Fun to solve.

cn anybody plz explain the

khyatigupta @ 4 Apr 2010 02:00 PM

cn anybody plz explain the test cases??

i m a bit confused

Which part confuses you?

triplem @ 4 Apr 2010 02:38 PM

Which part confuses you?

heyy i dint udestand what

pratyushag @ 4 Apr 2010 02:50 PM

heyy i dint udestand what this first line means

 

"There are N cities numbered from 0..N-1."

Uh, how can that possibly be

triplem @ 4 Apr 2010 02:58 PM

Uh, how can that possibly be confusing?

That means we call the first

writerAPR10 @ 6 Apr 2010 01:01 AM

That means we call the first city 0, the second city 1, ..., and the last city N-1. Every city is given a name.

Can we assume that tolls are

mcsharma1990 @ 8 Apr 2010 06:12 PM

Can we assume that tolls are located in a two dimension plane at (x_p, y_p) ? And if I move from ith city to jth city then I have to pay 1 dollar to all the tolls located in the right bottom quadrant w.r.t point (i, j) ?

Damn !.. you are not supposed

flying_ant @ 9 Apr 2010 09:11 AM

Damn !.. you are not supposed to discuss your ideas like that here, when the contest is going on. No one stops you from assuming / deriving anything. Problem is very clear and many people solved it already with no complaints.

I thought it was just a

mcsharma1990 @ 9 Apr 2010 12:31 PM

I thought it was just a clarification of problem. Anyways i am sorry if this looks an idea of solution.

Why isn't my most recent

abhijith @ 9 Apr 2010 04:02 PM

Why isn't my most recent submission (and also faster one) being updated in the submissions list ?

P.S I submitted that around 6 hrs ago.

can two toll locations be

mcsharma1990 @ 12 Apr 2010 11:27 PM

can two toll locations be same?..i mean can they overlap?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions