Need help in DRSTRNGE

#1

What’s wrong in my solution?(in which case its failing)
Its working for maximum constraint.
https://www.codechef.com/viewsolution/30358122

Question link : https://www.codechef.com/COSQ2020/problems/DRSTRNGE

#2

If I’m deciphering the Problem statement correctly (seeing questions from external contests always make me appreciate the job that the official Codechef problem-setting panel does :)), it’s easy to write a verifier for this:

#include <bits/stdc++.h>
#include <iostream>
#include <set>

#define boost ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
#define f(a,b) for(int i=a;i<b;i++)
#define mod 1000000007
using namespace std;

int h[10000000];

bool isUnique(const vector<ll>& z)
{
    set<ll> sumsOfSubArrays;
    for (int i = 0; i < z.size(); i++)
    {
        ll sum = 0;
        for (int j = i; j < z.size(); j++)
        {
            if (z[j] > 1'000'000'000)
                return false;
            sum += z[j];
            cout << "sum of [" << i << ", " << j << "] = " << sum << endl;
            if (sumsOfSubArrays.find(sum) != sumsOfSubArrays.end())
            {
                cout << "Duplicate subarray sum found!" << endl;
                return false;
            }
            sumsOfSubArrays.insert(sum);
        }
    }

    return true;
}

void solve()
{
    ll n;
    cin>>n;
    ll c=1;
    vector<ll> z;
    f(0,n)
    {
        while(h[c]!=0)
            c++;
        z.push_back(c);
        ll sum=0;
        for(ll j=z.size()-1;j>=0;j--)
        {
            sum+=z[j];
            h[sum]=1;
        }
    }
    f(0,n)
        cout<<z[i]<<" ";
    cout<<endl;
    assert(isUnique(z));
}

int main()
{
	boost;
// 	int t;
// 	cin>>t;
// 	while(t--)
// 	{
		solve();
	//}
	return 0;
}

The N=8 case is the earliest failure I can find.

2 Likes
#3

Thank you sir

1 Like