|
|
Make difference array, where dif[i] = i - a[i] 4 3 1 4 2 answer : 3 12 1 3 5 6 4 1 3 5 7 10 8 2 answer : 11 8 8 2 5 8 1 3 4 5 answer : 4 9 5 3 2 5 4 7 9 2 1 answer : 9 10 2 2 4 4 5 8 7 9 9 1 answer : 1 Edited by author 10.11.2013 18:43 1) Don't forget, that pupils sit in a circle! 2) You have to count how many pupils you can satisfact with choice 'i' boy at first (even he doesn't to be so :-) ). There are algo claimed O(n) 3) If you have such info, it's so easy to calculate the answer ;-) I can send the solution to your mail. This algo gets TL too... plz send me code to rockprogressive.s[at]gmail.com Hi, Yes the problem can be solved by thinking about it as a voting problem. Consider the following input: 5 3 3 1 5 5 1st student wants 4th student to go first. 2nd student wants 5th student to go first. 3rd student wants 3rd student to go first. 4th student wants 5th student to go first. 5th student wants 1st student to go first. 5th student receives the maximum votes so answer is 5. Consider another example from the problem test case. 4 4 1 2 3 1st student wants 2nd student to go first. 2nd student wants 2nd student to go first. 3rd student wants 2nd student to go first. 4th student wants 2nd student to go first. So, the answer is 4. Another example from a test case taken from elsewhere in the forum: 8 1 2 3 5 5 6 7 8 1st student wants 1st student to go first. 2nd student wants 1st student to go first. 3rd student wants 1st student to go first. 4th student wants 8th student to go first. 5th student wants 1st student to go first. 6th student wants 1st student to go first. 7th student wants 1st student to go first. 8th student wants 1st student to go first. So the answer is 1. Edited by author 10.01.2011 04:57 My solution: Calc b[i] - count of numbers such (n+A[i]-i)%n == i Then find max_idx - index of maximum element in array b answer is (n - max_idx) % n + 1 did you get AC? I don't think to satisfy most students is right. for example(the one you mentioned): 5 3 3 1 5 5 your answer is 5,so the sequence is 2 3 4 5 1. we can calculate the difference: |3-2|+|3-3|+|1-4|+|5-5|+|5-1|=8 but for another sequence:1 2 3 4 5,the difference is: |3-1|+|3-2|+|1-3|+|5-4|+|5-5|=6, is smaller than 8. so as my conclusion, we should make the "displeasure" minimal. if using your method, maybe a lot of students is "satisfied(the difference of him is 0)", but others maybe larger. sorry for my bad English. did you get AC? I don't think to satisfy most students is right. for example(the one you mentioned): 5 3 3 1 5 5 your answer is 5,so the sequence is 2 3 4 5 1. we can calculate the difference: |3-2|+|3-3|+|1-4|+|5-5|+|5-1|=8 but for another sequence:1 2 3 4 5,the difference is: |3-1|+|3-2|+|1-3|+|5-4|+|5-5|=6, is smaller than 8. so as my conclusion, we should make the "displeasure" minimal. if using your method, maybe a lot of students is "satisfied(the difference of him is 0)", but others maybe larger. sorry for my bad English. Hi, Yes the problem can be solved by thinking about it as a voting problem. Consider the following input: 5 3 3 1 5 5 1st student wants 4th student to go first. 2nd student wants 5th student to go first. 3rd student wants 3rd student to go first. 4th student wants 5th student to go first. 5th student wants 1st student to go first. 5th student receives the maximum votes so answer is 5. Consider another example from the problem test case. 4 4 1 2 3 1st student wants 2nd student to go first. 2nd student wants 2nd student to go first. 3rd student wants 2nd student to go first. 4th student wants 2nd student to go first. So, the answer is 4. Another example from a test case taken from elsewhere in the forum: 8 1 2 3 5 5 6 7 8 1st student wants 1st student to go first. 2nd student wants 1st student to go first. 3rd student wants 1st student to go first. 4th student wants 8th student to go first. 5th student wants 1st student to go first. 6th student wants 1st student to go first. 7th student wants 1st student to go first. 8th student wants 1st student to go first. So the answer is 1. Edited by author 10.01.2011 04:57 I got AC for voting solution... 4 4 1 2 3 1st student wants 2nd student to go first. 2nd student wants 2nd student to go first. 3rd student wants 2nd student to go first. 4th student wants 2nd student to go first. So, the answer is 4. typo i'd rather like this. cuz it's clear :) What is special about this problem? I get WA 7 all the time. My algo [code deleted] Edited by author 01.01.2013 16:44 Edited by author 01.01.2013 20:16 Edited by author 01.01.2013 20:18 Edited by moderator 29.11.2019 14:27 I found the error, it was not the algo. It was in the routine to find the maximum. The algo is perfect. What is it??? Edited by author 16.10.2010 17:42 Edited by author 16.10.2010 17:43 8 1 2 3 5 5 6 7 8 answer 1 #include <iostream> #include <math.h> using namespace std; int main() { long i,n,a[102020],b[102020],t=0,u,r=1,e; cin >> n; for (i=1;i<=n;i++){cin >> a[i];}; for (i=1;i<=n;i++){b[i]=0;}; for (i=1;i<=n;i++){if (a[i]==1){cout << i; goto lkj;};}; for (i=1;i<=n;i++){b[a[i]]++;if (b[a[i]]==2){cout << i; goto lkj;};}; lkj: ; cin >> i; return 0; } WHY AN ERROR????????????????? Try this one 4 1 1 1 2 Your programm output 1 instead of 3 And your algo is wrong!!! 8 1 2 3 5 5 6 7 8 answer 1 It is the test number 6??? Edited by author 24.10.2010 18:26похоже, что нет. if(n==8) while(true); он вывел WA, так что там другой тест. тогда какой там тест? There's a test like: 7 3 4 5 6 7 1 1 Answer 6. Or something kinda this. There are 100 numbers. 12 5 1 2 3 6 3 8 4 10 3 12 7 anaswer 12 Edited by author 22.04.2011 01:59 >> 12 >> 5 1 2 3 6 3 8 4 10 3 12 7 Why answer 12, but not 2? Edited by author 03.10.2011 17:22 I understand... Because 6 . 8 . 10 . 12 maximum ordered subsequence and sequence 7 5 1 2 3 6! 3 8! 4 10! 3 12! 1 2 3 4 5 6! 7 8! 9 10! 11 12! Edited by author 03.10.2011 18:51 thanks to all))) acept!!! I try with this program....but the answer is "wrong answer in test 10"...do you know why??? [code deleted] Edited by moderator 29.11.2019 14:29 Resize you arrays from 10000 to 100001 and you will get AC ! Пробовал тесты в другой теме-не помогает. Программу уже тестил буквально на всё!!!!!!!! if you have wa13, try test 4 4 4 4 3 answer is 2 why not 1? or 3? 4 4 4 3 4 1 2 3 1st and 4th positions are equal in both sequences. I tried this test,it works.But I have wa13! When I test 3 1 1 1 answer is 1. Edited by author 17.12.2010 22:15 i'm using shellSort and good algo, but wa 7, why??? my program on my machine passes 99999 numbers in 0.2-0.5 seconds! and your 7 test in 0.156 seconds!!! and my algo passes 999 999 numbers(6.7Mb on the txt xD ) for 3 seconds! AND i'm using new algo))) my new algo do O(n*2)(static) operation)) But WA 7((( in 0.14 seconds If there are several possible answers, output any of them.???? check its condition sorry for my english Edited by author 12.11.2010 13:47 Here is my code: #include <iostream> using namespace std; //long int _wants[200002]; //long int _nums[100001]; long int n; long int *_wants; long int *_nums; int main() { cin>>n; _wants = new long int[2*n]; _nums = new long int[n]; for (long int i=0; i<n; i++) cin>>_wants[i]; for (long int i=0; i<n; i++) { _nums[i]=_wants[i]; _wants[i]-=i+1; _wants[i+n]=_wants[i]-n; } long int _max=_wants[0]; long int _pos=1; long int _count=1; for (long int j=0; j<n; j++) { if (_wants[j]>-n) { _count=1; for (long int i=j+1; i<2*n; i++) { if (_wants[i]==_wants[j]) { _wants[i]=-n; _count++; } } _wants[j]=_count; if (j==0) _max=_wants[j]; else if (_wants[j]>_max) { _max=_wants[j]; _pos=j-(_nums[j])+2; } } } if (_pos<=0) _pos+=n; cout<<_pos<<endl; return 0; } My algo is following: we take the input twice, like this: for "4 1 2 3" - "4 1 2 3 4 1 2 3". For each standing in array of meanings we count arr[i]-i . For students standing in a right way to answer counting gives same results. Then we count a number of each difference in our array of 2*n elements, but only for meanings in left half of arr (and write it to the beginning of the arr). After that we will have the length of the longest sequence and its beginning position. There's no problem to say who must be first. I found out that for n=99999 there's a TL. But why? This algo is enough fast... Edited by author 25.10.2010 13:15 your program do O(n^2) operation (you have two embedded loop) beg for sample... my mistake.... My WA program on test 5 gives WA on 3 2 3 1 Can someone give me test 6? |
|
|