my solution link:
https://www.codechef.com/viewsolution/32190104
I am getting AC in subtask 1 but WA in subtask 2. Can someone help me out??
1 Like
Use long long to store values in array… You are having integer oveflow that is why it is giving WA
But the upper limit is 1e9 which can be stored in int.
When I initialized ‘min’ as long long ,the solution got accepted but I had initialised it with 1e9+6 and then updated it with a lower value.
I didn’t get it.
Coins also has to be declared long long. The expression
coins+=len*min is over flowing. Len*min is calculated first. Which overflows, ans is then added to coins. If you declare min or len as long long l, then that won’t happen.
Also @vijju123
Is it possible to add a test case with 5 strictly decreasing arrays of length 10^6. Codes with worst case O(n^2) are passing.
Unless that is intended to show the difference between amortised complexity and worst case complexity.
1 Like
I will see what can be done about it. Do you have any sub optimal solution for reference?
1 Like
T=1, n=10^5
CodeChef: Practical coding for everyone - 3.38 seconds
CodeChef: Practical coding for everyone - more than 5 seconds.
TL is 1 second;
They were checked by replacing the input loop with a[i]=n-i; since I needed to check on codechef servers and I couldn’t paste it on custom input.
The code I used to check are here
Code 1
//* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
int size=100000;
int[] arr=new int[size];
int min=Integer.MAX_VALUE;
int index=-1;
long total=0;
for(int i=0;i<size;i++){
arr[i]=size-i;
if(arr[i]<min) {
min=arr[i];
index=i;
}
}
total=(long)min*(long)size;
while(index!=0){
int temp=Integer.MAX_VALUE;
int ix=index;
for(int i=0;i<index;i++){
arr[i]=arr[i]-min;
if(arr[i]<temp) {
temp=arr[i];
ix=i;
}
}
total+=(long)temp*(long)index;
index=ix;
min=temp;
}
System.out.println(total);
}
}
}
Code 2
#pragma GCC optimize "trapv"
#include <iostream>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while (t--)
{
int n;
long long coins=0;
//cin>>n;
n=100000;
int a[n];
for (int i=0;i<n;i++){
a[i]=n-i;
}
//cin>>a[i];
int len=n;
// cout<<n;
while (len)
{
// for the array
int i,ind;
long long min=1000000006;
for (i=0;i<len;i++)
{
if (a[i]<min)
{
ind=i;
min=a[i];
}
}
// cout<<len;
coins+=(len*min);
for (int j=0;j<len;j++)
a[j]=a[j]-min;
// cout<<"g"<< a[0]<<endl;
len=ind;
}
cout<<coins<<endl;
}
return 0;
}
Edit : In fact some codes are flat out incorrect.
This CodeChef: Practical coding for everyone
gives WA for
Test case
1
3
3 4 2
I understand you probably don’t want many tests, especially for a cakewalk problem, but 1 test case per subtask is too less.
1 Like
I cannot understand what’s wrong with my code.
It is giving AC for first task and WA for the second task.
code:-
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int ans(ll arr[], ll en)
{
ll mn = 1e10;
ll mnindex = -1;
if(en<0)
{
return 0;
}
ll i;
for(i=0; i<=en; i++)
{
if(arr[i]<mn)
{
mn = arr[i];
mnindex = i;
}
}
ull sum = (en-mnindex+1)*arr[mnindex];
return sum+ans(arr, mnindex-1);
}
void solve()
{
ll n;
cin>>n;
ll s[n];
ll i;
for(i=0; i<n; i++)
{
cin>>s[i];
}
cout<<ans(s,n-1)<<endl;
}
int main()
{
ll t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
I have used divide and conquer. someone please review
my code.