This firstly happens in 8th test. If you have WA on test #3 or on test #1 or on test #2 you must use DP! Else if you have WA on test #4 you must use unsigned int or int 64 or long. If you have WA on test #8 you must change start and finish points ( 6-2 and 2-6 is equal ) !^_^! Thanks a lot for WA 8.I got AC.^^ Thank you. I got WA at #8.And I have ACed now; Thank you from reminding! Thank you for your suggestion Thank you very very much! thx a lot!! If you have WA8 and use Binary Search - check that it work properly, i.e. return far station instead of nearest Edited by author 03.12.2010 00:05 thank u very much for the 2nd suggestion. first i got wa4 and then wa8..your message help a lot! thank you. Thanks a lot for WA #8! It's really tricky. first i got wa14 and forgot to use long long.your message help a lot! thank you. Можно считать, что мы имеем ориентированный взвешенный граф, у которого максимальная степень вершины равна трём . Равна она трём потому, что нам всегда выгодно ехать как можно дальше, потому что мы заплатили за всю дистанцию. То есть из какой-то станции ребра с весами C1, C2 и C3 проводим в как можно более далёкие станции. Тогда это получается очень сильно разреженный граф, так как N<=1e4. На этом графе запускаем алгоритм Дейкстры для разреженных графов. Я использовал вариант за O(Nlog2N) с std :: set. Для расчёта того, куда проводить ребра, я использовал бинарный поиск. И немного запорол реализацию этого поиска. Мой поиск возвращал первую станцию, которая находится дальше, чем разрешено. И возвращал он некорректное значение, если не было такой станции. Это послужило причиной WA#6. Причиной WA#2 послужило то, что я забыл сделать обновление расстояния до пункта назначения. Так как ребра идут жадно, то пункт назначения проезжался и в очередь не попадал, и расстояние соответственно никогда не обновлялось. i meet the same WA#5.may be the reason is you assume if distance of start and end is less than L3 then cost is C3. but it may be c1+c2 c1+c1 or c2+c2 instead. 3 6 8 20 30 40 7 1 6 3 7 8 13 15 23 //answer: 80
3 6 8 20 30 40 7 3 6 3 7 8 13 15 23 //answer: 40
3 6 8 20 30 40 7 2 5 3 7 8 13 15 23 //answer: 60
1 2 3 1 1000 1000000000 2 1 2 1 //answer: 1
1 2 3 1 1000 1000000000 2 2 1 1 //answer: 1 all test case passed.but meet WA5 My solution runs in O(N logN) and it uses heap data structure. The discussion forums hint that there may be a O(N) time solution. Is there a linear time algorithm? heap?:D just use lower_bound And, BTW, Yes there is. At first I used Binary Search on each station but on the next station you can start with the previous index. code: int canReach1 = A[i] + L1; while (ind1 <= end && A[ind1] <= canReach1) ind1 ++; i've used dp (which is easy to notice) with some optimization. suppose we have three stations s1 s2 s3 and there exists path s1-s2 covered with l1, and path s1-s3 also covered with l1. then we can skip the analysis from s2. we can easily reduce used time if we create list of "allowed" stations to analyze (like s3) I already change start and finish points but still WA #8…… this is my coad #include<iostream> using namespace std; const int maxn=10005; long long f[maxn][maxn]; int cost[4]; int d[4]; int a[maxn]; int main() { freopen("in.txt","r",stdin); for(int i=1;i<=3;i++) cin>>d[i]; for(int i=1;i<=3;i++) cin>>cost[i]; int n; cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=INT_MAX; int s,e; cin>>s>>e; for(int i=2;i<=n;i++) { cin>>a[i]; int temp=a[i]-a[i-1]; if(temp>d[2]) temp=cost[3]; else if(temp>d[1]) temp=cost[2]; else temp=cost[1]; f[i-1][i]=temp; } for(int i=1;i<=n;i++) f[i][i]=0; for(int p=2;p<=n;p++) for(int i=1;i<=n-p;i++) for(int j=i+1;j<=i+p;j++) { int k=1; while(1) { if(j-k<=i) break; if(a[j]-a[j-k]>d[3])break; if(a[j]-a[j-k]>d[2]) f[i][j]=min(f[i][j],f[i][j-k]+cost[3]); else if(a[j]-a[j-k]>d[1]) f[i][j]=min(f[i][j],f[i][j-k]+cost[2]); else f[i][j]=min(f[i][j],f[i][j-k]+cost[1]); k++; } k=1; while(1) { if(i+k>=j) break; if(a[i+k]-a[i]>d[3]) break; if(a[i+k]-a[i]>d[2]) f[i][j]=min(f[i][j],f[i+k][j]+cost[3]); else if(a[i+k]-a[i]>d[1]) f[i][j]=min(f[i][j],f[i+k][j]+cost[2]); else f[i][j]=min(f[i][j],f[i+k][j]+cost[1]); k++; } } int aaa=min(s,e); int bbb=max(e,s); cout<<f[aaa][bbb]<<endl; return 0; } i think you should solve it yourself..we got wronganswer because of bad thinking habit try this test case: 1 2 3 1 2 3 2 2 1 1 ans = 1 Edited by author 30.10.2014 08:37 you should set distance of station 1 = 0, as input: distance from 1 to 2 = 2 3 100 10000 100 101 102 35 1 34 0 3 3 3 ... 3 99 100 i guess the answer is 201(1-35-34) can DP give this answer? i think only ShortestPath can give this answer. It's wrong answer. Right answer is 101. I agree with you. for example 1 2 100 100 100 1 4 2 3 2 3 99 when I used this input,my AC programm gave the answer 100 while the correct answer was 2 Distances are different(!) integer numbers given in ascending order. So this test isn't correct. Edited by author 10.05.2012 20:35 hey @bill125 if L2 < X ≤ L3 then cost is C3. // from table in problem statement if 2 < X ≤ 100 then cost is 1 . As X is 1 you can't use C3=1. According to the problem statment 1 ≤ L1 < L2 < L3 ≤ 10 ** 9, 1 ≤ C1 < C2 < C3 ≤ 10 ** 9 but test #10 fails with integers (32-bit) for Li and Ci. I fixed WA #10 by lowering my infinity constant to 1100000000. This is my program: [code deleted] Be careful of the s and t.In TEST#8,s>t. Edited by moderator 23.10.2019 08:45 Thanks a lot That last line you wrote got me through :) Could you please give me the file of test node #11??? why time limit? n*(n+1)/2 operations: import java.util.*; public class RailwayTickets { public static long l1,l2,l3,c1,c2,c3,n; public static int s,t; public static long f(long k) { if (k>0 && k<=l1) return c1; else if (k>l1 && k<=l2) return c2; else if (k>l2 && k<=l3) return c3; return Long.MAX_VALUE; } public static void main(String args[]) { Scanner in = new Scanner(System.in); l1=in.nextLong();l2=in.nextLong();l3=in.nextLong();c1=in.nextLong();c2=in.nextLong();c3=in.nextLong();n=in.nextLong();s=in.nextInt();t=in.nextInt(); long[] d = new long[10001], c = new long[10001]; if (s>t) {int yed=s;s=t;t=yed;}; for (int i=2;i<=n;i++) c[i]=in.nextLong(); for (int i=1;i<=n;i++) d[i]=Long.MAX_VALUE; d[s]=0; for (int i=s+1;i<=t;i++) for (int j=s;j<i;j++) if (d[i]>d[j]+f(c[i]-c[j])) d[i]=d[j]+f(c[i]-c[j]); System.out.println(d[t]); } } Edited by author 01.12.2011 15:34 Try to use c++ to solve this problem or think about better algorithm))) And you read not very fast)) Try to use stream tokenizer)) Edited by author 16.06.2012 22:14 Hi, could you post the test 11 data?.. I made my code but it's always crashing on this test. who is answer it now,i had passed today, simple DP What a poor English :) Did anybody get what he was going to say? not really.. haha =) probably he's just bragging that he got it! =) I have used DP to solve.. but I find 2 man is 0.031. is there a faster algorithm? faster algorithm time = 0.015 Super faster = 0.001 Even simple N*logN works in 0.031. And O(N) solutions... I use DP do solve it,like LIS. Who can give me testdata of test8?please. Test #8: 1 2 3 1 1000 1000000000 2 1 2 1 Thanks a lot.I got AC! Why did you have the test of this problem ? Would you please give me the link to download them ? My answer for this test is 1 ! But I haven't got AC yet ! Is "1" an accurate figure ? What is your answer ? 1 2 3 1 1000 1000000000 2 1 2 1 The right answer is "1" The text should be like this: 1 2 3 1 1000 1000000000 2 2 1 1 ans:=1 Hint:you can start at a large number and end at a small number. Hint: start station number can be greater than end station number. I've got WA on test #8 too, but when i made start<finish then i've got AC. thx,start>finish the case i didn't find p.s if you use pascal,this program do not use qword i used it and got tle.鲜红鲜红的,倍吓人 Hey! Look at the following RULES! * Messages should be written in English. Please translate that"鲜红鲜红的,倍吓人"! 鲜红鲜红的,倍吓人 means tle looks read.... PS:panpasixiongying(name),I use qword and tle.. > The Time complexity is o(n^2),is it fast enough? >>The Time complexity is o(n^2),is it fast enough? I think yes, but there is a rather simple solution with the complexity of O(n). It's really simple, just do some thinking :o) Besides, I think I can't explain the idea in English... :( Yes...You can use DP to solve.but not DFS or other searching method.. |
|