Discussion @ 1119. Metro @ Timus Online Judge

Kate WA test5! Help, please! [4] // Problem 1119. Metro 22 Dec 2013 06:38

Mescheryakov_Kirill [SESC17] To admins [2] // Problem 1119. Metro 23 Feb 2016 11:20

codefresher Is given problem test case is right??? [1] // Problem 1119. Metro 27 Mar 2019 00:01

Egor_Shchetinin Is possible to have AC on Python 3.6? [2] // Problem 1119. Metro 14 Feb 2019 17:59

dtchau data test 9 [1] // Problem 1119. Metro 4 May 2013 13:52

yakung runtime error // Problem 1119. Metro 9 Mar 2021 09:44

Georgi_georgiev Wrong answer on 6th test. Please help:) [13] // Problem 1119. Metro 3 Jun 2009 05:52

Edited by author 04.06.2009 17:47

Edited by author 04.06.2009 17:47

Georgi_georgiev Re: Wrong answer on 6th test. Please help:) [11] // Problem 1119. Metro 4 Jun 2009 17:46

I found my stupid mistake but here are some tests:
2 2
1
1 2

2 2
2
1 2
2 1

2 2
2
1 1
2 2

2 2
2
2 1
2 2

6 6
1
6 1

6 6
1
1 6

6 6
18
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
2 1
3 2
4 3
5 4
6 5

6 6
6
1 6
2 5
3 4
4 3
5 2
6 1

1 1
1
1 1

1 1
0

10 1
1
1 1

10 1
5
1 1
2 1
3 1
10 1
5 1

10 6
8
5 2
1 5
2 1
4 5
1 6
10 1
10 2
10 4

10 5
20
5 4
3 2
1 4
6 5
2 3
2 1
9 3
7 4
10 2
2 5
9 2
8 4
9 1
8 1
3 3
5 2
7 5
4 5
9 5
6 1

10 5
20
10 1
1 1
1 3
9 3
7 1
6 3
4 4
9 2
7 3
5 5
4 2
4 3
9 4
3 2
6 1
1 2
3 1
3 3
10 4
7 5

wakeeper Re: Wrong answer on 6th test. Please help:) [9] // Problem 1119. Metro 18 Jul 2009 09:19

Can you figure out where you are wrong?
Would you please print the test's result out?

Prabhjot Singh Test Case answers [8] // Problem 1119. Metro 23 Jan 2010 06:02

Answer to above test

1) 341

2) 341

3) 283

4) 341

5) 1141

6) 1141

7) 907

8) 1141

9) 141

10)200

11)1041

12)1041

13)1424

14)1266

15)1266

Hope that helps :)

Prabhjot Singh

Mikuru_Beam Re: Test Case answers // Problem 1119. Metro 6 May 2011 00:04

thanx a lot)

[SESC USU] Zhirov Eugene Re: Test Case answers // Problem 1119. Metro 4 Oct 2012 23:28

Thanks =)

[TH2011/03]Ho Vo Thanh Trong No subject // Problem 1119. Metro 22 Nov 2012 15:32

Thanks very much :)

[TH0312]PhanChauPhucThinh Re: Test Case answers // Problem 1119. Metro 22 Nov 2012 21:48

thanks

thefourtheye Re: Test Case answers [1] // Problem 1119. Metro 5 Dec 2012 16:15

10 6
8
5 2
1 5
2 1
4 5
1 6
10 1
10 2
10 4

For this case, there can be only 2 diagonal crossings ((2,1) & (5, 2)), right? but the answer (1424) says 3.

Edited by author 05.12.2012 16:23

hatred [Ivanovo SPU] Re: Test Case answers // Problem 1119. Metro 8 Jan 2013 14:39

2-1, 5-2, 10-4

ImgJ Re: Test Case answers // Problem 1119. Metro 5 Apr 2015 23:37

Thank you wery much, there are very good tests, I got AC :)

capitan.ARA.code Re: Test Case answers // Problem 1119. Metro 12 Jul 2020 13:24

tanhk you the test are graet

Islom(TUIT Urgench) Re: Wrong answer on 6th test. Please help:) // Problem 1119. Metro 11 Jan 2015 16:10

thank you very much for tests!!!

Максим Re: Wrong answer on 6th test. Please help:) // Problem 1119. Metro 28 Jul 2019 16:49

Thanks! You are breathtaking)

CmYkRgB123 An O(K^2) solution [2] // Problem 1119. Metro 31 Oct 2008 18:11

Sort the quarters that can be crossed.And then dp.

The state transition equation is
F[i]=Max{ F[j] + 1 | P[j].x<P[i].x and P[j].y<P[i].y }

The maximum of F[i] is the number of the the quarters that should be crossed.

Then you can work out the answer.

Edited by moderator 18.08.2020 02:22

CmYkRgB123 Re: An O(K^2) solution [1] // Problem 1119. Metro 31 Oct 2008 18:26

A solution for Chinese readers.Much clearer.

这道题有明显的动态规划策略。首先不要按照方格来考虑，考虑顶点，这样目标点就是(N+1,M+1)。

---------算法1-----------
最直观的想法是按照矩阵动态规划。

设状态F[i,j]为走到点(i,j)时的最短路径

状态转移方程
F[i,j]=Min
{
F[i-1,j]+100
F[i,j-1]+100
F[i-1,j-1]+141.4213562373
}

边界条件 F[0,0]=0

F[N+1,M+1]就是结果。

但是对于8M的内存限制，要使用滚动数组。

时间复杂度为O(N*M)

