Обсуждение @ 1119. Метро @ Timus Online Judge

Kate WA test5! Help, please! [4] // Задача 1119. Метро 22 дек 2013 06:38

Mescheryakov_Kirill [SESC17] To admins [2] // Задача 1119. Метро 23 фев 2016 11:20

codefresher Is given problem test case is right??? [1] // Задача 1119. Метро 27 мар 2019 00:01

Egor_Shchetinin Is possible to have AC on Python 3.6? [2] // Задача 1119. Метро 14 фев 2019 17:59

dtchau data test 9 [1] // Задача 1119. Метро 4 май 2013 13:52

yakung runtime error // Задача 1119. Метро 9 мар 2021 09:44

Georgi_georgiev Wrong answer on 6th test. Please help:) [13] // Задача 1119. Метро 3 июн 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] // Задача 1119. Метро 4 июн 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] // Задача 1119. Метро 18 июл 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] // Задача 1119. Метро 23 янв 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 // Задача 1119. Метро 6 май 2011 00:04

thanx a lot)

[SESC USU] Zhirov Eugene Re: Test Case answers // Задача 1119. Метро 4 окт 2012 23:28

Thanks =)

[TH2011/03]Ho Vo Thanh Trong No subject // Задача 1119. Метро 22 ноя 2012 15:32

Thanks very much :)

[TH0312]PhanChauPhucThinh Re: Test Case answers // Задача 1119. Метро 22 ноя 2012 21:48

thanks

thefourtheye Re: Test Case answers [1] // Задача 1119. Метро 5 дек 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 // Задача 1119. Метро 8 янв 2013 14:39

2-1, 5-2, 10-4

ImgJ Re: Test Case answers // Задача 1119. Метро 5 апр 2015 23:37

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

capitan.ARA.code Re: Test Case answers // Задача 1119. Метро 12 июл 2020 13:24

tanhk you the test are graet

Islom(TUIT Urgench) Re: Wrong answer on 6th test. Please help:) // Задача 1119. Метро 11 янв 2015 16:10

thank you very much for tests!!!

Максим Re: Wrong answer on 6th test. Please help:) // Задача 1119. Метро 28 июл 2019 16:49

Thanks! You are breathtaking)

CmYkRgB123 An O(K^2) solution [2] // Задача 1119. Метро 31 окт 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] // Задача 1119. Метро 31 окт 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 // Задача 1119. Метро 30 мар 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] // Задача 1119. Метро 26 мар 2017 21:00

mr_invincible If you get WA2 [8] // Задача 1119. Метро 6 сен 2008 16:53

nexerd Comp error [1] // Задача 1119. Метро 2 окт 2014 19:44

Dewesh Deo Singh Need Help TEAST CASE5 [1] // Задача 1119. Метро 4 июн 2016 08:45

German WA10 test [3] // Задача 1119. Метро 20 ноя 2016 11:36

sukhad TLE with bfs // Задача 1119. Метро 18 фев 2017 03:53

Anton for those who use graph & recursion approach [3] // Задача 1119. Метро 7 мар 2012 06:30

c_pp There exists O(K^2) solution!!! // Задача 1119. Метро 7 янв 2017 21:27

Sushant Bhat getting Runtime error in test case 3 of metro. Please help [1] // Задача 1119. Метро 29 авг 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 // Задача 1119. Метро 4 сен 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] // Задача 1119. Метро 14 июн 2015 17:00

wuqingxin wrong answer 3 [1] // Задача 1119. Метро 29 окт 2013 21:32

Minayev {SESC USU} WA 13 Help, pls // Задача 1119. Метро 2 ноя 2014 17:16

Обсуждение задачи 1119. Метро