Invitation to Byterace 2k20 on CodeChef [Rated for Div-2]

i have used a simple technique of storing indices only in the updating array, feel free to check here

ps-problems were really good(even though i f***ed up a simple one)

2 Likes

Think for a while. Double prefix sum helps here.

1 Like

I just got an AC on 4th problem 2 minutes after the contest, missed it by one insert statement. Problem worst feeling ever :sob:
AC_CODE
WA_CODE

3 Likes

i took forever on B and C and solved D in like 15 minutes

explain your logic / intution

hey @tamo11 @l_returns How do I report plagiarism in this contest. there a few submissions with the same code. These people have used the same code in the December lunch-Time as well.
the submissions are :
solution 1
solution 2
solution 3
solution 4
solution 5
solution 6

Before you change the rating of DIV 2 please run a plag test…
Checked random solution of ques 4 and got this.

Soln1
soln2
soln3
soln4

Just check the 17 mb solution of 4th question in c++ you may find many more…

Can you please explain how using prefix sums twice helps?

Here’s my solution : O(n) Solution

I solved using 3 hashmaps. First one to store the number of points that start at a given indeix, one to store the number ending points at given index, and one to store how long the ranges are, mapped to their ending points.

Then I simply iterated through the array maintaining the number of active ranges and the total amount that they add to each index. When a new range is encountered, simply increment the active ranges and when the range ends, simply decrement the active range At the end of each loop, update the total range as total range += no: of active ranges.
Also subtract the amount added by the expired ranges if their ending point is reached

1 Like

Can anyone please point out the mistake or any test case in which my solution fails for problem B, Solution Link - Solution: 40931954 | CodeChef Thanks in advance :slight_smile:

0 0 0 0 0 0
1 0 0 -1 0 0
This is how we update it
Now, one prefix sum will make it
1 1 1 0 0 0
Second will make it
1 2 3 3 3 3
Now can you see how it helps?
We need to remove last 3 3 3 by one more update on initial array

Now try to connect these pieces. The editorial will be out soon. Then you can read full solution if you are not able to figure it out.

Edit: editorial

1 Like

and we update at R+1 with -(R-L+1) value right ?

1 Like

EDITORIAL will be published soon. Thanks all for participating :slight_smile:

2 Likes

Does problem 5 require RMQ knowledge? Or there is a simpler way?

stack

see for any index we are basically calculating (number of ranges in which it lies)*i-sum of beginning indices of ranges,
so we need to just store the sum of beginning ranges, and we can mark beginning and endings by i and -i
now i m using an arraylist because the same index can be used in multiple queries, so i m updating all the query start/ends in that index, before moving on to find the value of the index

the contest is most better to cooking of and lunch.
plz the author u set codechef round next time

Liked the problem Cybertree.

1 Like

I solved the first four questions today. I had a correct divide and conquer with RMQ via sqrt-decomposition approach for the fifth (now AC), but I messed up some details in the code. Link to YT livesolve video

1 Like

Why are my submissions not shown in my profile?