Show all threads Hide all threads Show all messages Hide all messages |
WA 25? | Heorhii | 1500. Pass Licenses | 11 Jun 2022 20:11 | 1 |
WA 25? Heorhii 11 Jun 2022 20:11 My program passes all tests created by me, so I don't know what could be the problem with it |
How long it is until this Problem unlocked | DarksideCoder | 1500. Pass Licenses | 17 Mar 2022 19:07 | 1 |
|
is there a polynomial solution to the problem ? | Konstantin | 1500. Pass Licenses | 12 Apr 2019 19:01 | 1 |
|
WA #1 | mezkresh | 1500. Pass Licenses | 6 Jun 2016 17:52 | 1 |
WA #1 mezkresh 6 Jun 2016 17:52 I tried test 1 given in task on my computer and got the same answer. But i get WA #1 wwhen submit |
Changes in problem 1500 Pass Licenses | Vladimir Yakovlev (USU) | 1500. Pass Licenses | 15 Jan 2015 16:16 | 3 |
* Clarification in problem statements: For any pair of crossroads no two segments of the same category connect these crossroads. * Tests not satisfing this condition are corrected. * The first test is changed to the sample from the problem statements. * New time limit is 2.5 seconds (old time limit was 3 seconds). * New memory limit is 64 MB (old memory limit was 16 MB). * New tests are added All solutions are rejudged. More than 100 authors lost AC during this rejudge. * Clarification in problem statements: For any pair of crossroads no two segments of the same category connect these crossroads. Sample test 0 2 0 0 2 1 is this true? * Clarification in problem statements: For any pair of crossroads no two segments of the same category connect these crossroads. Sample test 0 2 0 0 2 1 is this true? Yes, of course! |
Hint: if you got TLE | OpenGL | 1500. Pass Licenses | 22 Dec 2013 09:48 | 3 |
If you got TLE, try change adjacency matrix to edge list. Bitset<30> operation "|" helps to avoid inner N-loop = 、= Using edge list, got TLE. I got AC changed edge list to adjacency matrix. |
(2 ^ k) * (n ^ 2) works in 0.171 | Bekzhan | 1500. Pass Licenses | 9 Oct 2013 03:07 | 2 |
Of course, with a little optimizations :) But not (2 ^ k) * (n ^ 2) * K : )) |
For the TLEers | [NKU]sweet | 1500. Pass Licenses | 6 Jul 2013 23:55 | 2 |
I sort the the 2^k states by the bits it contains, then check the states in order, and always TLE #22 Then, I choose a state randomly in the 2^k states and check if it's legal, and get accepted…… part of my code: 63 int ans = (1 << k) - 1; 64 int tot = 1 << k; 65 int times = 0; 66 while (tot > 0 && (times * realm < (500000000))) { 67 int now = rand() % tot; 68 if (countBit(arr[now]) < countBit(ans)){ 69 memset(visit,0,sizeof(visit)); 70 times++; 71 if (dfs(0,arr[now])) { 72 ans = arr[now]; 73 } 74 } 75 arr[now] = arr[--tot]; 76 } If you use G++, it's better to use standart function (__builtin_popcount(n)) instead of countBit(n) |
WA 14 | mikewu | 1500. Pass Licenses | 5 Apr 2011 09:21 | 3 |
WA 14 mikewu 5 Apr 2011 04:25 need some test plz. no idea whats wrong. thanks. As far as I know, 14 requires the maximum of 20 licenses - which may or may not be an issue for you. It was why I got WA 14. thank you. It is indeed the issue i have. |
Admins, please add this test | Orfest (Novosibirsk SU) | 1500. Pass Licenses | 9 Dec 2010 07:47 | 5 |
I have AC with time 0.953sec, but my solution runs >2sec on a test generated by the following program: #include <cstdio> int main(){ int k = 20; int n = 30; int m = k+k*(((n-k)*(n-k-1))/2); printf("%d %d %d\n",k,n,m); for (int i = 1; i <= k; i++){ printf("%d %d %d\n",i,i+1,i-1); } for (int i = k+1; i < n; i++){ for (int j = i+1; j < n; j++){ for (int l = 0; l < k; l++){ printf("%d %d %d\n",i,j,l); } } for (int l = 0; l < k; l++){ printf("%d %d %d\n",i,0,l); } } return 0; } Admins, please respond. Was the test added? Admins! Please respond! :) Edited by author 08.12.2010 18:16 Thank you for test. It was added and the problem was rejudged. 69 authors lost AC. Great, thanks, I also lost AC :) |
What is the limit for M? | DEF | 1500. Pass Licenses | 2 Mar 2010 13:14 | 5 |
It is not actual. Possibly K*N*(N+1)/2. It's also not actual. It seems to me test#20 has multiedges. In that case M is not limited at all )))) |
I have WA8. Give me some tests. | AiD | 1500. Pass Licenses | 7 Jan 2010 19:20 | 5 |
Give me some tests or write if there are some sly tests. I solve this problem by 2^K*N*N. I have the same problem. Where is bag? Edited by author 09.07.2008 23:49 Also WA8. Give some tests WA8. Small Code, but can not find any bug/ [code cut] Edited by moderator 18.04.2013 21:14 My solution is O(2^k). I think, that main problem's are - how reduce amount of DFS (check the route existence's with current set of licenses) and reduce brute-force to find all possible combinations of licenses. Binary search for number of licenses helped me to avoid TLE. Edited by author 08.01.2010 01:39 |
Getting TLE, Please Help | shilp | 1500. Pass Licenses | 16 Aug 2008 01:00 | 1 |
I am trying to take all possible combinations of k and run union-find to check if 0-1 are connected in that combinations. complexity is O(M(2^K)). is there a faster approach? Edited by author 16.08.2008 01:01 |
K==20 at test #1 (+) | Test | 1500. Pass Licenses | 12 Aug 2008 19:53 | 3 |
K==20 at test #1 And the answer for this test is "2\n0 2", as in the sample Is this test correct? Edited by author 15.02.2007 00:05 You are right. If K would be 20 for the sample test, then the answer will remain the same. I keep receiving WA1 here. Is the 1 test like the sample (except for the K = 20) ? On my machine I'm getting answer as the sample's one |
Changes for 1500 "Pass Licenses" (+) | Vladimir Yakovlev (USU) | 1500. Pass Licenses | 30 Oct 2006 14:06 | 1 |
Problem statement was updated: • "N >= 2" instead of "N >= 1" • "Crossroads are numbered from 0 to N – 1, categories are numbered from 0 to K – 1" New tests have been added. Timelimit was decreased to 3 seconds. Submissions made after contest have been rejudged. |