---------算法2-----------
可以发现，如果我们只走直边的话，要走(N+M)*100长度。如果走C条斜边，那么要走(C*141.4213562373)+(N+M-C*2)*100 的长度。那么显然我们要尽可能使C更大，即多走斜边。

这样可以转化为经典的LIS模型。即把所有的斜边按照坐标排序，然后求最长的上升序列(x，y都要严格递增)，走这样的斜边一定是最优的策略。于是我们可以求出C。

结果就是(C*141.4213562373)+(N+M-C*2)*100。

Vijos 1336其实就是这道题的数据加大版。对于较小的K和很大的N,M，只能用算法2解决。

abid1729 Re: An O(K^2) solution // Problem 1119. Metro 30 Mar 2020 23:12

by translating.............

A solution for Chinese readers.Much clearer.

This problem has obvious dynamic programming strategies. First, don't think in terms of squares, consider vertices, so the target point is (N + 1, M + 1).

--------- Algorithm 1 -----------
The most intuitive idea is dynamic programming in terms of matrices.

Let the state F [i, j] be the shortest path to the point (i, j)

State transition equation
F [i, j] = Min
{
F [i-1, j] +100
F [i, j-1] +100
F [i-1, j-1] +141.4213562373
}

Boundary condition F [0,0] = 0

F [N + 1, M + 1] is the result.

But for the 8M memory limit, a rolling array is used.

Time complexity is O (N * M)

--------- Algorithm 2 -----------
It can be found that if we only go straight, we have to go to (N + M) * 100 length. If you take the C hypotenuse, then you have to take the length of (C * 141.4213562373) + (N + M-C * 2) * 100. So obviously we want to make C as large as possible, that is, take more hypotenuse.

This can be transformed into a classic LIS model. That is, sort all the hypotenuses according to the coordinates, and then find the longest ascending sequence (x, y must be strictly increased). Taking such hypotenuses must be the optimal strategy. Then we can find C.

The result is (C * 141.4213562373) + (N + M-C * 2) * 100.

Vijos 1336 is actually an enlarged version of this question. For smaller K and large N, M, it can only be solved by algorithm 2.

ComebackSeason A better solution [3] // Problem 1119. Metro 26 Mar 2017 21:00

mr_invincible If you get WA2 [8] // Problem 1119. Metro 6 Sep 2008 16:53

nexerd Comp error [1] // Problem 1119. Metro 2 Oct 2014 19:44

Dewesh Deo Singh Need Help TEAST CASE5 [1] // Problem 1119. Metro 4 Jun 2016 08:45

German WA10 test [3] // Problem 1119. Metro 20 Nov 2016 11:36

sukhad TLE with bfs // Problem 1119. Metro 18 Feb 2017 03:53

Anton for those who use graph & recursion approach [3] // Problem 1119. Metro 7 Mar 2012 06:30

c_pp There exists O(K^2) solution!!! // Problem 1119. Metro 7 Jan 2017 21:27

Sushant Bhat getting Runtime error in test case 3 of metro. Please help [1] // Problem 1119. Metro 29 Aug 2016 16:39

#include<iostream>
#include <cmath>
#include <climits>
#include <deque>

using namespace std;

int v[1001][1001];
float table[1002][1002];

int metro(int n,int m,int k){
    deque<int> qi,qj;
    qi.push_back(1);
    qj.push_back(1);
    table[1][1] = 0;
    while(!qi.empty()){
        int i = qi.front(),j = qj.front();
        qi.pop_front();
        qj.pop_front();
        if(i <= n && table[i+1][j] > table[i][j]+100){
            qi.push_back(i+1);
            qj.push_back(j);
            table[i+1][j] = table[i][j]+100;
        }
        if(j <= m && table[i][j+1] > table[i][j]+100){
            qi.push_back(i);
            qj.push_back(j+1);
            table[i][j+1] = table[i][j]+100;
        }
        if(v[i][j] == 1){
            if(i <= n && j <= m && table[i+1][j+1] > table[i][j] + 141.4){
                qi.push_back(i+1);
                qj.push_back(j+1);
                table[i+1][j+1] = table[i][j]+(141.4);
            }
        }
    }
    return ceil(table[n+1][m+1]);
}

int main(){
    int n = 0,m = 0,k = 0;
    cin>>n>>m;
    for(int i = 0;i <= n+1;++i){
        for(int j = 0;j <= m+1;++j){
            v[i][j] = 0;
            table[i][j] = INT_MAX;
        }
    }
    cin>>k;
    for(int i = 0;i < k;++i){
        int x = 0,y = 0;
        cin>>x>>y;
        v[x][y] = 1;
    }
    cout<<metro(n,m,k)<<endl;
    return 0;
}

Edited by author 29.08.2016 16:40

Edited by author 29.08.2016 16:40

Dmitriy Re: getting Runtime error in test case 3 of metro. Please help // Problem 1119. Metro 4 Sep 2016 19:34

It is a biggest test for check boundaries. And you are have a problems with it. For example:
for(int i = 0;i <= n+1;++i){
for(int j = 0;j <= m+1;++j){
v[i][j] = 0;

where v is: int v[1001][1001];

With n = 1000 this code will crash. It's about 3 test case.
Ans I see another mistakes...

esbybb java AC code [2] // Problem 1119. Metro 14 Jun 2015 17:00

wuqingxin wrong answer 3 [1] // Problem 1119. Metro 29 Oct 2013 21:32

Minayev {SESC USU} WA 13 Help, pls // Problem 1119. Metro 2 Nov 2014 17:16

Discussion of Problem 1119. Metro