ARRT - Editorial

1
9
12 8 15 5 1 2 3 13 4
3 14 5 16 2 7 4 18 13
1 Like

I don’t know why it’s showing out of bounds… But my code is working fine on my pc and on online gdb… Maybe it’s failing on some other test case… But it is working fine for the test case given by you.

I am sorry for the confusion !! Fixed

3 Likes

There’s undefined behaviour for you :slight_smile:

It absolutely is an out-of-bounds access: add this line before the line I mentioned:

cout << "ans3+1: " << (ans3 + 1) << " ans+1: " << (ans + 1) << " n: " << n << endl;

to see it:

ans3+1: 10 ans+1: 4 n: 9
/usr/include/c++/7/debug/vector:417:
Error: attempt to subscript container with out-of-bounds index 10, but 
container only holds 9 elements.
1 Like

Solution: 49348544 | CodeChef can anyone tell me what’s wrong with my solution, it’s getting accepted partially.

Consider the test input:

1
8
16 5 4 1 6 13 8 12
8 12 6 16 15 2 7 11

Hi! Can someone help with this:
https://www.codechef.com/viewsolution/49375345

The code is passing the first test and not the 2nd one.

Thanks!

Consider the test input:

2
3
1 4 5
1 3 4
3
1 4 5
1 3 4

Can anyone tell me how to think of a test case during a contest when our sol gives wrong ans??

Dunno about during a short contest, but here’s what I’ve been using in this thread:

http://vps2.etotheipiplusone.com:30176/public_html/codechef/ssjgz-ARRT.cpp

./a.out --test > last-testcase.txt; cat last-testcase.txt | ./a.out 

to write a random testcase to last-testcase.txt and print the (brute-force calculated) output.

I usually combine everything into one (e.g. CodeChef: Practical coding for everyone) so I can just run:

while true; do ./a.out --test | tee last-testcase.txt | ./a.out ; if [ "$?" -ne "0" ]; then break; fi; done | g

until it finds a mismatch.

1 Like

but what you do sir when your solution gives wrong ans?? how do you find where is the mistake

  1. Find a testcase where your solution gives a different result to the simple, brute force solution, as above
  2. Find out why it does that
  3. Fix it!

Thanks! But it is still failing:
https://www.codechef.com/viewsolution/49376305

1 Like

Consider the test input:

1            
18
24 8 5 35 26 32 2 4 21 19 12 1 15 27 17 10 28 25
14 30 6 12 19 32 29 26 2 35 7 5 27 4 22 28 1 9
1 Like

I guess the test cases were weak my O(n^2) solution passed.
I knew it was gonna TLE still submitted it in last 15mins and got accepted :slight_smile:
Link to my solution:
https://www.codechef.com/viewsolution/49349215
My code will have worst case when the ci will be in decreasing order
eg
5 4 3 2 1

bhai kya aap bta sakte ho ki kaise at most 2 starting point exist karte h maine editorial dekha par usme bhi ye wala portion samaz nahi aaya

I don’t speak Hindi :slight_smile:

1 Like

See element range is form1 to 2*N
Lets take an Example
lets say
arr[] = {1 2 3}
brr []= {…anything doesn’t matter …}

Now you want first elememt of your sequence as minimum as possible
so lets try to make C[0] = 0

for that equation will look like (arr[0] + x)%N = 0 where N = 3 and arr[0] = 1

for this perticular example x value can be 2,5,8,…)
but brr[i] range is 0 to 2N (means 0 ot 6 for above example)
So x value is 2,5 that you will search in brr whether it is present or not
if not the you will try to make C[0] = 1 {(arr[0] +x)%N= 1} and so on

that’s the logic of atmost two starting point
Hope my explanation is good enough to clear your doubt

1 Like

bro i saw the editorial i understand the mostly solution but did not get why he said at most two numbers whose mod n is same in the range 1 to n and n+1 to 2n if you can please resolve this doubt

@ssjgz bro tell me whether my logic is correct or not