CSES-Josephus Problem I & II getting TLE

help
1

Hi, lately I was solving Josephus Problem I and Josephus Problem II but getting TLE.

In my approach, I first take all the values from 1 to n in a vector. Then,print (pos+k)th value from vector and then erase the pos .Here, the erase function creates extra time complexity as vector erase costs O(n) times.

Now,please help me with that. Thank you.

My code-(I) 
signed main()
{
    int n,k;cin>>n;
    vector<int>josep;
    for(int i=1;i<=n;++i)josep.push_back(i);
    int pos=0;
    while((int)josep.size()>1)
    {
    	pos=(pos+1)%(int)josep.size();
    	cout<<josep[pos]<<' ';
    	josep.erase(josep.begin()+pos);
    	pos%=(int)josep.size();
   }
   cout<<josep.at(0)<<' ';
   cout<<endl;
   return 0;
}
My code-(II) 
signed main()
{
    int n,k;cin>>n>>k;
    vector<int>josep;
    for(int i=1;i<=n;++i)josep.push_back(i);
    int pos=0;
    while((int)josep.size()>1)
    {
    	pos=(pos+k)%(int)josep.size();
    	cout<<josep[pos]<<' ';
    	auto it=find(josep.begin(),josep.end(),josep[pos]);
    	josep.erase(it);
    	pos%=(int)josep.size();
	}
	cout<<josep.at(0)<<' ';
    cout<<endl;
	return 0;
}
1 Like
2

(post deleted by author)

1 Like
3

You can use always use ordered sets instead of vectors to simulate the process (as it has an O(logN) erase and insert time), but it’d be interesting to know if there exists a more clever solution to this, instead of just blindly simulating the process.

AC_CODE FOR JOSEPHUS-2 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
signed main(){
  int n,k;
  cin >> n  >> k; 
  int p =k%n ; oset<int>a ;
  for(int i=1;i<=n;i++)
    a.insert(i) ;
  while(a.size()){
    int r = *a.find_by_order(p) ;
    a.erase(r) ;  
    if(a.size())
      p=(p+k)%a.size() ;
    cout << r << " " ;
  }
}

For Josephus-1 just fix k=1

8 Likes
4

thanks

5

This fails for test-cases:
5

Expected: 2 4 1 5 3
Got: 2 4 1 3 5
1 Like
6

See the comment here,

7

Oh, I have made a blunder. I haven’t looked at the sample input and output. I should have noted carefully. It’s my fault. Anyways, I guess the problem 1 can be solved using Circular Linked Lists, I guess.

1 Like
8

Just don’t write your random thoughts… Look now after deletion of even numbers odd numbers will be deleted alternately… Please delete your comment

9

It’s already been mentioned, no point of highlighting it again.

1 Like
10

Cool
Ps: your soln is lovely

1 Like
11

your code is O(n ^ 2) the erase function in O(n) .

12

i have AC code
signed main() {
cin >> n ;
set mark ;
for(int i = 1 ; i <= n ; ++i) mark.insert(i) ;
int pos = 2 ;
while(cnt < n) {
cnt ++ ;
cout << pos << ’ ’ ;
auto it = mark.upper_bound(pos) ;
mark.erase(pos) ;
if(it == mark.end()) {
it = mark.begin() ;
it ++ ;
pos = *it ;
}
else if(*it == *(–mark.end())) {
pos = *mark.begin() ;
}
else {
it ++ ;
pos = *it % n ;
if(!pos) pos = n ;
}
}
cout << *mark.begin() ;
}

13

you can always use queue . add 1 to n elements in a queue. just pop the first element and add it to the queue again. Now the second element, or now the first element in the queue, push it in the vector and pop. continue till you have 1 element left in the queue. Also push the last element, print the vector

4 Likes
14

how this oset(ordered set ) is working(any resource ?) , and any another way to implement this ?

15
16

learn pbds…it will be a o(nlogn) solution

17

Using Linked Lists I did the Josephus Problem I in O(n) space and time. I just did the whole process as said.

#include<bits/stdc++.h>
using namespace std;
#define ll long long

struct Node {
    ll val;
    Node* next;
    Node(ll x): val(x){}
};

void solve(Node* head){
    cout << head->next->val << ' ';
    if(head->next == head){return;}
    head->next = head->next->next;
    solve(head->next);
}

int main(){
    fastio;
    ll n;
    cin >> n;
    Node* head = new Node(1);
    Node* curr = head;
    for(ll i=2; i<=n; i++){
        curr->next = new Node(i);
        curr = curr->next;
    }
    curr->next = head;
    solve(head);
}
18

Don’t misguide anyone else.