|
|
Show all threads Hide all threads Show all messages Hide all messages | Any hints? | Programmer | 1790. Searching for the Truth | 20 Dec 2016 21:36 | 2 | Any hints for this problem? Try solve 2 sub problems when dodecahedron on odd position and not. | No subject | Sirko | 1790. Searching for the Truth | 19 Jan 2016 04:10 | 1 | Thinking of kittens and doors rather than Dodecahedrons helped me to find O(N) solution :) | WA8 | Hi4ko | 1790. Searching for the Truth | 26 Sep 2011 01:36 | 1 | WA8 Hi4ko 26 Sep 2011 01:36 #include <iostream> #include <cstdlib> #include <vector> using namespace std; int main() { int n,m,al; int aga=1,t=0; vector<int> algo; cin>>n>>m; int lol; for(int i=0;i<m;i++) { cin>>al; algo.push_back(al); } for(int j=n;j>=1;j--) { lol=rand()%n+1; for(vector<int>::iterator it=algo.begin();it!=algo.end();it++) { if(*it==lol) { aga=0; break; } else { int dir=rand()%2; if(dir==0) { if(lol!=0) --lol; else ++lol; } else { if(lol!=n) ++lol; else --lol; } } } if(aga==1) { cout<<"NO"<<endl; t=1; break; } aga=1; } if(t==0) cout<<"YES"<<endl; } what's the mistake? | Easy solution | Alexander Georgiev | 1790. Searching for the Truth | 27 Oct 2010 17:07 | 15 | Interestingly enough the problem can be solved with simple simulation. Just simulate the process, choosing random directions and random initial positions while you are within the time limit and you will get accepted. I really doubt this is the correct solution, so I was wondering what is the real one? There is very simple O(m) solution - just use your algorithm for solution of previous problem. I've got WA#9. My algo is: first I generate the possible answers in both directions (strating from 1 and n) with algorithm from the previous problem, and with KMP I'm searching the input array for match, also I added special cases for 2 (1 1 and 2 2) and for 3 (2 2). Edited by author 20.10.2010 04:44 To KALO: Try this test 5 10 1 2 3 4 5 1 2 3 4 5 To KALO: Try this test 5 10 1 2 3 4 5 1 2 3 4 5 If N is odd = then sequence are 1..N 1..N 2..N-1 N-1 else the sequence is 2..N-1 N-1.. 2 I'm right? Edited by author 20.10.2010 17:04I don't understand you. As I know, jury's solution don't use misterious knowledges about any sequences. =) O(m) solution doesn't use them as well =) No, I was talking about general logic of my algorithm. Of course, it is incorrect to search for some predefined sequence in the answer. For example, for m=5 general algorithm gives sequence like 1 2 3 4 5 1 2 3 4 (or something like that), but possible answer is 2 2 4 4 4 4 3 2. if m = 5, 2 2 4 4 4 4 3 2 can't be the answer imagine original is on 4th pedestal you touch 2 orig move 4 -> 3 you touch 2 orig move 3 -> 2 you touch 4 orig move 2 -> 3 you touch 4 orig move 3 -> 2 you touch 4 orig move 2 -> 3 you touch 4 orig move 3 -> 2 you touch 3 orig move 2 -> 3 you touch 2 orig move 3 -> 4 you didn't catch the orig! if the sequence has 2 * k numbers suquencially you can take only 2 if 2 * k - 1 you can take 1 (I think) example 2 2 2 2 3 3 3 5 6 --> 2 2 3 5 6 Edited by author 20.10.2010 22:39 Idea: Game of two person and bacward analysis from the end Example: 3 3 1 2 3 3: 1,2-win; 3- fail 2:1,3-win(1->2,3->2) 2- fail 1:2-win(2->1)1,3-fail so win:2->1->2 Edited by author 25.10.2010 14:41 I understand ur algo but I think it's O(n*m). Isn't It? Won't it get TL Yes. But pattern of failed states exits and it's maitaining costts O(1) on eaxh of n steps. what if n = 10^5 and m = 10^5 sequence is like this 4 6 4 6 4 6 4 6 4 6 . . . I think at this test the length of failed pattern is 1 all the time and time is O(n, m) again. Or I didn't understand your previous massage rightly? To Alexander Georgiev: now your solution gets wa51. do you happy? :) Edited by author 20.10.2010 16:37 Yep. It is interesting - how many brute force solutions fail after new tests :) Sort of =) NOW I have to write a real solution :) | New tests were added. Thanks to Fedor Fominykh and Mikhail Rubinchik.(-) | Sandro (USU) | 1790. Searching for the Truth | 20 Oct 2010 16:32 | 1 | | No subject | Moscow SU Chapelnik (Shteiner, Panin) | 1790. Searching for the Truth | 16 Oct 2010 16:14 | 1 | No subject Moscow SU Chapelnik (Shteiner, Panin) 16 Oct 2010 16:14 We got CE for some reason while our compilers manage to run it. |
|
|
|