For CHEFEXQ: Chef and easy XOR Queries, i wrote a blog post which can help you guys understand square root decomposition. Blog post link.
I wonder, but I have WA in VK18 and still canāt catch where are principial differ of my code and solution idea, except I hasāt optimaze it.
I try different kinds of debug output, but cannot fix whatās wrong. Its seems correct, but WA appears anyway.
Here is link to my solution https://www.codechef.com/viewsolution/16540692.
Can you explain why you used the condition ((i + j)&1 == 1) in GIT01
For pre-processing you will need to declare array of size V[2000000], but my compiler (C++11) gives segmentation fault. How to solve this issue?
This is same as (i+j)%2 == 1 (in bitwise).
This condition automatically make adjacent cells of different colors.
Often you would find thatwhenever there are 1e5 test case, you need to answer test cases in O(1) or atmost O(logN) time. For that, itās very often you preprocess all answers, or enough to find all answers.
Nice one!!
I donāt think there should be such a problem, but you can refer to this memory efficient solution if you can declare an array of size 1000000.
This is my solution for CPLAY. https://www.codechef.com/viewsolution/16567845 Can someone check and tell me why its giving Wrong Answer?
There are two errors in your solutionā¦
First, you were not reading all the input lines. You were just reading the first line. Try putting a loop and break the loop at the end of the input file.
Second, you have commented out a portion of your solution from line 5-18
I was stuck on the Vk18 since 2 days, I had solved the question as you did in subtask-2, but I always wondered about finding a formula or pattern to get a O(1) solution for the 3rd subtask. So as a beginner is it always allowed to pre-process answer or only when there is no other way (how to find that there is no other way and you need to preprocess??)
btw thanks for the editorial!
1 Like
Well, it is not always necesaary that you need to preprocess the answer. Rather, take CHEFUNI of current long challenge. It too require O(1) answer, because T upto 1e5. But in that problem, we cannot even store or calculate answers for all possible values of X, Y Z, A,B and C.
Well, preprocessing often is easier but have time and memory constraints. If preprocessing is feasible with given constraints, go with preprocessing, else prefer constant time solutions (comparatively tougher than preprocessed solution as i feel).
So, it depends upon problem and constraints.
Got it!.
I was doing it only for the first line.And after I got a wrong answer, I commented the code to atleast get the 1st subtask right.Which again failed coz i was just processing first line.
You can visualise it as a 2-D matrix rather than a chessboard. These patterns become obivous after some practice on similar problems.
Ofcoursw i can check, but i would recommend u to solve this again, using the way i tell u belowā¦
First make a 2D character array, and take all input.
Now, solve this for first case, that is, if (i+j)%2 == 0, color should be green, otherwise red, and calculate cost
Now, solve this for second case, that is, if (i+j)%2 == 0, color should be red, otherwise green, and calculate cost.
Output minimum of both.
Idea Use separate loops whenever u feel it complicatedā¦
@dinesh2193 you first initialize 1D array
string a[n]
and then you doing this a[i][j] you didnāt initialize a 2d array and as taran said try to separate the for loops when getting the input and solving the problem
yeah ,i got the answer for both the above methods.but i had not used any extra space for creating a 2D array(for the above two cases) but used a single variable which can optimise the solution.but it didnt get accecpted
I want you to to solve the problem the way i mentioned, and then rewrite the solution in the way you want, Thatās how we all learnā¦
PS: Donāt mind using extra space, as long as it gets you an AC, and then reduce space complexity.
I hope you donāt mind that.