|
|
Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Tests | Islom(TUIT Urgench) | 1425. Ферзь 2 | 11 ноя 2016 18:24 | 1 | Tests Islom(TUIT Urgench) 11 ноя 2016 18:24 Test#1 3 3 1 2 3 ans:27 Test#2 2 6 1 3 ans:36 Test#3 3 6 3 4 5 ans: 180 Test#4 1 5 3 ans:5 Test#5 1 2 1 ans:1 Test#6 3 2 1 2 2 ans:4 | Only 0.031s | pperm | 1425. Ферзь 2 | 25 мар 2015 13:11 | 3 | Maybe new problem with increase S,K) 5 500 250 250 250 250 250 ------------------- 22288580 I'm curious how do you solve this problem so fast, could you give me some hint?? or send you code to my email:qizichao@gmail.com THX I managed to reach the same time, but only once :) | STL::set work fast :D | Alex Vistyazh [Ivye School] | 1425. Ферзь 2 | 10 сен 2013 17:35 | 1 | I use set when solve this task :D And i have AC with 2.453s But hashes work faster 0.625s (sorry for my bad english) Edited by author 10.09.2013 21:09 | if n=1 | Alexander Kouprin | 1425. Ферзь 2 | 15 авг 2008 18:47 | 6 | if n=1 Alexander Kouprin 8 апр 2007 16:09 What I must write if n=1? Please, give me answers for tests: 1 1 1 (yes, it's uncorrect ;) 1 2 1 1 3 1 1 4 4 Edited by author 08.04.2007 16:10 Hi evil cheater!:) my prog out 1 3 4 Hi, friend! =) My prog out 1 3 4 too, but I get WA#6. I using hash. You have any good (or evil :) tests for me? And what answers for this: 5 2 1 1 1 1 1 -> 22 4 12 1 5 3 5 11 -> 1781 5 45 18 33 1 1 45 -> 41312 n=2 -> s*s Edited by author 08.04.2007 20:31 :) Alexander Kouprin 8 апр 2007 22:30 I solved it! It's not hard as you think. Using hash, you must deleting 1-step queen places only. My time is 1.687 Thanks! Re: :) Denis Koshman 15 авг 2008 18:47 There're about 3e+6 positions before reduction to 1e+6. So, it's too compacted for hasing. You'll either get TLE or ML, or you're lucky :) My solution eats 2.4 sec, but it spends most of its time inside qsort. And I couldn't do any bucketing due to ML :( | std::prev_permutation | Lomir | 1425. Ферзь 2 | 30 июн 2007 01:55 | 1 | http://www.cplusplus.com/reference/algorithm/prev_permutation.html"If the function can determine the previous smaller permutation, it rearranges the elements as such and returns true. If that was not possible (because it is already at the smallest), it rearranges the elements according to the last permutation (sorted in descending order) and returns false." On Timus std::prev_permutation function doesn't return false ever. This code gets TLE: std::vector<int> v(5); for (int i = 0; i < 2; ++i) v[i] = 1; while (std::prev_permutation(v.begin(), v.end())); | Stl vectors vorks! | svr | 1425. Ферзь 2 | 13 мар 2007 14:22 | 12 | Structure vector<int>Pos[100][100] gave Ac. With O(lgN) find(S) and O(N) insert(S) where S- new position set<int>Pos[100][100] led to MLE Thus only all position generating without any combinatorical counting. Who can advice more effective structure for store position, please, do it. Does your algo gives right answers on all possible tests? I see you use only ~5Mb Do you store all positions? More efficient structure is simple liniear array:) I Qsort it and found different elements P.S. I understand your algo it's not fast but it works Edited by author 11.03.2007 14:05 My algo absolute correct and simple It simply build all possible two-moving new positions and store them in vector<int>Poses[100][100] where If S[0..4]- new position then value 10001*S[2]+101*S[3]+S[4] stored in Poses[S[0]][S[1]]. You opinion that array[] better than vector<int> does't understand me fully because we must have dynamic structure and maxsize 10000 unacceptible. Edited by author 11.03.2007 18:32 Edited by author 11.03.2007 18:33 Edited by author 11.03.2007 18:34 Yes. It is possible to use common array. But using char Poses[3300000][5] will give MLE. Therefore because 100<128=2^7 it is enaught 35 bit for one position. Or ~12Mbait for all matrix. After apply qsort and count differet copies moving along sorted array. Thank for effective advice. Follow it i will try to be in first 10 on 1425. 35 bit is bad for adressing max num of positions is <2900000 (test: 5 100 50 50 50 50 50) so you can store all But when I tried qsort array[3000000] of string[5] I got TLE You can store position as integer+byte=5 byte And it can be sorted fast enough But I got MLE in this case (array[3000000]*5) ... strange Any case it's not easy do it less then 1 sec 3000000 values for qsort it's not small:)
Edited by author 11.03.2007 21:46 I will use variant of my idea. int *Poses[100][100] array of pointers to dynamic memory. Use int Buffer[100] for periodic increasing taken memory. After it apply qsort and count in each Poses[i][j]. Shue that time will diminish without MLE Edited by author 11.03.2007 22:15 Edited by author 11.03.2007 22:28 Many dimensional arrays and dynamic memory will work slow IMHO Why you stil don't solve 1220 :) It's more interesting in coding If you need help with 1220 mail me, but I think you can solve it yourself easily Because 1220 as i undestood needs stable sorting on place. I couldn't find in literature algos for stable sorting without additional memory. Continuing! Thank for Reminder very much! I was thinking about 1220(Stacs) 1 year ago and failed. Now, after training in timus I can solve it. I tried to manage stable sort on PUSH A B rows and couldn't pack A and B in Int type. But it possible to work with POP A rows and in for each such row in int type variable there is place for A and number of POP or for stable information. After it each PUSH A B row can O(lg N) find corresponding POP in POPs part of global array. push and pop in O(1) but I think it better discuss in other thread or mail:) KIRILL!! I got AC(1220) making stable sorting using bubble sort in 10 segments of Push data with size of <=10000 yes:) but easy ways not for us:) It can be solved with self organazed lists and own 3 byte type byte mas[700001] (blocks by 7 byte) and int last[1001] for pointers on last value in mas Edited by author 13.03.2007 14:23 Edited by author 13.03.2007 14:24 | Anybody can help? i got wa#10 | Dan.hu | 1425. Ферзь 2 | 28 фев 2007 13:43 | 5 | Try this tests 5 100 1 1 1 1 1 ------- 196120 5 100 50 50 50 50 50 ------- 858180 4 100 1 1 1 1 1 -------- 112912 How many new positions maximal number may be? It seems that it is not very much. Therefore we may don't use clear combinatorical approach but just build each new position acording roules of king moving , put it in set and set itself esclude multuples. This is not mathematic but just context's way. If new positions number too much and we have TLE we may count mathematically simple subset as two roork's moving and for rest use set's approach. But going this way I have TLE14 Edited by author 28.02.2007 10:01 Max answer is 858180 I think 5 100 50 50 50 50 50 Probably it's 16 test Potentially queen can reach ~3000000 cells, but many of them coincide. I just choose different from this I hash 5 byte to 4 | I've solved it with hash, but it's not good way | KIRILL(ArcSTU) | 1425. Ферзь 2 | 28 фев 2007 03:24 | 1 | Does anybody solve it without hash? I can get just 1 right hash from several hundreds | I have WA#5. What is special in this test? | EfremovAleksei | 1425. Ферзь 2 | 19 сен 2006 14:30 | 2 | Try this test: 1 2 1 Obviously correct answer is: 1 |
|
|
|