new problem

Given M salesmen and N cities. Cities are set along a river in a straight line, and cities are numbered from 1 to N. Each merchant chooses an interval [ai; bi] cities where will sell a product (unique - each trader has a unique product). In addition, they begin to sell their products at the pi price in the ai city, but as they go, each merchant becomes greedier and increases the price by 1. In other words, in the city a each merchant will sell the product with p price,in the city a + 1 with p + 1, ..., and in city b with b - a + p.
To find out which city is the most "expensive" city, residents want to determine for their city how much will cost the most expensive product brought by merchants. Because they do not know how to do it, they ask you to help.

Input data
first line N and M, representing the number of cities and the number of merchants. On the following M lines, there will be 3 numbers, a, b and p, representing the fact that a merchant expands in the range [a; b] and starts in the city a with the p price.

Output data
N numbers, representing the most expensive price of the city i.

limitations
1 <= N <= 1 000 000
1 <= M <= 300 000
1 <= a < b <= N
1 <= p <= 2 000 000 000
If no merchant comes in a city, the price for that city will be 0.
Execution time 1 sec.

Any idea how to solve ??
Always break down your problem into smaller, simpler steps and work your way up to the final solution.

Why don't you start by having a fixed number of cities (say 10) and a single salesman? Also hard-code the start (a) and end (b) cities (say, 2 and 7) and initial price (p) (say 5) for this salesman. Print out the price of the object at each city. You should get a printout something like this:


city    price
1          0
2          5
3          6
4          7
5          8
6          9
7         10
8          0
9          0
10         0


Next, add a second salesman with differing a, b and p values. Put the a, b and p values into an array to make this expandable in the future. Now print out the calculated price for each salesman at each city, as well as the maximum price at each city.

So, for a1=2, b1=7, p1=5, a2=4, b2=9, p2=3 you would get a printout something like this:


city    price1     price2     max
1          0          0        0
2          5          0        5
3          6          0        6
4          7          3        7
5          8          4        8
6          9          5        9
7         10          6       10
8          0          7        7
9          0          8        8
10         0          0        0


After you get this far you can worry about keeping track of the maximum city value and expanding to a million cities (wow, that's a long river) and 300,000 salesmen and initial prices of up to 2 billion (wow, think about the GDP for that country).

But get the basics working before you expand your code to implement the entire problem.
Yeh, indeed huge GDP. Thank you for your feedback anyway!

Of course I have tried some basic working before posting the problem.
First, I have tried brute force :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <fstream>
using namespace std;
ifstream in("file.in");
ofstream out("file.out");
int v[1000001];
int main()
{
    int n,m,a,b,p,i,j;
    in>>n>>m;
    for(i=1;i<=m;i++){
        in>>a>>b>>p;
        for(j=a;j<=b;j++)
            v[j]=max(v[j],p+(j-a));
    }
    for(i=1;i<=n;i++)
        out<<v[i]<<" ";
    return 0;
}


I'm getting 30/100, time limit exceed

there are no way to build the solution in a matrix of 1000000x300000, due to memory limit (65M).

I guess the problem can be solved somehow by doing some work on the tree of intervals (for those 300000 salesmen). I didn't figure it yet what exactly should be done in this respect.
Last edited on
Unfortunately, I don't have the time to think about a streamlined algorithm trick for solving this problem. I think that's the point of the exercise.

My suggestion is to continue expanding the data sets you are working with printing out the results. Look for patterns in the output. I agree that analyzing the salesmen's routes is the place to start. And you can probably focus on the last city on each route.

By the way, when you post code, please put it in code tags. Click the Format button that looks like "<>" and paste your code between the generated tags. This will make the code easier to read and comment on.
thank you for comment. I have edited my previous post (as you suggested re code).
So, anyone else have idea how to solve the puzzle?
Topic archived. No new replies allowed.