| Show all threads Hide all threads Show all messages Hide all messages | | WA test5! Help, please! | Kate | 1119. Metro | 27 Sep 2023 14:02 | 5 | Попробуй большую точность, там где большое поле, например:
Input:
1000 1000
5
100 100
200 200
300 300
400 400
500 500
Output:
199707 Thanks it was rounding error | | To admins | Mescheryakov_Kirill [SESC17] | 1119. Metro | 21 Jun 2023 04:11 | 3 | To admins Mescheryakov_Kirill [SESC17] 23 Feb 2016 11:20 In a task it is told that a way of departure (1; 1) though, actually, the way of departure has to be (0; 0) Nop, he is starting out from the south-west corner of the 1;1 quarter Isn't that the same as 0;0? | | Is given problem test case is right??? | codefresher | 1119. Metro | 29 Jun 2022 20:47 | 2 | The problem test case is:
3 2
3
1 1
3 2
1 2
but is it right??
My observation finds:
3 2
3
1 1
3 2
2 1
plz help me??? | | Is possible to have AC on Python 3.6? | Egor_Shchetinin | 1119. Metro | 4 Feb 2022 21:28 | 3 | I tried to solve this task by dp and bfs, but always have a TL on test 3. the same for python3
Edited by author 03.07.2021 00:47 I just got an AC with pypy | | data test 9 | dtchau | 1119. Metro | 4 Feb 2022 21:24 | 2 | Apparently something like this
1 1000
1
1 40 | | runtime error | yakung | 1119. Metro | 9 Mar 2021 09:44 | 1 | I'm getting runtime error(access violation) on test case three. I don't know where I went wrong. Can anyone please help me?
Here is my code
using namespace std;
#include <iostream>
#include <cmath>
#include<bits/stdc++.h>
long long int n,m;
bool vi[1005][1005], di[1005][1005];
float dp[1005][1005];
#define inf 1e7
float shortest_path(int x, int y){//returns shortest path
//base case
if(x==n && y==m) return 0.0;
if(x>n || y>m) return inf;
//memorization
if(vi[x][y]) return dp[x][y];
//recursive relation
float a,b,c = 20000.0;
if(di[x][y]==1){
a = sqrt(c) + shortest_path(x+1,y+1);//diagonal
b = inf;
}
else
{
a = 100.0 + shortest_path(x+1,y);//left
b = 100.0 + shortest_path(x,y+1);//up
}
float ans = min(a,b);
dp[x][y] = ans;
vi[x][y] = 1;
return dp[x][y];
}
int main(){
cin>>n>>m;
int k;
for (int i = 0; i < n*m; ++i)
{
for (int j = 0; j < n*m; ++j)
{
di[i][j] = 0;
vi[i][j]=0;
dp[i][j]=0;
}
}
cin>>k;
for (int i = 0; i < k; ++i)
{
int a,b;
cin>>a>>b;
di[a-1][b-1] = 1;
}
cout<<round(shortest_path(0,0))<<endl;
} | | Wrong answer on 6th test. Please help:) | Georgi_georgiev | 1119. Metro | 12 Jul 2020 13:24 | 14 |
Edited by author 04.06.2009 17:47
Edited by author 04.06.2009 17:47 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
Can you figure out where you are wrong?
Would you please print the test's result out? 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 No subject [TH2011/03]Ho Vo Thanh Trong 22 Nov 2012 15:32 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 Thank you wery much, there are very good tests, I got AC :) tanhk you the test are graet thank you very much for tests!!! Thanks! You are breathtaking) | | An O(K^2) solution | CmYkRgB123 | 1119. Metro | 30 Mar 2020 23:12 | 3 | 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:22A 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解决。 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. | | A better solution | ComebackSeason | 1119. Metro | 9 Jan 2019 20:32 | 4 | I got an AC with dynamic programming and without a graph and I am frustrated with my memory consumption. I used C++ for this and i've got 0,31s and 16000 KB. I guess my solution consumed so much memory because I've stored 2 matrices, one for grid second for diagonales.
Matrix[i][j] = min (Matrix[i-1][j]+100, Matrix[i][j-1]+100, Matrix[i-1][j-1] + Diag[i][j])
where Diag[i][j] is either 100 * sqrt(2) or Infinity.
I wonder if there is a better solution. I think a simple BFS could give me an answer, Bellman-Ford and Dijkstra's algorithms will give it for sure though. Nevertheless, I've never worked with a graph where every vertex is a 2D point. How should i store it? vector <int> g[maxN][maxN] ? How do I fill it with values efficently? But when Diag[i][j] get infinity sir I think the main cause of memory consumption is the matrix of DOUBLES. Even a simple array of doubles consumes a lot of memory.
Even for the solution involving graph and shortest paths would use 'huge' amount of memory, since you would also need a 2 dimensional array of doubles (I suppose).
I managed to solve it using 9360KB.
Edited by author 14.06.2018 17:45 a better solution is to use dynamic programming to find the longest increasing sequence of diagonals, which there are 100 at most.
then
```
min = (n + m - maxDiagonals * 2) * distance + maxDiagonals * diagonalDistance
``` | | If you get WA2 | mr_invincible | 1119. Metro | 2 Jun 2018 19:31 | 9 | Test 2 is something like this
3 2
0
Good luck! Thank you very very much , I love u Thank you !!! you test help found my mistake i tested the answer is 500. it's right. but i still get WA 2 | | Comp error | nexerd | 1119. Metro | 19 Mar 2018 16:47 | 2 | while (n>0)
{
b=a;
b=b/pow(10,n-1) - rezult/pow(10,n-1);
for (int i=1;i<10;i++)
if ((b-i>=0)&(b-i-1<0)) rezult += (i)*pow(10,n-1);
n--;
}
/*
if delete :
b=b/pow(10,n-1) - rezult/pow(10,n-1);
for (int i=1;i<10;i++)
if ((b-i>=0)&(b-i-1<0)) rezult += (i)*pow(10,n-1);
- work! */ 1. Which programming language do you use?
2. Did you name the variable for result "rezult" (if there is need to pre-declare variables in yout PL)? | | Need Help TEAST CASE5 | Dewesh Deo Singh | 1119. Metro | 22 Jan 2018 12:24 | 2 | I am getting WA 5 Can anyone provide me the test case 5.. or hint to test case 5.. same with u LOL i WA test 5 :"( | | WA10 test | German | 1119. Metro | 22 Jul 2017 16:34 | 4 | 10 6
8
2 1
2 2
4 5
5 2
5 4
6 5
9 4
10 5
Ansver: 1366 Парень, я не знаю, где ты это взял, но тебе ОГРОМНОЕ спасибо!
С помощью твоих данных нашел ошибку и сдал программу. Спасибо. My program do this test case is correct, but i get WA on 10 test. Pls, anybody write this test! my program pass this too, but I came up with the test which leads to error:
8 8
8
2 7
3 3
4 4
5 4
6 3
6 1
7 2
8 3
answer must be 1424. | | TLE with bfs | sukhad | 1119. Metro | 18 Feb 2017 03:53 | 1 | I am using bfs to solve the problem but still getting TLE. Can anyone suugest the cause? | | for those who use graph & recursion approach | Anton | 1119. Metro | 18 Feb 2017 03:51 | 4 | My graph consists of vertexes, which are points, that allow diagonal crossing. Edge (a, b) exists if and only if (a) strictly south-west from (b). Since graph is built, simple dfs easily helps solve the problem ( length of the longest path in the graph - it's diagonal part of result path ).
To avoid TLE#10 in this approach, memorization should be used.
I know, it's not the best approach, but since constraints are relatively low, it does work.
My AC - 0.015 164 КБ.
I think, Longest increasing subsequence - is better in general case. how you use longest increasing subsequence in this problem ? To avoid TLE#10 in this approach, memorization should be used. Thanks, it helped me) I added functools.lru_cache() decorator for my Python program and got AC :) Shouldn't we use bfs as we require the shortest path? | | There exists O(K^2) solution!!! | c_pp | 1119. Metro | 7 Jan 2017 21:27 | 1 | | | getting Runtime error in test case 3 of metro. Please help | Sushant Bhat | 1119. Metro | 4 Sep 2016 19:34 | 2 | #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 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... | | java AC code | esbybb | 1119. Metro | 14 Jun 2015 17:28 | 3 | Messages should not contain correct solutions.
i use matrix of costs, each step set value of the cell as minimal of the
previous vertical cost + 100,
previous horizontal cost + 100,
previous diagonal cost + 100*sqrt(2)
the answer is Math.round(cost[M][N])
p.s.
cycle is organized from 1 to n, 1 to m inclusively
Edited by author 14.06.2015 17:09 by default diagonal cost is set to MAX_VALUE, it is updated in case of a[i][j]=true, where a is a matrix of allowed to be crossed through diagonally cells also column with index 0 is populated incrementally (cost[0][0]=0, cost[1][0]=100, cost[2][0]=200..)
as well as row with index 0 before the main nested loop starts | | wrong answer 3 | wuqingxin | 1119. Metro | 10 Dec 2014 00:37 | 2 | Could I get the data of the test 3 something like this
1000 1000
0 | | WA 13 Help, pls | Minayev {SESC USU} | 1119. Metro | 2 Nov 2014 17:16 | 1 | this is my bad code #include <vector> #include <iostream> #include <cmath> #include <algorithm> #include <stdio.h> using namespace std; struct poi { int x,y; }; vector<poi> g; int n; int ma=0; vector<int> w; bool compare(poi m,poi mm) { if (m.x>mm.x) { return false; } else { return true; } } void dp(int t,int coun) { if (coun>ma) { ma=coun; } for (int x=t+1; x<n; x++) { if ((g[x].x>g[t].x) and (g[x].y>g[t].y) and (coun+1)>w[x]) { w[x]=coun+1; dp(x,coun+1); } } } int main() { int a,b; poi t; scanf("%d%d%d",&a,&b,&n); w.resize(n); for (int x=0; x<n; x++) { scanf("%d%d",&t.x,&t.y); g.push_back(t); w[x]=0; } sort(g.begin(),g.end(),compare); for (int x=0; x<n; x++) { if (w[x]==0) { w[x]=1; dp(x,1); } } double ras=(a+b-2*ma)*100; ras+=ma*sqrt(20000); printf("%d", int(ras+0.5)); } what is the test №13 |
|
|
