Show all threads Hide all threads Show all messages Hide all messages | !!! AUTHORS PLEASE READ THIS !!! | Ostap Korkuna (LNU) | 1450. Russian Pipelines | 2 Dec 2019 12:01 | 13 | There is a country named [Сensored]. In this country the national instrument is called "balalayka". In the capital of [Сensored] the biggest square is called Red Square... I don't have nothing against [Сensored], but there are some idiots who live there (like Gyrinovskiy), that like to say before think! And what thay say is very politically uncorrect! I hope that authors of the problem are not such idiots. I'd like to wish the authors of the problem to think more before write such things in the problem statement. It would be very nice for you to change the problem statement completly. best regards, Ostap Korkuna. I want to propose you to make your own contest - and I will be really pleased to read another funny story about country named [Censored] ;) Anyway, the task statement offends me in particular and I belive that there are a lot of other respected people, who are offended by such kind of "jokes". In my opinion this "joke" has overstepped the limits of innocents... See, one may feel offended even if I write "the sky is blue". No concrete names of people and country are mentioned. Why do you think the story is about your country I respect very much? There are a lot of countries in the world who deal with Russian gas. Not all of them steal it in fact ;) But if you associate [Censored] with you country - you must have some reasons... More people from your country will complain about this problem - more people may think something politically incorrect about it. But we are not guilty of it, aren't we? Relax, the story is really cool. Maybe next time we will write something funny about the presidential elections in [Censored] ;))) Edited by author 24.04.2006 23:58 Dmitry, it seems that Michael Rybak is not the only man offended by this task statement. Isn't it? As the administrator of this site I DEMAND this task statement to be rewritten. It DOES offend visitors of this site regardless of which coutry is hidden under phrase '[Censored]'. Otherwise you have a choice: either I will change task statement by myself or task will be hidden from public (or completely removed from archive). Everybody who got offended by the statement of this task, let me know about it in this thread. I completely agree with you. Please, avoid offending messages. Just let me know that there are a lot of people who wants Timus to be over politics. And let me know, which solution would you prefer: change of statement or task removal. as Russian citizen i think that shuld corect not only tsk about [cenzored] country but and 1457(about old pop), and ALL task in timus archive wich creat wrong understending about my GREAT matherland :) First, if the statement will be changed by you, all our twenty problems will be locked until we may come to some decision. And lots of programmers who have sense of humour and want to solve these problems will thank you very much for what you achieved because of several malcontents. Second, now Ilya Grebnov, Nikita Rybak and me are trying to think out something. We need at least one day to do it. Third, if you think it is so just and noble of you to put pressure upon us, you are mistaken. You forget something. We are not your subordinates. You do not pay us money for what we are doing here - for the sake of Timus Online Judge by the way. As you could see, our contests are much more popular than any contests before. We are still the Top Coders. So try to learn to respect us - at least as this site's best programmers - OK? P.S. Now we are working at "Pascal vs. C++. Version 2" problem which is going to be added to the Volume 4 soon. But because of you we had to slow down our activity. Thank you very much, it is very useful for Timus. ============================================================ IBM is short, Pascal is forever! Edited by author 25.04.2006 03:04 Our, i'm so impressed by you kindness, really , yes you won't get paid for changing problem statement, but i'd like to inform you that in civilized world there exists such thing as "law" and your problem can be recognized as offending honour of some country and peoople, so try be more carefull in future plz. Of course i understand that changing problem statement is a really exhausting job, so thank you for this great effort! No one wants to put pressure on you! We just want to make problem statements nonpolitical and inoffensive. You may assume it as a basic rules of this site. JOKE? Where is a joke? Your Country repeatedly do it. And every time your Goverment with the disgrace plead guilty. You may call it "technical selection of gas" but we call a spade a spade. Goverment plead guilty and I don't understand why you think that the statement is pollitically incorect. We know that our geverment nothing better. And we say about it, for example, in the statement of problem # 1457 Edited by author 17.06.2006 16:44 o_O Alex Tolstov (Vologda STU) 28 Jul 2009 21:56 respect to authors. others can kill themselves by hitting the wall. Re: o_O Moonstone 15 Aug 2010 20:24 Can anybody upload original statement? Школота detected. Such an intellectual "humor" from authors. It was kind of surprise to find such shet on Timus. Edited by author 02.12.2019 12:02 Edited by author 02.12.2019 12:02 | Wtf is wrong with Test #3 ?!?!?!??! Dijkstra not working here??? | Luka Bulatovic | 1450. Russian Pipelines | 29 Jan 2019 17:38 | 4 | I did Dijkstra algorithm for S to F, but seems to exceeds time on test #3 ? Anyone got a clue? Tnx in advance Well, I do not know what this test is, but the answer for this test is "No solution". I don't know how to solve this problem with Dijkstra algorithm. My approach is another. Perhaps one pair of tests below can help you to understand the problem more clearely: 7 7 1 2 10 2 3 10 3 4 5 1 5 1 5 6 50 6 7 50 7 3 50 1 4 ans: 156 7 7 1 2 10 2 3 10 3 4 5 1 5 50 5 6 50 6 7 50 7 3 50 1 4 ans: 205 What you need to do is to find the path with maximum weights of all edges while Dijkstra tries to find minimum. You're solving the wrong problem. | Wrong Answer #5 Some test please | Manflack | 1450. Russian Pipelines | 7 Jul 2017 00:10 | 1 | #include <iostream> #include <vector> #include <queue> #define INF (1<<29) using namespace std; struct Arista { int hasta,costo; }; Arista armar(int h,int c) { Arista ar; ar.hasta=h; ar.costo=c; return ar; } struct Grafo { int suma=0; vector <vector <Arista>> adj; vector <int> dist; vector <bool> visitado; bool encontro=false; int nodos,aristas; int S,F; void leer() { cin >> nodos >> aristas; adj.resize(nodos+1); dist.resize(nodos+1,INF); visitado.resize(nodos+1,false); int desde,hasta,costo; for(int c=0; c<aristas; c++) { cin >> desde >> hasta >> costo; adj[desde].push_back(armar(hasta,costo)); } cin >> S >> F; dist[S]=0; } void bdfs(int nodo, int padre) { visitado[nodo]=true;
for(int c=0; c<adj[nodo].size(); c++) { int vecino=adj[nodo][c].hasta; int costo=adj[nodo][c].costo; if(dist[vecino]>dist[nodo]+costo&&visitado[vecino]==false) { dist[vecino]=dist[nodo]+costo; bdfs(vecino,nodo); } } } void start() { if(dist[F]<INF) cout << dist[F]; else cout << "No solution"; } }; int main() { Grafo g; g.leer(); g.bdfs(g.S,-1); g.start(); cout << endl; return 0; } BFS+DFS Some test, guys? | WA 9. Give me some tests, please! | spuntik_ua | 1450. Russian Pipelines | 5 Feb 2016 14:05 | 1 | WA 9. Give me some tests, please! | What is test case #3? | Suchith J N | 1450. Russian Pipelines | 7 Jan 2015 08:54 | 1 | I'm repeatedly getting WA in Test#3. I converted all weights to negative and used Bellman-Ford. I also checked if the destination is reachable from the source. Nevertheless, I'm getting WA in the same test case. Could someone give me test case #3? | for those who have WA10 | Vladislav | 1450. Russian Pipelines | 30 Mar 2014 19:07 | 1 | If you use topological sort, and then use dp, you should check that there is a way from s to vertex from which you want to get to the next vertex. | WA 11. Give me some tests, please! | Marshal | 1450. Russian Pipelines | 25 Jun 2013 13:31 | 4 | Somebody.... Anybody... Help I have WA#11 too. Please help me. give me some tests or any hint. Edited by author 23.01.2007 21:09 I have WA#11 too. Please help me. | Ford - Bellman | Ivan | 1450. Russian Pipelines | 25 Jun 2013 13:29 | 1 | My solution is very simple. All weight of edges are inverted((a)->(-a)). Ford-Bellman! | WA#7 | khanh45a3kct | 1450. Russian Pipelines | 11 Jun 2013 18:53 | 2 | WA#7 khanh45a3kct 23 Feb 2007 10:48 Re: WA#7 Ivan Tyamgin (TNU) 11 Jun 2013 18:53 | TL # 10 | Enigma [UB of TUIT] | 1450. Russian Pipelines | 17 May 2012 23:11 | 2 | TL # 10 Enigma [UB of TUIT] 14 Oct 2011 21:28 I have a TL#10, I did Dijkstra's algarithm !!! Tel me please better algarithm than Dijkstra. | This problem is very easy! | Andrew Sboev | 1450. Russian Pipelines | 8 May 2012 13:08 | 1 | 1) Don't forget, that you have a directed graph! 2) Also don't forget, that standard C++ streams(cin and cout) are very slow! Use scanf and printf. 3) And just use Bellman–Ford algorithm. It works by O(n*m) - in the worst case. Edited by author 08.05.2012 13:16 | who solve this task, what answer for this test??? | Crash_access_violation | 1450. Russian Pipelines | 3 Feb 2012 16:21 | 4 | what answer for this test : 6 7 1 3 5 1 4 10 2 1 5 3 2 5 5 1 1 6 1 2 6 5 2 6 4 13 or 27? thX You have a cycle! 1->3 3->2 2->1 right answer is 28` 6-5-1-3-2-1-4 Read Oleg's comment above... This test is incorrect | Hints for all who has TL and especially for C# and Java coders | Leonid (SLenik) Andrievskiy | 1450. Russian Pipelines | 16 Sep 2011 05:42 | 1 | 0. Use DFS to find all vertices reachable from the start and exclude others from further steps. 1. Use O(m + n) algo. 2. [For C# coders] do not use List or SortedList or even Dictionary! And do not use foreach! 3. Use the fastest input parser you have. For example my parser looks like this: using System; using System.Collections; using System.Collections.Generic; using System.IO; using System.Text; namespace _1450__acm.timus.ru_ { class SerialInput { private static Dictionary<int, int> separators = new Dictionary<int, int> { { ' ', 0 }, { '\n', 0 }, { '\r', 0 } }; private StreamReader reader; public SerialInput(StreamReader reader) { this.reader = reader; } public int ReadInt() { while (separators.ContainsKey(reader.Peek())) reader.Read(); int symbol = reader.Read(); int value = 0; while ((symbol != -1) && !separators.ContainsKey(symbol)) { value = value * 10 + (symbol - '0'); symbol = reader.Read(); } return value; } } class Program { static void Main() { const int InputBufferSize = 65536; const int OutputBufferSize = 65536; #if (ONLINE_JUDGE) var input = new SerialInput( new StreamReader(Console.OpenStandardInput(InputBufferSize))); var output = new StreamWriter(Console.OpenStandardOutput(OutputBufferSize)); #else var input = new SerialInput( new StreamReader(new FileStream(@"..\..\input.txt", FileMode.Open, FileAccess.Read, FileShare.Read, InputBufferSize))); var output = new StreamWriter(new FileStream(@"..\..\output.txt", FileMode.Create, FileAccess.Write, FileShare.Write, OutputBufferSize)); #endif int n = input.ReadInt(), m = input.ReadInt(); // write your code here output.Flush(); } } } | Can the route go twice through the same vertics? | patryksharks321 | 1450. Russian Pipelines | 26 Jul 2009 21:17 | 3 | Like in the topic can the route of piplines go 2 through the same vertics? That means it goes through and there is a cycle and it returns again through the same vertics and then goes on further The text says "More over, if it is possible to transfer the gas from the station X to the station Y (perhaps, through some intermediate stations), then the reverse transfer from Y to X is impossible." which I think means it can't but I am not sure(?) I would be greatfull for any help, and please no comments - "no comment" better not write at all There is no cycles. So the route can't go twice through the same transfer station. As I thought but I just wanted to be sure Thank you very much | TLE 17 | THE_SCORPION | 1450. Russian Pipelines | 22 Jun 2009 02:27 | 5 | TLE 17 THE_SCORPION 30 Sep 2006 19:13 My program works very quickly, but I have time limit. I tested my programm many times. In all test time working is not more than 0,2 sec(even with 500 tops and 124750 edges). Maybe somebody can tell me what is thе 17 test or what is the special trick in this test? Re: TLE 17 Kaliningrad SU -J_A_MES-HeadLiner 30 Sep 2006 21:39 Use DP with presorting of course Edited by author 30.09.2006 21:42 It's another problem, where i can TLE troubles with Java. I implemented fastest and correct(!) solution : topological sort + relaxes according to resulting order of vertexes. It works in o(m + n) time, and executing time is very small (0.16 - 0.2 sec) on my computer. I also tried many classes of input/output, but nothing helps. Pls tell me, how can i AC it using Java... OMG, I just wrote this algo using C++, and AC in 0.125. Your java compiler is very bad... maybe you have problems with processing input/output(in java it's too slow) i've used ford-bellman algorithm (0.380 sec) | Looks like they did it again :) (+) | Dmitry 'Diman_YES' Kovalioff. On the brink of retirement | 1450. Russian Pipelines | 8 Jan 2009 01:13 | 2 | Sorry for the offtop, but still... To the situation nowadays, I can only praise my colleagues and myself for the problem statement that remains actual despite three years passed since the contest was held. Long life this problem! :) | WA6 | Kirin Vladislav | 1450. Russian Pipelines | 8 Jul 2008 00:32 | 6 | WA6 Kirin Vladislav 26 Feb 2007 11:59 WA6. What's wrong? Give some test's. In my solution I used Deixtra algo. Re: WA6 Anton [SUrSU] 26 Feb 2007 14:25 Why Dijkstra? Simple dfs for topsort and then dp. Re: WA6 @ntiFreeze 27 Feb 2007 00:57 I think this problem could not be solved with dijkstra. Simple dfs for topsort and then dp or simple BFS :) i used FLOYD's algo and have TLE15. i used Djkstra's algo and i have WA10.. pls, can you give me some tests or what's bug in my program? {$APPTYPE CONSOLE} uses SysUtils; var a:array [1..1000,1..1000] of longint; mas:array [1..1000] of longint; used:array [1..1000] of boolean; i,n,m,t,f:longint; procedure djkstra(st:longint); var cur,i:longint; begin fillchar(mas,sizeof(mas),255); fillchar(used,sizeof(used),0); cur:=st; mas[cur]:=0; repeat used[cur]:=true; for i:=1 to n do if (a[cur,i]<>0) and (mas[i]<mas[cur]+a[cur,i]) then mas[i]:=mas[cur]+a[cur,i]; cur:=0; for i:=1 to n do if not used[i] and (mas[i]<>-1)and ((cur=0)or (mas[cur]>mas[i])) then cur:=i; until cur=0; end; begin read(n,m); for i:=1 to m do begin read(t,f); read(a[t,f]); end; read(t,f); djkstra(t); if mas[f]<>-1 then write(mas[f]) else write('No solution'); halt(0); end. and what to do if there is cycle? Edited by author 16.04.2008 21:52 Edited by author 16.04.2008 21:56 Edited by author 16.04.2008 22:55 i've changed djkstra like this <code>procedure djkstra(x:longint); var cur,i:longint; begin fillchar(v,sizeof(v),-1); fillchar(used,sizeof(used),0); v[x]:=0; cur:=x; repeat used[cur]:=true; for i:=1 to n do if (a[cur,i]<>0) and ((v[i]=-1)or (v[i]<v[cur]+a[cur,i])) then begin v[i]:=v[cur]+a[cur,i]; used[i]:=false; end; cur:=0; for i:=1 to n do if not used[i] and (v[i]<>-1)and((cur=0)or (v[cur]<v[i])) then cur:=i; until cur =0; end;</code> and it's tle#15((( | If you have WA9 (+) | Ikari [pskov] - Andrey Marchenko | 1450. Russian Pipelines | 23 May 2008 22:08 | 1 | Try this test: 6 7 6 5 10 1 4 11 1 2 4 3 1 5 2 4 5 6 3 1 6 1 3 5 4 Thanks authors for good problem with funny statement)) Edited by author 23.05.2008 22:10 | WA#12 | Carbon | 1450. Russian Pipelines | 30 Jan 2008 01:15 | 1 | WA#12 Carbon 30 Jan 2008 01:15 My program doesn't work on this test. Please, tell me what's wrong with it: #include <stdio.h> int C[500][500],R[500][500],U[500],T[500]; int main(int argc, char* argv[]) { int N,M,start,finish,s,a,b,c,S,F,i,j,u; scanf("%d%d",&N,&M); start=N; s=N-1; for (i=0;i<M;i++) { scanf("%d%d%d",&a,&b,&c); C[a-1][b-1]=c; T[a-1]++; } scanf("%d%d",&S,&F); S--; F--; U[s]=F; for (i=0;i<N;i++) if (i!=S&&i!=F&&T[i]==0) { s--; U[s]=i; } do { finish=start-1; start=s; for (i=finish;i>=start;i--) { b=U[i]; for (j=0;j<N;j++) if (C[j][b]!=0&&j!=S) { T[j]--; if (T[j]==0) { s--; U[s]=j; } } } } while (s<start); U[0]=S; for (i=0;i<N;i++) { a=U[i]; for (j=0;j<N;j++) R[i][j]=C[a][j]; } for (i=0;i<N;i++) { b=U[i]; U[i]=-1; for (j=0;j<N;j++) C[j][i]=R[j][b]; } U[N-1]=0; for (i=N-2;i>=0;i--) { for (j=i+1;j<N;j++) if (C[i][j]!=0&&U[j]!=-1) { u=C[i][j]+U[j]; if (u>U[i]) U[i]=u; } } if (U[0]==-1) printf("No solution"); else printf("%d",U[0]); return 0; } | Why WA 10. Any special trick about this test | SPIRiT | 1450. Russian Pipelines | 24 Feb 2007 23:39 | 6 | Sorry, I got AC. Haven't noticed a slight trick. Well, it's a DAG. Therefore you can simply use DFS, that's all. What trick???? I have WA 10 too....... Could anybody give me a test to solve this problem? My program works correctly whith MY tests and whith the first 9 timus tests)... Why you trying to razvesti us? It's not a DFS, it's Deykstra algo or maybe Floid-Warshal Lol. So, try to solve problem with your algo especially for N<=500. |
|
|