The distances between the x are variable.
You want the max heights to be where the max distances between x are (biggest area gains).
distance between first and last is just to one neighbor, for all others to all neighbors.
In which order will we take the height ?
Heights are the x coordinatesā¦Then any order as ending or descending order of differences of consecutive point but multiply the maximum height differences with maximum of sum of parallels . I didnāt tried but hopefully thatās the correct way
Actually too few participants were there in this cookoff for div 1 due to end semesters rarely I dont participate in contests at codechef and codeforces but the exams were also coming o I preferred exams over the competition but when I solved first question in one go I regret my decision not to participate as the first question of div1 as unusual was very easy to solve.
easy solution link.
This is the basic approach when all the points are consecutive but see when points are non consecutive your approach will fail see the link of my solution
easy-code
Thanks, I will try with Brute forceā¦
Yeah, I had endsems until friday + codechef certification yesterday. Was kind of an onlooker, solved but did not submit during the contest window.
I was just going through my solution of BIGRES and realized that i did not write what i intended to, still got AC during contest !
Solution submitted during contest
https://www.codechef.com/viewsolution/27936782
Submitted in practice
https://www.codechef.com/viewsolution/27941380
Notice the difference in lines 19 and 20 of both solutions
I got AC because java initializes array with 0
Can anyone help me figure out where i am wrong with approach for ques ROBOTS.
My submission link is : CodeChef: Practical coding for everyone
Can someone explain me the approach for the problem The Biggest Restaurant.
It is the only mistake i made during the contest. Rest of my solution was correct.
Yeah i see it now xd. I tried it this morning as i said. Rearrangement inequality is to be used instead. So instead we can sort the intervals union {0,0} and the heights as well then match get the answer.
Also, robots i did with segtree but its very easy using prefix sums. Btw can someone give a hint for the compos one? Im tryna use segment trees but that same issue i mentioned before is killing me.
Well You could have implemented the correct logic in a better way :
By taking a bigger 2-D character array and without worrying of ever going out of bounds. Just remember to explicitly make all other elements of the array = ā0ā ( as question says ) and rest will go wellā¦ Hope this helps !
This is an easy code to understand the brute force involved. Just ignore the macro and focus on the solve() function.
The point is to declare a bigger array as this would prevent us ever going out of bounds
Ok i got the compos one using ordered maps and marking of L and R per update + some optimization.
haha, Thanks for the tip, however, I didnāt do the compi for rank, I just did for practice, and that question seemed interesting to tackle. I will try again and see where I went wrong
Hi buddy,
Actually I have memoized the previous values in cx and cy array (short for coordinate x and y), and yes It didnāt strike me to store values of sine and cosine in an array directly, however, I believe calculation and look up will have almost same time. What do you think?
Yes, what I mean is that getting cx[r] - cx[l-1] doesnāt give the desired value without a bit of tweaking I think. However, you definitely do need to keep previously found values for l-r somewhere.
Are you getting the correct values for the given testcase? If so, Iām probably wrong. I am, but I am getting a timeout so I need to use an appropriate data structure to memorize previous calculations (which was what I was trying to do before I ran out of time).
This is kind of a rough write up for how I did CHADAY.
Have an array of vector<int>'s; one for each of the N participants. Also, weāll be using set (ordered set) here.
Let us take the compoās one by one and process them. Let us say we are at a compo \mathcal C currently which includes challenges from A to B (inclusive). Then what we do is, for each challenge C in this range, we map L(C) to X(C) (increase the mapped value if already mapped) and R(C)+1 to -X(C) (if it is in range). Thus we can āmarkā ranges in \mathcal{O}(1) time. Now, say we just finished the marking procedure for the compo \mathcal C. Now what we do is maintain a temporary sum variable, initialized to 0, and move from left to right in our ordered map, adding the update values that we āmarkedā along the way. Also, at each of the 2*\text{number of marked points} we do the following:
- If the current sum is positive and none of the below cases hold, then just push the mapped value at this position to the vector corresponding to it.
- If the current sum just changed from positive to negative, then push -(\text{last positive value of sum}) to the vector corresponding to this index.
- If the current sum just changed from negative to positive then push the value of the current sum (not the mapped value) at the corresponding position.
Try to figure out why we do the last two before moving on(if you havenāt already).
We do this for all compos. Now, at the very end, maintain another sum variable initialized to 0.
Now scan the list from left to right. At each position, add to the sum all (if any) values in the corresponding vector. After this, print the value.
Why this works:
In each marking step basically we are saying āincrement value for this rangeā. Now what are the problems that could arise? That a skill change is negative and so the participant doesnāt want to participate in the compo. But this is only when the temporary sum becomes negative, in which case we add the negative of the last positive sum to make it exactly 0. To handle the reverse (negative to positive) scenario we include the last case (see above).
Time Complexity:
It takes \mathcal O(N) time to print the output. The map operations each take \mathcal O (\log M) time and there are at most MQ of them. Similarly, the number of āupdateā operations in the final scan from left to right is at most 2MQ as in each marking stage we mark 2 positions and we do this at most MQ times.
Thus the time complexity is \mathcal O (N + MQ \log M) which barely fits the time limit.
Edit: We can get rid of a log factor, see @mnaveenkumar20 's reply.
1 Like