Show all threads Hide all threads Show all messages Hide all messages | The difference between VC++ and g++ | ONU_1785 | 1521. War Games 2 | 21 May 2023 15:07 | 2 | Solved the problem using segment tree. Im using VC++ 12 and it's giving the correct answer for the sample. Still while sending (VC++ 2010) im getting WA 1. Changing it to G++ C++ 11 gives AC. What's the difference and why am i getting WA 1 when i choose VC++? Code: #include <iostream> #include <vector> using namespace std; const int MAXN=100000; pair<int, int> t[4*MAXN]; int z=1; void build_tree(int v, int tl, int tr) { if (tl==tr) { t[v]=make_pair(1,z++); return; } int tm=(tl+tr)/2; build_tree(2*v, tl, tm); build_tree(2*v+1, tm+1, tr); t[v].first=t[2*v].first+t[2*v+1].first; t[v].second=-1; } int req(int v, int tl, int tr, int n) { if (tl==tr) { --t[v].first; return t[v].second; } int tm=(tl+tr)/2; t[v].first--; if (t[2*v].first>=n) req(2*v, tl, tm, n); else req(2*v+1, tm+1,tr,n-t[2*v].first); } int main() { int n, k; cin>>n>>k; build_tree(1,1,100000); int cur=k; for (int i=0; i<n; ++i) { int h=req(1,1,100000, cur); cout<<h<<" "; if (i==n-1) break; cur=(cur-1+k)%(n-1-i); if (cur==0) cur+=n-1-i; } } Edited by author 10.03.2013 07:20 Not sure, but it could be because of this t[4*MAXN] instead of t[400000] | condition | 👑TIMOFEY👑 | 1521. War Games 2 | 18 May 2023 11:59 | 2 | He donated all the money to the poor and went to bed with a clear conscience... Yeah, he correctly thought that people will forgive him, because it is charity | Is it correct? | 👾_challenger128_[PermSU] | 1521. War Games 2 | 29 Dec 2021 01:04 | 2 | Test case: 5 5 Ans: 5 1 3 4 2 Test case: 10 2 Ans: 2 4 6 8 1 5 9 7 3 Is it correct ans? Of course 2nd one is wrong, it skips 10. I think, the correct answer for your second test is: 2 4 6 8 10 3 7 1 9 5 | If you have WA #21 | Smilodon_am [Obninsk INPE] | 1521. War Games 2 | 7 Oct 2018 04:20 | 1 | So check below test: 100000 1 Answer is: 1 2 3 4 ... 99998 99999 100000 | You can simulate in with segment tree | Mahilewets | 1521. War Games 2 | 1 Jul 2017 20:50 | 1 | In your segment tree you have count of zeros on every segment of vector of length N. Find k-th non-zero element. Then zero it. Update tree. Output. | in case of WA#2 | nikitaevg | 1521. War Games 2 | 24 Aug 2015 12:30 | 1 | the test is 1 1 the answer is obvious:) | fenwick | Berezhko German | 1521. War Games 2 | 31 Aug 2012 01:17 | 1 | fenwick Berezhko German 31 Aug 2012 01:17 I solved using Fenwick tree and binary search for answer (: | To admins: does test1 coincide with sample test from problem statement? | lenny | 1521. War Games 2 | 17 Jan 2012 01:34 | 2 | On my tests results are the same as results of 'naive' O(n^2) solution and no crashes | anyone, please answer: i really confused with crash test1 | lenny | 1521. War Games 2 | 16 Jan 2012 18:51 | 1 | My solution use order-statistic tree (red-black tree with additional info in nodes). In my computer it passes test from problem description and my tests too (without crashes). Also I have function which solve this problem in a 'naive' way (O(n^2)). I've run this function and my solution on all possible n, k: 1 <= k <= n <= 300 and results was equal (there were no craches too). I know that n, k from test1 are less than 300. So, I don't know where is my bug or it is some kind of other error. code here: http://acm.timus.ru/forum/thread.aspx?id=27746&upd=634623275302370098 | Please answer what test#1 looks like. My program crashes while test#1, but all right when i run it on my computer | lenny | 1521. War Games 2 | 16 Jan 2012 16:18 | 1 | my bulky code: #include <iostream> class RedBlackTreeWithoutRepeatedElements {
private:
static const int BAD_KEY = - 1; static enum TypeOfRotation {LEFT, RIGHT}; static enum NodeColor {RED, BLACK}; struct Node { int key; Node *left, *right, *parent; NodeColor color; int total_number_of_nodes_in_subtree_with_this_node_as_root; Node(int m_key) : key(m_key), left(NULL), right(NULL), parent(NULL), color(RED), total_number_of_nodes_in_subtree_with_this_node_as_root(1) {} }; Node *root_, *nil_delimiter; void inorderedWalkWithNodeDeletion(Node *node) { if ( node != nil_delimiter ) { inorderedWalkWithNodeDeletion(node->left); Node *root_of_right_subtree = node->right; delete node; inorderedWalkWithNodeDeletion(root_of_right_subtree); } }
void rotate(Node *node, TypeOfRotation type_of_rotation) {
if ( node == nil_delimiter ) { return; } Node *substitutor_node = (type_of_rotation == LEFT) ? node->right : node->left; if ( node == nil_delimiter ) { return; } if ( type_of_rotation == LEFT ) { node->right = substitutor_node->left; if ( substitutor_node->left != nil_delimiter ) { substitutor_node->left->parent = node; } substitutor_node->left = node; } else { node->left = substitutor_node->right; if ( substitutor_node->right != nil_delimiter ) { substitutor_node->right->parent = node; } substitutor_node->right = node; } substitutor_node->parent = node->parent; if ( node != root_ ) { if ( node == node->parent->left ) { node->parent->left = substitutor_node; } else { node->parent->right = substitutor_node; } } else { root_ = substitutor_node; } node->parent = substitutor_node; substitutor_node->total_number_of_nodes_in_subtree_with_this_node_as_root = node->total_number_of_nodes_in_subtree_with_this_node_as_root; node->total_number_of_nodes_in_subtree_with_this_node_as_root = node->left->total_number_of_nodes_in_subtree_with_this_node_as_root + node->right->total_number_of_nodes_in_subtree_with_this_node_as_root + 1; } void correctPropertiesOfRedBlackTreeAfterInsertion(Node *node) { while ( node->parent->color == RED ) {
Node *grandparent_node = node->parent->parent; Node *uncle_node = (node->parent == grandparent_node->left) ? grandparent_node->right : grandparent_node->left; if ( uncle_node->color == RED ) { uncle_node->color = node->parent->color = BLACK; grandparent_node->color = RED; node = grandparent_node; } else { if ( node->parent == grandparent_node->left ) { if ( node == node->parent->right ) { rotate(node->parent, LEFT); node = node->left; } } else { if ( node == node->parent->left ) { rotate(node->parent, RIGHT); node = node->right; } } node->parent->color = BLACK; grandparent_node->color = RED; rotate(grandparent_node, (node->parent == grandparent_node->left) ? RIGHT : LEFT ); } } root_->color = BLACK; } void correctPropertiesOfRedBlackTreeAfterDelettion(Node *node) { while ( node != root_ && node->color == BLACK ) { if ( node == node->parent->left ) { Node *sibling_node = node->parent->right; if ( sibling_node->color == RED ) { sibling_node->color = BLACK; node->parent->color = RED; rotate(node->parent, LEFT); sibling_node = node->parent->right; } if ( sibling_node->left->color == BLACK && sibling_node->right->color == BLACK ) { sibling_node->color = RED; node = node->parent; } else { if ( sibling_node->right->color == BLACK ) { sibling_node->left->color = BLACK; sibling_node->color = RED; rotate(sibling_node, RIGHT); sibling_node = node->parent->right; } sibling_node->color = node->parent->color; node->parent->color = BLACK; sibling_node->right->color = BLACK; rotate(node->parent, LEFT); node = root_; } } else {
Node *sibling_node = node->parent->left; if ( sibling_node->color == RED ) { sibling_node->color = BLACK; node->parent->color = RED; rotate(node->parent, RIGHT); sibling_node = node->parent->left; } if ( sibling_node->left->color == BLACK && sibling_node->right->color == BLACK ) { sibling_node->color = RED; node = node->parent; } else {
if ( sibling_node->left->color == BLACK ) { sibling_node->right->color = BLACK; sibling_node->color = RED; rotate(sibling_node, LEFT); sibling_node = node->parent->left; } sibling_node->color = node->parent->color; node->parent->color = BLACK; sibling_node->left->color = BLACK; rotate(node->parent, RIGHT); node = root_; } } } node->color = BLACK; } void removeNode(Node *node) { Node *node_to_be_actually_deleted; if ( node->left == nil_delimiter || node->right == nil_delimiter ) { node_to_be_actually_deleted = node; } else { node_to_be_actually_deleted = node->right; while ( node_to_be_actually_deleted->left != nil_delimiter ) { node_to_be_actually_deleted = node_to_be_actually_deleted->left; } } --node_to_be_actually_deleted->total_number_of_nodes_in_subtree_with_this_node_as_root; Node *current_node = node_to_be_actually_deleted->parent; while ( current_node != nil_delimiter ) { --current_node->total_number_of_nodes_in_subtree_with_this_node_as_root; current_node = current_node->parent; } Node *only_child_of_node_to_be_actually_deleted = (node_to_be_actually_deleted->left != nil_delimiter) ? node_to_be_actually_deleted->left : node_to_be_actually_deleted->right; only_child_of_node_to_be_actually_deleted->parent = node_to_be_actually_deleted->parent; if ( node_to_be_actually_deleted->parent != nil_delimiter ) { if ( node_to_be_actually_deleted == node_to_be_actually_deleted->parent->left ) { node_to_be_actually_deleted->parent->left = only_child_of_node_to_be_actually_deleted; } else { node_to_be_actually_deleted->parent->right = only_child_of_node_to_be_actually_deleted; } } else { root_ = only_child_of_node_to_be_actually_deleted; } if ( node != node_to_be_actually_deleted ) { node->key = node_to_be_actually_deleted->key; } if ( node_to_be_actually_deleted->color == BLACK ) { correctPropertiesOfRedBlackTreeAfterDelettion(only_child_of_node_to_be_actually_deleted); } delete node_to_be_actually_deleted; }
Node* find_k_th_element(int k, Node *root_of_subtree) {
int r = root_of_subtree->left->total_number_of_nodes_in_subtree_with_this_node_as_root + 1; if ( r == k ) { return root_of_subtree; } else if ( r > k ) { find_k_th_element(k, root_of_subtree->left); } else { find_k_th_element(k - r, root_of_subtree->right); } } public:
RedBlackTreeWithoutRepeatedElements() { nil_delimiter = new Node(BAD_KEY); nil_delimiter->color = BLACK; nil_delimiter->left = nil_delimiter->right = nil_delimiter; nil_delimiter->total_number_of_nodes_in_subtree_with_this_node_as_root = 0; root_ = nil_delimiter; } void insert(int new_key) { if ( root_ == nil_delimiter ) { root_ = new Node(new_key); root_->color = BLACK; root_->left = root_->right = root_->parent = nil_delimiter; return; }
Node *current_node = root_, *parent_node = nil_delimiter, *new_node = new Node(new_key); new_node->left = new_node->right = nil_delimiter; while ( current_node != nil_delimiter ) { ++current_node->total_number_of_nodes_in_subtree_with_this_node_as_root; parent_node = current_node; current_node = (current_node->key > new_key) ? current_node->left : current_node->right; } if ( parent_node->key > new_key ) { parent_node->left = new_node; } else { parent_node->right = new_node; } new_node->parent = parent_node;
correctPropertiesOfRedBlackTreeAfterInsertion(new_node); }
int getKeyOfKthElementAndRemoveIt(int k) { Node *k_th_element = find_k_th_element(k, root_); int key_of_k_th_element = k_th_element->key; removeNode(k_th_element); return key_of_k_th_element; } int getSize() const { return (root_ != nil_delimiter) ? root_->total_number_of_nodes_in_subtree_with_this_node_as_root : 0; } ~RedBlackTreeWithoutRepeatedElements() { inorderedWalkWithNodeDeletion(root_); delete nil_delimiter; } }; int main() { int number_of_soldiers, number_of_words_in_counting_out_rhyme; std::cin >> number_of_soldiers >> number_of_words_in_counting_out_rhyme; RedBlackTreeWithoutRepeatedElements soldiers; for ( int soldier_id = 1; soldier_id <= number_of_soldiers; ++soldier_id ) { soldiers.insert(soldier_id); } int start_position_for_counting = 1, position_of_excluded_solider; while ( soldiers.getSize() > 1 ) { position_of_excluded_solider = start_position_for_counting + number_of_words_in_counting_out_rhyme - 1; if ( position_of_excluded_solider > soldiers.getSize() ) { position_of_excluded_solider = (number_of_words_in_counting_out_rhyme - (soldiers.getSize() - start_position_for_counting + 1)) % soldiers.getSize(); if ( position_of_excluded_solider == 0 ) { position_of_excluded_solider = soldiers.getSize(); } } std::cout << soldiers.getKeyOfKthElementAndRemoveIt(position_of_excluded_solider) << " "; start_position_for_counting = (position_of_excluded_solider <= soldiers.getSize()) ? position_of_excluded_solider : 1; } std::cout << soldiers.getKeyOfKthElementAndRemoveIt(1); #if !defined(ONLINE_JUDGE) std::cin.ignore(std::cin.rdbuf()->in_avail()); std::cin.get(); #endif return 0; } Edited by author 16.01.2012 16:24 Edited by author 16.01.2012 16:39 | O(n ^ 3/2) in 0.062 s. :) | Walrus | 1521. War Games 2 | 1 Nov 2010 23:24 | 19 | O(N log N) is possible. Of course, but not in 0.062 s. :) In this problem the most time-consuming thing is output. So your 0.062 it is only fast output. PS: Btw, O(nlogn) - 0.046 sec ;) PS: Btw, O(nlogn) - 0.046 sec ;) Hmm... 0.046 also is not 0.062 :) But it is fact: my solution is so simple. More simple than Interval Tree? =) Anyway you've intersted me. So if you don't mind, please, send your solution to sk1@hotbox.ru I plan to create a site collecting articles, ebooks, problems, and so on about algorithms. I've also uploaded my (too small) solutions to Timus problems, containing 1521. If you have any resources and want to share, please take a minute. It benefits our problem-solving community! Here is the URL: Merry Christmas to all ! Regards, Minh Duc Edited by moderator 29.12.2006 09:26 How to speed it up? My O(N*logN*logN) solution takes ~0.7 sec. to get AC... Vedernikoff Sergey: I don't know what your algo is but mine has O(NlogN) like most of the others. I used Index tree (also known as Dynamic Order Statistics or as Burunduk said - Interval tree - this must be the same). I am interested in the O(N^3/2) solution. Could someone explain it here? Edited by author 15.01.2007 07:20 Let's exchange with our progs. My is O(N^3/2). Just 316Kb memory is needed for it. Send it on my e-mail or post your Kiril, my e-mail is cheater_no1@abv.bg my email: onlyforme_@ok.kz My mail is hulakov@gmail.com Vedernikoff Sergey: I don't know what your algo is but mine has O(NlogN) like most of the others. Edited by author 15.01.2007 07:20 My solution has O(N*logN*LogN). Main idea - find k-th order statistics in array, where a[i]=1, if i-th soldier was in circle else a[i]=0 (use binary search and Fenwick tree). I don't know how to find k-th order statistics only by Fenwick by O(LgN) Edited by author 21.07.2010 18:09can anybody explain me n ^ 3/2 algo? I have solved it using Binary Search Tree | WA 10. Can you give me some tests?(+) | Programmer | 1521. War Games 2 | 27 Oct 2010 19:31 | 2 | Sorry , have found bug. Edited by author 24.04.2009 03:03 Anybody, wright test 10, please... | what is the output for n=6 k=2,n=5 k=4 | Madhav | 1521. War Games 2 | 23 Aug 2010 21:14 | 3 | pls help.Can any one give the output for the above test cases and explain why is it like that? pls help.Can any one give the output for the above test cases and explain why is it like that? n = 5 k =4 1 2 3 4 5 1 round : 1 2 3 5 4 2 round : 1 2 5 4 3 3 round : 1 5 4 3 2 4 round : 5 4 3 2 1 6 round : 5 4 3 1 2 answer 5 4 3 1 2 n = 6 k = 2 1 2 3 4 5 6 1 round : 1 3 4 5 6 2 2 round : 1 3 5 6 2 4 3 round : 1 3 5 2 4 6 4 round : 1 3 5 2 6 4 5 round : 3 5 2 6 4 1 6 round : 3 2 6 4 1 5 answer 3 2 6 4 1 5 n = 5 k =4 1 2 3 4 5 1 round : 1 2 3 5 4 2 round : 1 2 5 4 3 3 round : 1 5 4 3 2 4 round : 5 4 3 2 1 6 round : 5 4 3 1 2 answer 5 4 3 1 2 n = 6 k = 2 1 2 3 4 5 6 1 round : 1 3 4 5 6 2 2 round : 1 3 5 6 2 4 3 round : 1 3 5 2 4 6 4 round : 1 3 5 2 6 4 5 round : 3 5 2 6 4 1 6 round : 3 2 6 4 1 5 answer 3 2 6 4 1 5 What's that sh!t? n = 5, k = 4 4 3 5 2 1 n = 6, k = 2 2 4 6 3 1 5 | Compilation Error | Shelest Pavlo | 1521. War Games 2 | 8 Apr 2009 15:20 | 1 | I receive compilation error but in Borland C++ all ok. What is problem? #include<iostream.h> #include<stdlib.h> #include<string.h> void main() { unsigned long N, K, i, position; char * mas[30000]; char * mas1[30000]; char * mas2[30000]; char * mas3[10000]; cin>>N; cin>>K; for( i = 1 ; i <= N; i++) { if(i < 30000) { ultoa(i, mas[i - 1], 10/* size(i)*/); } else if (i < 60000) { ultoa(i, mas1[i - 30001] , 10/* size(i)*/); } else if (i < 90000) { ultoa(i, mas2[i - 60001] , 10/*size(i)*/); } else if (i < 100000) { ultoa(i, mas3[i - 90001] , 10/*size(i)*/); } } i = 0; position = 0; int step = 0; while( i < N) { while(step < K) { if(position >= N) position = position - N; if(position < 30000) { if(strcmp(mas[position], "0") != 0) step ++; } else if(position < 60000) { if(strcmp(mas[position - 30000], "0") != 0) step ++; } else if(position < 90000) { if(strcmp(mas[position - 60000], "0") != 0) step ++; } else if(position < 100000) { if(strcmp(mas[position - 90000], "0") != 0) step ++; } position++; } step = 0; position --; if(position < 30000) { cout<<mas[position]; mas[position] = "0"; } else if(position < 60000) { cout<<mas1[position]; mas1[position] = "0"; } else if(position < 90000) { cout<<mas2[position]; mas2[position] = "0"; } else if(position < 100000) { cout<<mas3[position]; mas3[position] = "0"; } cout<<" "; i++; position ++; } } | Optimization | Valentin Pimenov | 1521. War Games 2 | 22 Aug 2008 11:14 | 5 | Should the interval tree be balanced? I use simple interval tree and get TL22. My program on Pascal with simple interval tree gets AC. I don't understand, what problem with C++ may you have??? I think the problem is in that fact that my 'simple interval tree' is not balanced. So in worst case (N=100000,K=2) I got too long tree. Oh, if you solve it with real tree - of course, it should be balanced! My solution works with interval tree - RSQ, so it is quite fast... I get TLE 15 with circular linked list; His trees aren't definitely good; | I use interval tree (n * log n) and only 0.281c. How to improve? | Ont | 1521. War Games 2 | 18 Sep 2007 19:55 | 8 | How alogorithms with n^3/2 may be faster? Probably with lower constants in the compexity calculation. ..but I doubt there are many O(n^3/2) solutions better then the O(nlogn) can anybody give me link about Interval Tree? I think that to solve we should have dynamic container with operations delete- O(lgn) take_k_th - O(lgn) try write the program (5 rows) in these terms. After this find anywhere such data type for example on base of red-black trees. If you will read interval trees it will take long time because all typical tasks in this theory far away of 1521/ Edited by author 26.02.2007 23:14 Now I has made realization of this plan according with Cormen's augmented red-black tree sytucture for which an additional field : size belongs to each vertex of balanced tree. But have only 0.821 AC. Interval tree automatically balanced but how make it augmented with such field ? In all cases I very glad because this balanced structure rather helpful. For example interesting problem 1424 needs another augmented red-black tree (also as in Cormen) when in grredy algotithm we check next interval may or may not to include it in optimal set of intervals formed to this moment. Edited by author 16.09.2007 18:54 Edited by author 16.09.2007 18:55 Binary Search Tree is faster then red - black trees in this case. I solved it using BST in 0.281 sec. At first I constructed balanced BST with n numbers and then there is a simple algorithm to delete and find n - th element in the tree Edited by author 18.09.2007 18:49 Yes. Order 1,2,3,...N predescribed and we can use random tree. But this situation rather seldom and very often we have dynamic data base. | C++ | Valentin Pimenov | 1521. War Games 2 | 30 Aug 2007 19:21 | 1 | C++ Valentin Pimenov 30 Aug 2007 19:21 Can I use C++ feature "overloading of operator new" to increase the speed of memory allocation? | Can i use malloc.h? | VALERO | 1521. War Games 2 | 4 Feb 2007 22:11 | 1 | | How to output fast? | Victor Barinov (TNU) | 1521. War Games 2 | 11 Jan 2007 00:23 | 3 | Especially to Burunduk1 :-) How your output method is organized? I tried different ideas. My best time is 0.078. My algo is O( n log n ). Maybe anyone have any ideas? Thanks. Bye. Mine one is also O(nlogn) But its constant is very small. About output: /* printf("%d\n", mi); */ char s[9]; int l = 0; while (mi) s[l++] = mi % 10, mi /= 10; while (l--) putc('0' + s[l], stdout); putc('\n', stdout); Thanks. I improved my algo, now 0.062 Does your structure use binary operations intensively? | No subject | Reset | 1521. War Games 2 | 30 Dec 2006 11:16 | 1 | |
|
|