codeprokeshav's blog

By codeprokeshav, history, 4 months ago,

Link : https://cses.fi/problemset/task/1670 is it a wise idea to think of recursion by making a function with 9 parameters there will be only two types: at the correct position, not correct position. Sometimes we will lock the numbers which will be at correct positions sometimes we will not and move it from correct to incorrect. so how to compute this problem

cses #game

• -6

 » 4 months ago, # |   0 Auto comment: topic has been updated by codeprokeshav (previous revision, new revision, compare).
 » 4 months ago, # |   0 There could be $9!$ such permutations. So you don't need to make a function with $9$ parameters, just storing the index of the permutations would be enough. And then just perform a straightforward dynamic programming.Oh, you can also solve it using BFS.
•  » » 4 months ago, # ^ |   0 Sir I don't think 9! or dp approach will work because you can have base condition but what algorithm you will have below base condition. Sir can you please elaborate BFS approach Sir what I am feeling is that there is a small trick which can lead to a very simple and intuitive solution of this problem
•  » » » 4 months ago, # ^ |   0 Yeah, you are right. Dp won't work.So just use BFS as spookywooky said. But you don't need to use string, instead, you can use the index of the permutations which will be faster as in that case you won't need to use map, but a simple array would suffice.
•  » » » » 4 months ago, # ^ |   0 right right we can just use max variable no need to use map it will decrease time complexity but how usage of index will reduce time
 » 4 months ago, # |   0 I did a brute force by bfs. The state of the board can be stored as a string, ie start with "123456789". Then there are 12 different swaps possible. So just store every possible state in a map with the number of swaps needed to reach that state. My code needs 0.9 sec to calculate all possible states, which gives AC.
•  » » 4 months ago, # ^ |   0 looks good doing it but Sir what I am feeling is that there is a small trick which can lead to a very simple and intuitive solution of this problem
•  » » 2 months ago, # ^ |   0 Your approach is fabulous. Can you share your implementation?
•  » » » 2 months ago, # ^ |   0 Note that this is not very efficient. However, it looks like this: Code/** * Dont raise your voice, improve your argument. * --Desmond Tutu */ #include using namespace std; const bool ready = []() { ios_base::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(12); return true; }(); const double PI = acos(-1); using ll= long long; #define int ll #define all(v) (v).begin(), (v).end() #define fori(n) for(int i=0; i>i; #define cins(s) string s; cin>>s; #define cind(d) double d; cin>>d; #define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; } #define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; } #define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; } using pii= pair; using pdd= pair; using vd= vector; using vb= vector; using vi= vector; using vvi= vector; using vs= vector; const int B=3; const int MASK=0x7; /* int doSwap(int va, int i1, int i2) { int v1=(va&(MASK<<(i1*B)))>>(i1*B); int v2=(va&(MASK<<(i2*B)))>>(i2*B); va= (va & ~(MASK<<(i1*B))) | (MASK<<(i2*B)); va= (va & ~(MASK<<(i2*B))) | (MASK<<(i1*B)); } int toInt(const string& s) { int ans=0; for(int i=0; i<8; i++) { ans<<=B; ans+=(s[i]-'2'); } return ans; } string toString(int va) { string ans(8,' '); for(int i=0; i<8; i++) { ans[i]='2'+(va&MASK); va>>=B; } } */ /* the possible swaps */ constexpr pii sw[]= { { 0,3 }, { 1,4 }, { 2,5 }, { 3,6 }, { 4,7 }, { 5,8 }, { 0,1 }, { 1,2 }, { 3,4 }, { 4,5 }, { 6,7 }, { 7,8 } }; const unordered_map calcDp() { unordered_map ldp; string a="123456789"; ldp[a]=1; queue q; q.push(a); while(q.size()) { string cur=q.front(); q.pop(); int dpcur=ldp[cur]; string next=cur; for(pii p : sw) { char tmp=next[p.first]; next[p.first]=next[p.second]; next[p.second]=tmp; int dpnext=ldp[next]; if(dpnext==0) { ldp[next]=dpcur+1; q.push(next); } next[p.second]=next[p.first]; next[p.first]=tmp; } } return ldp; } const unordered_map dp=calcDp(); /* swap _adjacent_ fields * There are 12 different moves * possible. * Note that there are only 9! different * states. * Ie it is simple BFS. * **************** * Unfortunatly it turns out that this is to slow, ~3000ms * We would need to find a way to map the 9! permutations to the first 9! integers, * then we could use BFS in a quicker way. * * ***************** * Other strategy: * move the 1 in place fastest possible, then permute only the other positions. * ... * And it turns out then we have to put 8 different numbers into 8 positions. * Since we can place 8 different numbers into 3 bits this is only 24 bits, * ie fits in array of size 16M. * So we do not need a map for dp, we can use vector instead. * ... turns out there are some wrong ones :/ * 4 2 7 * 6 8 3 * 1 5 9 * We cannot swap the 1 and 6 in first place. It is better to first * move the 7 to the place of the 6... * ***************** * Ok. Lets calculate the distance to all permutations per compiletime. * Then output solution in O(1) * ...turns out this is difficult :/ **/ void solve() { string a(9,' '); for(int i=0; i<9; i++) cin>>a[i]; if(dp.find(a)!=dp.end()) { int ans=dp.find(a)->second-1; cout<
•  » » » » 2 months ago, # ^ |   0 Thanks for this but I already wrote my own. However, I'm getting TLEHow should I optimize?
•  » » » » » 2 months ago, # ^ |   0 Easiest optimization is to BFS from both ends.
•  » » » » » » 2 months ago, # ^ |   0 Can you elaborate more?
•  » » » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 Essentially the answer isn't very large (I believe up to 16 for largest cases), so instead of doing a full BFS up to distance 16, only do a BFS up to distance 8 from both the starting grid and the final grid, and iterate over the "meetup grid".If we imagine BFS as a tree, the number of edges between depths increases roughly exponentially, so BFS'ing to only half of the depth is going to significantly reduce the amount of edges we check.Here's my submission that got 0.57 s on CSES. It's pretty basic with minimal optimization, so you can probably get it even faster.https://cses.fi/paste/5b823493d891d75d12d603/EDIT: Apparently there's a name for this: https://en.wikipedia.org/wiki/Bidirectional_search
•  » » » » » » » » 2 months ago, # ^ |   0 If for an arrangement that is (let's say 9 units from the start) and 7 units away from the goal. Ig the approach you mentioned wouldn't consider this case?
•  » » » » » » » » » 2 months ago, # ^ |   0 Yes, but that's ok, because there exists an arrangement that's distance 8 from the start and goal, so we'll use that instead.
•  » » » » » » » » » 2 months ago, # ^ |   0 So is there any certainty that this arrangement will definitely exist
•  » » » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 By DefinitionEDIT: Image doesn't want to load so direct link: https://www.imageupload.net/image/bIGfa
•  » » » » » 2 months ago, # ^ |   0 I made one which uses an array instead of hashmap for the dp values, which speed things up.https://cses.fi/paste/e40a153a2154cdee13d897/