I am sorry for the confusion !! Fixed
There’s undefined behaviour for you
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.
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.
but what you do sir when your solution gives wrong ans?? how do you find where is the mistake
- Find a testcase where your solution gives a different result to the simple, brute force solution, as above
- Find out why it does that
- Fix it!
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
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
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
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
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
Your logic is unconvincing. You might want to elaborate further, using some examples.
n = 3
a[] = 1,2,3
b[] = 2,3,5
so as a[0]% 3 = 1 and b[2]%3 = 2 so we rotate in one time so that first index of c be 0
as i was searching for no n - a[0]%n so that i can get 0 at first index