You are not logged in. Please login at www.codechef.com to post your questions!

×

MAXSEGM: Need speacial test case / spot the bug

Hi,

Recently I have been trying hard to find the bug in my code for the problem MAXSEGM, which was the second question of June Lunch Time(LTIME49). And strange enough I am getting 70 points, (not 30, nor 100). It clearly means I am missing some special test case or their might be a small bug in my code.

Please help me in spotting the bug, or giving a test case for which my code can give wrong answer.

If you prefer the link of my "70" points solution: link

The code is pasted below:

#include <bits/stdc++.h>
#define gc getchar_unlocked
using namespace std;

int fastScan()
{
    int n = 0;
    register int c;

    c = gc();
    while(c < '0' || c > '9')
        c = gc();

    for (; c >= '0' && c <= '9'; c = gc())
        n = n * 10 + c - '0';

    return n;
}

#define ARR_MAX 1000000
int w[ARR_MAX], c[ARR_MAX];

long long int findMaxUniqueSum(int n)
{
    unordered_set<int> number;

    int j = 0, maxLen = 0, iIdx, jIdx;
    long long int sum = 0, maxSum = 0;
    for (int i = 0; i < n; i++)
    {
        while (j < n && number.find(c[j]) == number.end())
        {
            number.insert(c[j]);
            sum += w[j];
            j++;
        }

        if (j - i > maxLen)
        {
            maxLen = j - i;
            maxSum = sum;
        }

        else if (j - i == maxLen && sum > maxSum)
            maxSum = sum;

        number.erase(c[i]);
        sum -= w[i];
    }

    return maxSum;
}

int main()
{
    int t, n;

    t = fastScan();

    while (t--)
    {
        n = fastScan();

        for (int i = 0; i < n; i++)
            c[i] = fastScan();
        for (int i = 0; i < n; i++)
            w[i] = fastScan();

        long long int sum = findMaxUniqueSum(n);

        cout << sum << "\n";
    }

    return 0;
}

asked 29 Jul '17, 10:33

nvs232's gravatar image

2★nvs232
344
accept rate: 0%


You have misunderstood the Q

You only need to find a unique range with max sum, NOT the longest unique range with max sum.

Here is where your code fails-

Input
1
3
0 0 1
2000 10 100
Your Output
110
Expected Output
2000
link

answered 29 Jul '17, 11:14

vijju123's gravatar image

5★vijju123 ♦♦
15.1k11857
accept rate: 18%

Silly me, thanks! Got it correct.

(29 Jul '17, 11:31) nvs2322★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×122
×34
×15
×4

question asked: 29 Jul '17, 10:33

question was seen: 304 times

last updated: 29 Jul '17, 11:31