Unofficial editorial December long challenge

editorial
,
8

I tried doing a similar approach but don’t understand where I went wrong. Can you help?
The link is https://www.codechef.com/viewsolution/16530358

9

Nicely explained!
I was stuck on the problem Total Diamonds [VK18]. I kept looking for patterns to develop a formula in order to establish my O(1) solution; apparently I was looking in the wrong direction altogether.

10

For CHEFEXQ: Chef and easy XOR Queries, i wrote a blog post which can help you guys understand square root decomposition. Blog post link.

11

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 CodeChef: Practical coding for everyone.

12

Can you explain why you used the condition ((i + j)&1 == 1) in GIT01

13

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?

14

This is my solution for CPLAY. CodeChef: Practical coding for everyone Can someone check and tell me why its giving Wrong Answer?

15

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
16

@taran_1407 can u please check this code CodeChef: Practical coding for everyone
FOR GIT01

17

I can’t believe but I used the exact same approaches for all the 3 problems and in 3rd question, I solved it subtask wise only, i.e. the same approaches explained for each subtask by you.

18

When you have 1e5 test cases to answer, you would find it really common to pre-process in such a way that we can answer our queries in O(1) or O(logN). Otherwise we’ll get TLE.

I just solved the problem for all values from 1 to 1e5, answering queries int O(1).

19

Cheers!! Happy Coding…

20

Well, I’m glad that we are not in for plagiarism accusation then… :smiley:

3 Likes
21

Hey, I have run the code and it gives 8 as output. Check it here: 2oXGt7 - Online Java Compiler & Debugging Tool - Ideone.com .

[Note: I have used @taran_1407 's code.]

22

All top solution??

Can you please mention that solution link, which gives 16 as answer.

23

Well, the problem states that every red marble should only have green marbles in four adjacent cells. Yes, problem doesnt mention chess board, but as i identified the pattern, i saw it similar to chess board. Where a white cell always has four black adjacent cells and same for black cells.

I mentioned chess board to make myself entirely clear. :slight_smile:

24

As we move from, say N= 2 to N=3,

ans[3] = ans[2] + (4+5)(for last row except last element) + (4+5)(for last column except last element) +2*3

ans[3] = ans[2] + 2*(sum[5]-sum[3]) + V[2*3].

ans[i] = ans[i-1] + 2*(sum[2i-1]-sum[i]) + V[2i]

Cheers

25

Shouldn’t sum[1] be 1 instead of 0??

That’s the only error i guess.

26

@taran_1407 no it’s just that the array need’s to be long long thanks by the way a more memory efficient is possible solution:- CodeChef: Practical coding for everyone

27

@taran_1407
i have edited my post.