|
|
my same logic got tle in c++ but AC in java so beware LOL. That's interesting. Could you share code please? That's because in Java objects like String pass by their links, when in C++ strings pass by their values(all chars). So when you move a string in Java you do less operations than you do in C++ Edited by author 24.04.2022 12:50 Try this 4 a b c a p d b e w b t y ans:2 IF you have TL, try this test: 18 aasda0sd basdasdasd casdasd asdasd33a 0b12asdasd ca45sdasd cdasdas3das dasd0asda2ds e1dasqew sdsdad4asdsaf dasda0sdasd 0gasdasd asdasda5sa asdasdasd3b asda0sdasdc aqwewq6e bqweqwe cqweq0we cqweqw7e dqweqwe eqw3ewqees fsadasd8asd dasdasdas0d gasdasd asdasds9adasa abasdas3dads casdasd12 qweqwew123qea bqweqw3ewqe cweqqwee csadas12d dasdas0d ed0dsdadsa fdasdasd33 dasdasds30ad gasasdsad adasdasd123d badas3ddasda cdasds0adas asdads455as basdasda2sd casdasdd0sa cqwewq123e deeqw12e eqw1easda8d fasd123asd dasdasds3a1dqw gqwe9wqewes jeqweqw123e eqweq123wewee hwewe9wqq ldszczx123c ad123sdasdaq qweweq09f ans: 18 Edited by author 10.08.2019 22:28 Edited by author 10.08.2019 22:28 Edited by author 10.08.2019 22:28 very similar to the NP-complete problem 3-dimensional matching (3-сочетания) Yes, this problem is NP-hard. i have a not brute force solution. The conditions of the problem impose restrictions on the graph But your algorithm is wrong :) We added more tests and now you have WA. Thank you! any hints plzzzz Lamest O(2^K) is enough here. Act greedy. At each iteration select such team X, that if X in contest, then the number of teams can't attend contest is minimal. Remove such teams that have common members with X from the list. Hello! If you have WA 5, pay attention to the fact, that some programmer could take part in contests in more than 3 comands, even in all. Anybody else? 5 1 2 a 4 b c 3 a b 5 c d 6 7 d answer 3 Here's the big test case: 18 a b c d e f g h i j k l m n o p q r s t u v w x y z 1 2 3 4 5 6 7 8 9 0 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 If you are using bitmask be careful with: *Use long long to store the bitmask. There can be 58 contestant (18*3) as showed above *Be careful with casting in C/C++. I was using the following: #define ll long long void SB(ll &m, ll x) { m = ((m) | (1 <<(x))); } But the (1 << (x)) part auto-cast to int. Hence the overflow The correct should be: #define ll long long void SB(ll &m, ll x) { m = ((m) | (1LL <<(x))); } Hope it help! Edited by author 30.05.2016 06:02 Hah I decided to check all variants, but due to misprint my program become greedy) try this: 13 a b c b c d a e q e r t q f e dd qw ff aa f dd e q f dd ee mm vv bb cc pp ii uu pp a d d e q ans: 5 my answer is 5 but still i am getting wrong answer on test case 9. New anti-greedy tests were added. 93 authors lost AC. If you still have AC with greedy solution, please, tell us about it here or to timus_support(at)acm.timus.ru. Hi! After 3 algorithms, I finally nailed it!. Don't try coloring, doesn't work. What I did: First, convert the teams onto nodes, and create ONE bidirectional edge between two teams when these team are sharing one or two contestants. Then, I make a pair array, and save, in decreasing order, the grades of the nodes ant their "names" (I used numbers). When I have that ordered array, I delete the nodes when have more than zero adjacent nodes. If have zero adjacent, means that the team is non-sharing any contestant. When you deleted a node, don't need to reorder the grades array. Finally, return the total initial nodes minus the times that I had deleted teams. Hope it helps you. Bye! I was getting TLE because it's bigget input is too small :) It had a very nice tip: nC2 > 3*nlogn (n>25) & nC2 <= 3*nlogn (n<25) The maximum n was 18 so 18C2=153 > 3*18log18=216 and in a normal mode we often prefer nlogn solutions to n^2 solutions. But in this problem max n was 18 and I tried many times to optimize my brute force solution (I was getting TLE for few extra ms) to get AC and I couldn't see the tip because n was so small :) My 2^n*nC2 solution got AC but my 2^n*3*nlogn solution got TLE. Edited by author 29.01.2015 13:48 My greedy algorithm have 'accepted', but gives wrong answer for this test: 8 a b c d e f g i k b l m l m i i k c d e c e f k Notice that there are 18*3=54 participants, 64bit-type should be used for masks. It's possible to solve that problem with only 32-bit masks. Encode team number k as 2^k (in c "1 << k", in pascal "1 shl k"). Create an array (I named it "check"): forall (i) { check[i] = 0; forall (j, not equal i) { if (there is a member in team j that exists also in team i) then check[i] = check[i] bitwise or (2 ^ j); } } You can encode every possible teams combination in one number from interval [0 .. (2^k) - 1]. Note that the number is less than 2 ^ 18 (or 262144). Then enumerate all numbers from that interval and for every number S for every bit p in position q in number S check inequality "S & check[q] > 0". If for some p in position q in number S this inequality is true, than state S is inacceptable. Edited by author 23.09.2011 01:18 My first approach was as simple as possible: Console.Readline().Split(' '); but got WA test#1 then parsed input with regex [a-z]+ to find names and got AC There were no EOLN characters in the end of some tests. Now your first approach is AC too. Don't spend your time searching a fast algorithm. Simple recursive solution which searchs all possible answers gets AC 0.015!! Yeah, but I have TLE#7! Firstly I made a table that shows which team can't participate with which one and then used recursion to compute answers. Note that order of teams does not matter. Choosing teams numbered 2,3 is same as choosing 3, 2 so try to choose teams in increasing odrer. I hope that it will help you I'd simply bruteforced it and used DP approach. AC in 0.156 sec on worst test. There are only 18 teams, so we can iterate over all possible 2^18 combinations and store "useful information" from previous iterations in large array. All done with bitmasks |
|
|