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 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). 6 2 2 10 11 16 16 21 32 33 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) 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! I am not sure, but I think yes! any good test case, thanks help. send please the test 1 for mail antonluzhbin@yandex.ru Is there only one solution for test?? but i still can't pass test 10 what's in it? Is it really appropriate to translate 'целые числа' as 'whole numbers'? short, int, long etc... ;) 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. //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 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 . 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. 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~~~ 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 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 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 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? Please, add it. 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? 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? 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 |
|