Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Such easy problem , A big Hint ! | XueMao | 1115. Корабли | 27 дек 2022 23:34 | 4 |
you can only use dfs , but don't forget to sort the team . When I use sorting as from short to long , I got TL , but when from long to short , only 0.02s ! I sort from long to short, but still Time Limited Exceeded. Can you tell me why? :) Edited by author 23.12.2018 21:36 Edited by author 23.12.2018 21:39 I was expecting TLE, because I use O(N^N), but in fact got AC in 0.015 I wonder if people who get TLE are doing something like O(N^N^N^π^e) lol |
Same code - AC on 1115, WA11 on 1394 | Hristo Nikolaev (B&W) | 1115. Корабли | 27 дек 2022 23:30 | 1 |
Apparently, this is a very complicated problem, but 1115 allows solutions with naive implementations. I almost used brute force here, with some little optimizations (like looking for solutions for the next few sums while working on the 'current' one). |
is this TEST10 ? | esbybb | 1115. Корабли | 12 окт 2016 22:56 | 3 |
maybe this? 8 3 2 10 10 11 16 16 18 21 39 32 33 10 11 18 16 16 2 10 21 AC java 0.14 = for (int i=0; i<R; i++) { int retcode = s(i); if (retcode==-1) { i=-1; } } int s(int row) { .. //some backtracking call bt(list_of_added, left, r) .. if (errorwith_this_row) {//error row will be processed first, reprocess all rows int reg = L[r]; for (int i=r; i>0; i--) { L[i]=L[i-1]; } L[0]=reg; return -1; } .. return 0; } bt(list_of_added, left, r) { if (list_of_added.size=0) return -1; index=list_of_added.removelast left+=l[index]; //greedy adding itemd to list_of_added, decrease 'left'
if (left>0) bt(list_of_added, left, r);
} also i use marked[] with indexes of rows were needed, i use Lorig[], L[] (sorted Lorig[]) and id[], and ID[] (indexes of original lengths in Lorig) |
Please help with solution | g00d | 1115. Корабли | 15 апр 2016 03:30 | 2 |
I wrote program on Python 3, but second test is wrong for me. Why? I need a hint. Maybe, you can wrote test for my program? Idea: 1. sort length descending 2. take first that smaller SUM in row 3. reduce SUM and colored ship 4. take next 5. finally for SUM if they == 0 -> go to next row My solution: [n, m] = [ int(x) for x in input().split() ] a = [] for i in range(n): a.append(int(input())) b = [] for i in range(m): b.append(int(input())) a.sort(reverse=True) color = [-1 for x in range(n)] i = 0 while i < m: s = b[i] z = 0 while z < n: aa = [] j = z while s > 0: while j < n and a[j] > s : j += 1 if j >= n: for ee in aa: s += a[ee] color[ee] = -1 aa = [] break elif color[j] != -1: j += 1 else: s = s - a[j] aa.append(j) color[j] = i z += 1 if s == 0: break i += 1 for i in range(m): aa = [] cnt = 0 for j in range(n): if color[j] == i: aa.append(a[j]) cnt += 1 print(cnt) aa.sort(reverse=True) ab = [str(x) for x in aa] ss = " ".join(ab) print(ss) please, never post your code here! use pastebin or ideone! |
Is the length of the row exactly the same as the sum of the length of ships in it? | yuelin | 1115. Корабли | 13 фев 2016 14:41 | 2 |
I am not sure, but I think yes! |
WA10, ask for test case | invokerj | 1115. Корабли | 28 дек 2013 15:46 | 1 |
any good test case, thanks |
help please | antonluzhbin | 1115. Корабли | 23 мар 2012 12:08 | 1 |
help. send please the test 1 for mail antonluzhbin@yandex.ru |
Is there only one solution for test? | Max | 1115. Корабли | 1 мар 2012 00:35 | 1 |
Is there only one solution for test?? |
ship and row's length can be zero | Enzo | 1115. Корабли | 18 июн 2010 19:32 | 1 |
but i still can't pass test 10 what's in it? |
Whole numbers? | SkidanovAlex | 1115. Корабли | 8 янв 2010 16:27 | 3 |
Is it really appropriate to translate 'целые числа' as 'whole numbers'? short, int, long etc... ;) |
My AC solution | Denis Koshman | 1115. Корабли | 1 фев 2009 22:10 | 3 |
I write it here because there exist data sets which will TL it out. 1. Sort rows ascendingly 2. Sort ships descendingly 3. Recurse row-by-row, ship-by-ship 4. Keep ships in the linked list, so you don't have to skip them over and over once they are taken. 5. For each row try only next ships (1+2+3 is same as 1+3+2). 6. Once you reach the last row, don't recurse over it, just pick remaining ships. This yields AC in 0.015 sec More optimizations can be done: 1. For each row store index of the first ship which fits in it (don't forget to skip this ship(s) if it's already taken by the time you reach the row) 2. Store amounts of same-size ships, so that 2+2 is processed only once with 6 ships of size 2, but not C(2,6) times. Edited by author 30.07.2008 14:41 Tests in this problem are quite stupid. I've got AC with BF in 0.015! When I stored amounts of same-size ships, I've got TLE #7 many times with all kinds of optimization. Really bad problem, surely must be replaced. |
What's wrong with my code? I got WA on Test #2 | Yuplis | 1115. Корабли | 29 ноя 2008 09:41 | 2 |
//Please, don't post your codes here. #include <stdio.h> #include <string.h> #define infile "1115.in" #define outfile "1115.out" int main() { init(); work(); print(); return 0; } Edited by moderator 16.04.2004 18:16 May be you had sort the teams of ships. Edited by author 29.11.2008 10:14 |
I just used DFS and got AC with 0.001s! | Fu Dong | 1115. Корабли | 26 авг 2007 16:57 | 4 |
850784 15:24:03 20 May 2005 Fu Dong 1115 Pascal Accepted 0.001 141 KB I think the most important thing to this problem is to sort ships' length. First I sorted them from short to long, but I got TLE on test #8, then I sorted from long to short, to my surprise, I got AC with 0.001s! My solution is not DFS ! I think it O(x*n*MaxL) with MaxL = Max( length row[i] , i=1..n ) . But I haven't define how much x does yet ! Maybe x <= 10 ! I don't think your program run faster than mine because the test are not so hard. To N.M.Hieu ( DHSP ): What's your way? Sorry , I'm mistaken . Mine is backtracking . At that time , I was too young , so ... I used DP to reduce the time of searching in bad result . It's hard to say clearly due to my bad english . If you want , leave me your email-address , I will mail you my solution , it's not good to pass the tests of problem 1394 ( Ship versions 2 ) but enough to pass those of this problem . |
To "Fu Dong" : Do you have to sort row's length? Thanks | Nguyễn Đình Tư (DHSP) | 1115. Корабли | 22 авг 2007 14:07 | 5 |
Edited by author 10.07.2005 23:49 Edited by author 10.07.2005 23:50 I will mail my solution for you ! I accepted in 0.046s and used 337 KB Plz email me... cpp_student@163.com THX PLZ!!!!! I'll appriciated To sort is a quite good way to save time. |
I had done my best but my program still be tle on test 14...need help... | FailedWing | 1115. Корабли | 16 авг 2007 19:20 | 2 |
var n, m : longint; f : boolean; done : array[1..100] of boolean; put : array[1..100, 0..100] of longint; board : array[1..100] of longint; row, order : array[0..10] of longint; procedure sort; var i, j, x, y : longint; begin for i := 1 to n - 1 do for j := i + 1 to n do if board[i] < board[j] then begin x := board[i]; board[i] := board[j]; board[j] := x; end; for i := 1 to m - 1 do for j := i + 1 to m do if row[i] < row[j] then begin x := row[i]; row[i] := row[j]; row[j] := x; x := order[i]; order[i] := order[j]; order[j] := x; end; end; procedure init; var i, j, x : longint; begin readln(n, m); f := false; fillchar(put, sizeof(put), 0); fillchar(done, sizeof(done), false); for i := 1 to n do begin readln(board[i]); end; row[0] := 0; for i := 1 to m do begin readln(row[i]); order[i] := i; end; end; procedure print; var i, j, l : longint; begin for i := 1 to m do begin writeln(put[i, 0]); for j := 1 to put[i, 0] do write(put[i, j], ' '); writeln; end; halt; end; procedure make(k : longint); var i : longint; begin if f then exit; if (k = m + 1) then begin print; f := true; exit; end; for i := 1 to n do if (not done[i]) and (board[i] <= row[k]) then begin done[i] := true; dec(row[k], board[i]); inc(put[order[k], 0]); put[order[k], put[order[k], 0]] := board[i]; make(k + ord(row[k] = 0)); if f then exit; dec(put[order[k], 0]); inc(row[k], board[i]); done[i] := false; end; end; begin init; sort; make(1); end. Add "Program URAL1115 in the front" Get a compiler Don't waste time~~~ |
I've past it | cai niao | 1115. Корабли | 16 авг 2007 19:15 | 2 |
Yes, I passed it just by searching. But firstly I sorted the ships from short to long, then it was easy to cut the useless branch and retrace when necessary. I'm tired of getting WA Plz email me your code... cpp_student@163.com THX :D |
ACed in 0.001 :D | shrek | 1115. Корабли | 2 ноя 2006 11:10 | 1 |
I used knapsack to find all the ways in order to fill a row and solved the problem for other rows with remained ships. |
I can't understand the problem (at least I get WA1) | Tbilisi SU: Eldar Bogdanov | 1115. Корабли | 1 ноя 2006 19:07 | 3 |
I have some questions about the problem's statement: 1. Is the sum of lengths of the ships equal to the sum of the lengths of the rows? 2. What is the maximum length of a single row? 3. Should I output the lengths in each row in ascending order or in any order I like? I've got WA1 :rolleyes: My program gives this output on the sample test: 3 5 2 4 2 3 10 1.Yes they are. 2.maximum length is sum of ships' length 100*100=10000 3.you can output in any order you like |
Problem 1115 "Ships". New tests? | Vladimir Yakovlev (USU) | 1115. Корабли | 24 авг 2006 11:54 | 14 |
I know you all submit heuristics and get AC. In fact, tests are very easy to pass. I can change it. I have new tests. These tests are really good. I think nobody's current solution get AC with these tests. But I have a solution and can't create a test that break it. Do you want me to add this tests? Well, then I'll do it soon. New tests are here. Try it now. Problem will be rejudged soon. Probably ML is 16 MB? (not TL) Is it rejudged now? up Love_** 19 ноя 2005 12:33 2 admins: Please, add new tests. I submit one solution, and it get AC(0.015sec), but I know a lot of tests, in such my prog get TL. For example: 99 9 1 2 6 9 4 4 5 3 9 6 7 1 2 3 2 2 6 9 4 4 4 4 9 8 4 9 5 9 4 5 9 3 7 4 9 8 1 8 5 5 5 5 6 7 9 1 3 5 7 5 4 2 1 7 4 1 5 3 8 4 3 4 5 7 8 5 4 6 8 1 4 1 8 9 1 6 9 2 7 1 2 7 8 1 9 2 1 9 9 5 9 4 6 6 6 7 9 8 4 57 58 44 64 60 52 52 61 64 I can generate smaller TL test... Also, add please tests for 1269 problem. Sorry for my English. Edited by author 23.08.2006 21:28 And a decision was made to create a new problem Timus-1394 "Ships. Version 2" which test set includes the hardest tests Vladimir Yakovlev could imagine. In fact even I did not solve this problem yet... THX. 1394 is really hard problem(TLE24)... Do u know some difficult tests or how to generate it? Then what's your bt solution Now how can we get AC....? I got ACed easily in 0.14s (not this ID!), By adding a little Optimization. TO ADMIN: Did you use MaxFlow to Solve this Problem? If you did, How could you solve the MaxFlow in a short Time? |
Can I use recoursive search ? Help me please | Dostoyevsky | 1115. Корабли | 31 май 2006 04:34 | 1 |
My algorithm is follow. 1.I'm starting to put ships to the most short row ( ships are sorted from shortest to longest and I'm considering them in this order ). 2.I'm trying to put ships with maximum total length as it is possible. So, recoursive searching ( from longest free ships to shortest ) take place. 3.If all ships are already used and there are still free row(s), I put at this row(s) some ship(s) from other row(s) which have already more then one ship. Please, give me some test data or tell me why does such algorithm return WA. Edited by author 01.06.2006 19:20 |