Common Boardlook at overflow!!! in test 13 there are meny than 32 different dishes!!! my bug was: int h = j; ... d[i] |= (1 << h); change it to __int64 h = __int64(j); ... d[i] |= (__int64(1) << h); Edited by author 26.08.2008 17:18 Limit for dishes is 100. Why __int64 (64 bit) should be better than int (32 bit)? In both cases you need an array, don't you? CAN SOME ONE GIVE ME SOME TEST? MY GMAIL: LIHE21327@GMAIL.COM First, DP needs to be 2D. Values array can be 1D, but backtracking info should be 2D. At least I couldn't make it 1D. And even after making parental state indication 2D I still had bugs in that back-traversal :) about wa 13 i am pretty sure its a problem with backtracking. its a greedy+dp according to me you should analyze the four scenario like 1. two increasing sequence :
take two array . two array initially have only one value zero. then iterate over 2nd to nth element. if element > 1st and 2nd arrays last element then, 1st sequence last element > 2nd arrays last element then: (add element to the 1st array) otherwise (add element to the 1st array) otherwise add it to the array whose last element < element
(this is optimal ). 2. two decreasing sequence: approach greedily like 1st one 3. one increasing and one decreasing(1st element included in the increasing array):(try yourself) 4. one increasing and one decreasing(1st element included in the decreasing array):(try yourself) for 3rd and 4th criteria , think greedily also. my solution is 0.14sec if you are better plz email me s-2017915104@isrt.du.ac.bd The program is already installed in one computer. Now, we need to install it in (N-1) computers. abc cba 6 aba bab 2 abcabc cba 5 abcbaabdca abcada 1 abcabbaca abcabbc 1 thnx a lot for your tests you can easily find the solution with O(nk^3) but it will give u tle after optimization with cumulative sum array it will be O(nk^2) import java.util.Scanner; public class Staircases { public static void main(String... args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); System.out.println(find_Q(N, N)); }
static int find_Q(int X, int Y) { int U = X-1; if(Y<X) { U = Y; if(Y == 0 || Y ==1) return 1; } if(Y<=1) return 0; int A = 0; for(int i = U; i > 0; i--) A += find_Q(i, Y-i); return A; } } Use bottom-up approach, calling function and return rakes huge amount of time I've implemented several approaches, ones calculate 1/4 of circle, another ones calculate 1/8 of circle. All of them works fine for R < 60000000. With R > 60millions there is a chance (and it increases with bigger R) 2 approaches can give different results. They use the same calculations (sqrt, ceiling). I also tried to implement 1/8 without float point numbers, by integers only. Same result with same difference. Maybe these "magic" numbers can help someone r: 67250001 correct: 14208049816923164 diff: 12 r: 67250051 correct: 14208070944129524 diff: 4 r: 67250211 correct: 14208138551359320 diff: 4 r: 67250249 correct: 14208154608083608 diff: 8 r: 67250321 correct: 14208185031387396 diff: 16 r: 67250433 correct: 14208232356606236 diff: 4 r: 67250449 correct: 14208239117361224 diff: 4 r: 67250505 correct: 14208262780007696 diff: 4 r: 67250601 correct: 14208303344588340 diff: 8 r: 67250697 correct: 14208343909213316 diff: 4 r: 67250769 correct: 14208374332717888 diff: 4 r: 67250825 correct: 14208397995480888 diff: 4 r: 67250835 correct: 14208402220968636 diff: 4 r: 67251315 correct: 14208605045441340 diff: 8 r: 67251347 correct: 14208618567139620 diff: 12 r: 67251457 correct: 14208665047975948 diff: 4 Edited by author 07.04.2021 02:35 Forget about what I said earlier. It is always good idea to return to the problem with fresh mind :) It turned out my correct solution was actually incorrect, and my incorrect solutions were correct. If you are using sqrt and ceil, try to calculate ceil(sqrt(2 * 63611501 * 67250001 - 63611501 * 63611501)), and you will get wrong result I was able to get AC C# solution with 467286474 int64 multiplications for R=10^9, no divisions, and no floating point usage. Edited by author 08.04.2021 01:53 Edited by author 08.04.2021 01:53 I got WA in first test. I checked my program using a lot of compiler and in first test my program outputs is correct. my code id:9308865 +1 Just use Dirichlet's principle. AC in 0.015 sec with dp if u r better with math plz reply Edited by author 07.04.2021 13:27 Edited by author 07.04.2021 13:27 Edited by author 07.04.2021 13:27 AA=0,AB=1,BA=2,BB=3 cnt[0]=no. of AA,cnt[1]=no. of AB........... int sz=2; if(last letter==A) szvalue=0; if(last letter==B) szvalue=2; define DP[cnt[0]+2][cnt[1]+2][cnt[2]+2][cnt[3]+2][sz]; dp 1,0,0,0,0=1; //for AA dp 0,1,0,0,1=1; //for AB Edited by author 05.05.2016 19:23 I think string is: result = str(b) +result During this operation: - new string with size = result.size+1 created; - b contents copied to new string I am not sure about memory but it must lead to TLE. You know your n1, n2, result strings have known size = n. You should rather use efficient byte arrays of size n to store n1, n2, result contents Edited by author 28.04.2016 13:22 if You get TLE verdict, U can try to use short instead of int I had int n,i; and I had wa #10, then I changed them to long long and got ac, but I can't understand why I got wa10 with int n,i; where i and n can't exceed 10^6. It's obviously a mistake in task's text. Program won't be accepted until it will work with n=10e6. thanks for your hint, helped me to get accepted verdict When you divide at the end by n*(n - 1) it gets overflow so you need to have type long long Edited by author 31.10.2020 16:46 Edited by author 31.10.2020 16:46 You need long long n. Because you divide at the end by n*(n - 1),n*(n-1) is overflow. My algorithm is O(R) and i have AC I got WA at #1 and I use line tree. Now I've accepted! Edited by author 07.03.2013 19:40 Try to change compiler to Microsoft Studio. Worked for me what is test5 look like? Stacked at this point too. Found that following example crashes my structure for a looooong time to think: 2222223222222222322222222222322222222232222222222232222222223222222222223222222222322222 5 a aa afa aaaa aafaa answer should be like "aaaa aafaa aaaa aafaa etc..." Thanks for this example. My backtracking solution also is way too slow. Yes. A very nice benchmark. Edited by author 03.05.2015 16:52 Edited by author 03.05.2015 16:53 aaaa aafaa aa aaaa afa aaaa aaaa aafaa aa aaaa afa aaaa aaaa aafaa aa aaaa afa aaaa aaaa aafaa aa aaaa afa aaaa Very nice test, I understand, because my program is too slowly. Edited by author 02.04.2021 18:58 Hello. My program passes all tests from the forum, but I still get WA6. I do brute force First, I go through all the elements that are to the right of the current one, then everything that is to the left can anyone have any tests? here is y code is needed: #include <iostream> using namespace std; int n, result = 0, sizeHelpArray = 0, sizeAnswerArray; int line[100][2], helpArray[100][2], answerArray[100][2]; //initialization and sorting on the left border void Init() { int i, j; cin >> n; for (i = 0; i < n; i++) { cin >> line[i][0] >> line[i][1]; if (line[i][0] > line[i][1]) swap(line[i][0], line[i][1]); } for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if (line[j][0] < line[i][0]) { swap(line[i][0], line[j][0]); swap(line[i][1], line[j][1]); } if(line[j][0] == line[i][0]) if (line[j][1] < line[i][1]) { swap(line[i][0], line[j][0]); swap(line[i][1], line[j][1]); } } } } //adding a segment to the temporary answer void AddInHelpArray(int index) { sizeHelpArray++; helpArray[sizeHelpArray][0] = line[index][0]; helpArray[sizeHelpArray][1] = line[index][1]; } //to record the best current result void copyInAnswerArray() { int i; for (i = 0; i < sizeHelpArray + 1; i++) { answerArray[i][0] = helpArray[i][0]; answerArray[i][1] = helpArray[i][1]; } } void sortAnswerArray() { for (int i = 0; i <= sizeAnswerArray; i++) { for (int j = i + 1; j <= sizeAnswerArray; j++) { if (answerArray[j][0] < answerArray[i][0]) { swap(answerArray[i][0], answerArray[j][0]); swap(answerArray[i][1], answerArray[j][1]); } if (answerArray[j][0] == answerArray[i][0]) if (answerArray[j][1] < answerArray[i][1]) { swap(answerArray[i][0], answerArray[j][0]); swap(answerArray[i][1], answerArray[j][1]); } } } } void Solve() { int i, x, tmp = 1, currentPoint; //starting from the first element .. for (x = 0; x < n; x++) { sizeHelpArray = 0; tmp = 1; memset(helpArray, 0, sizeof(helpArray)); //I write the current element to an auxiliary array helpArray[sizeHelpArray][0] = line[x][0]; helpArray[sizeHelpArray][1] = line[x][1]; currentPoint = line[x][1]; //Checking items to the right of the current one for (i = x + 1; i < n; i++) { if (line[i][0] >= currentPoint) { tmp++; currentPoint = line[i][1]; AddInHelpArray(i); } }
currentPoint = line[x][0]; int border; border = line[x][0]; bool first = true; //Checking items to the left of the current one for (int j = 0; j < x; j++) { if (line[j][1] <= currentPoint && first) { tmp++; currentPoint = line[j][1]; AddInHelpArray(j); first = false; } else if (first == false && line[j][0] >= currentPoint && line[j][1] <= border) { tmp++; currentPoint = line[j][1]; AddInHelpArray(j); } } //If the result is better than the previous one, then I save it. if (tmp > result) { result = tmp; copyInAnswerArray(); sizeAnswerArray = sizeHelpArray; } } sortAnswerArray(); cout << result << endl; for (int i = 0; i <= sizeAnswerArray; i++) cout << answerArray[i][0] << " " << answerArray[i][1] << endl; } int main() { Init(); Solve(); return 0; } Edited by author 02.04.2021 07:26 Edited by author 02.04.2021 07:26 Edited by author 02.04.2021 07:37 Edited by author 02.04.2021 07:37 |
|