C++ Logic Implementation Help - program timing out | Together C & C++ | Page 1

gritty knotBOT Dec 18, 2023, 1:25 AM

#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

real acorn Dec 18, 2023, 1:26 AM

#

Cant help without seeing code

wise flax Dec 18, 2023, 1:26 AM

#

real acorn Cant help without seeing code

alright, should I send the code that I have?

real acorn Dec 18, 2023, 1:26 AM

#

TLE is almost always because your algorithm is suboptimal

wise flax Dec 18, 2023, 1:26 AM

#

these are the sample cases btw

#

Scoring:
Inputs 1-3: N <= 2
Inputs 4-5: N <= 50 and a_i, h_i <= 10^3
Inputs 6-8: N <= 10^3
Inputs 9-13: No additional constraints
and this is the scoring (for time complexity)

gritty knotBOT Dec 18, 2023, 1:27 AM

#

How to Format Code on Discord

Markup

```cpp
int main() {}
```

Result

int main() {}

wise flax Dec 18, 2023, 1:27 AM

#

my program is getting the first 3 cases, but 4-8 wrong, and timing out for 9-13

#

@real acorn can i dm you my code?

real acorn Dec 18, 2023, 1:29 AM

#

no

wise flax Dec 18, 2023, 1:29 AM

#

real acorn no

ok here's my code

real acorn Dec 18, 2023, 1:30 AM

#

just at a glance, TLEs are gonna be caused because you have an O(n^2 log n) algorithm

wise flax Dec 18, 2023, 1:31 AM

#

real acorn just at a glance, TLEs are gonna be caused because you have an O(n^2 log n) algo...

oh ok

#

how do you think i should fix it

#

so like O(n^2) isn't' going to be sufficient right

#

so it would be like O(N) or O(Nlogn)

real acorn Dec 18, 2023, 1:31 AM

#

likely not

wise flax Dec 18, 2023, 1:31 AM

#

right

real acorn Dec 18, 2023, 1:31 AM

#

you want something sub-quadratic

wise flax Dec 18, 2023, 1:31 AM

#

okay

#

what data structure do u think

#

i'm confused

real acorn Dec 18, 2023, 1:32 AM

#

But first, my focus would be on getting it correct

#

The data structure probably isn't the issue, but the algorithm itself

wise flax Dec 18, 2023, 1:32 AM

#

oh ok

#

can u take a look at it tell me what i should fix

#

ive been staring at this for the past 2 hours lol

real acorn Dec 18, 2023, 1:32 AM

#

ngl, your code is extremely hard to comprehend

wise flax Dec 18, 2023, 1:34 AM

#

real acorn ngl, your code is extremely hard to comprehend

ooops mb i cant rly explain code that well ;-;

real acorn Dec 18, 2023, 1:34 AM

#

don't write code you can't explain 😉

wise flax Dec 18, 2023, 1:35 AM

#

so its basically iterating through a map

real acorn Dec 18, 2023, 1:35 AM

#

but the reason your code is hard to leave it because of the lack of spacing, single letter variable names, etc

wise flax Dec 18, 2023, 1:36 AM

#

real acorn but the reason your code is hard to leave it because of the lack of spacing, sin...

ok

#

should i send it with it being reformatted

real acorn Dec 18, 2023, 1:36 AM

#

yeah, it's hard to read as it is

wise flax Dec 18, 2023, 1:39 AM

#

got it

#

too long so ill split it up into 2 messages

#

@real acorn

real acorn Dec 18, 2023, 1:47 AM

#

it's a lot of code, gotta chill and give me time to read and digest

#

also, doing a quick google search of your problem, looks like your classmates are trying in various places as well lol

wise flax Dec 18, 2023, 1:47 AM

#

lol

wise flax Dec 18, 2023, 1:47 AM

#

real acorn it's a lot of code, gotta chill and give me time to read and digest

alright my bad

real acorn Dec 18, 2023, 1:50 AM

#

can you come up with a minimal case that does not work?

wise flax Dec 18, 2023, 1:51 AM

#

real acorn can you come up with a minimal case that does not work?

yeah

#

my code works for 1-3

#

gets it wrong for 4-8, and times out for 9-13

real acorn Dec 18, 2023, 1:51 AM

#

No no no. A minimal test case.

wise flax Dec 18, 2023, 1:51 AM

#

so it only works when N<=2

real acorn Dec 18, 2023, 1:52 AM

#

Not the conditions it doesn't work under. A reproducing example where it doesn't work that is as small as possible

wise flax Dec 18, 2023, 1:54 AM

#

real acorn Not the conditions it doesn't work under. A reproducing example where it doesn't...

i don't think there's a simple test case where it doesn't work

real acorn Dec 18, 2023, 1:55 AM

#

make one

wise flax Dec 18, 2023, 1:56 AM

#

real acorn make one

i tried, but i can't find one
the sample test cases provided work
i checked some edge cases and they seem to work fine

#

i think it might be a problem with the time complexity

real acorn Dec 18, 2023, 1:56 AM

#

only the last 4 are tested for time complexity

wise flax Dec 18, 2023, 1:57 AM

#

real acorn only the last 4 are tested for time complexity

oh ok

real acorn Dec 18, 2023, 1:57 AM

#

that's what your description says, at least

wise flax Dec 18, 2023, 1:57 AM

#

but there doesn't seem to be any inherent issues with the code though

real acorn Dec 18, 2023, 1:57 AM

#

sure there is. it's getting a wrong answer

wise flax Dec 18, 2023, 1:58 AM

#

hmm

#

is it like an edge case

#

i cant think of anything

real acorn Dec 18, 2023, 1:58 AM

#

Maybe, hard to tell without an example that reproduces it

wise flax Dec 18, 2023, 1:58 AM

#

yeah like

#

i can't actually see which test cases fail

real acorn Dec 18, 2023, 1:58 AM

#

means it's time to make one that fails

wise flax Dec 18, 2023, 1:59 AM

#

ok ill try

marble gulch Dec 18, 2023, 2:04 AM

#

<@&847915341954154536> this is part of an ongoing copetition close asap

#

USACO Bronze

#

@wise flax I WILL report you

shadow aurora Dec 18, 2023, 2:05 AM

#

marble gulch <@&847915341954154536> this is part of an ongoing copetition close asap

We don’t do people’s work for them, rest assured

#

It looks like @real acorn has done a good job of guiding them without giving them the answer

wise flax Dec 18, 2023, 2:06 AM

#

yeah im just trying to work through the solution

marble gulch Dec 18, 2023, 2:06 AM

#

ah

#

ok but you csnt be asking about the question while the competition is going

#

ppl might see

#

its not rly a big deal cuz bronze but still

desert egret Dec 18, 2023, 2:07 AM

#

I'm not really sure it's reasonable for you to ask us to enforce that

marble gulch Dec 18, 2023, 2:07 AM

#

ik

#

sry i kinda over reacted

desert egret Dec 18, 2023, 2:07 AM

#

All good

wise flax Dec 18, 2023, 2:07 AM

#

yeah alr i just wanna know what's wrong with my code

marble gulch Dec 18, 2023, 2:07 AM

#

but if it were plat i would def do smthn

wise flax Dec 18, 2023, 2:07 AM

#

dw its just bronze lmao

marble gulch Dec 18, 2023, 2:08 AM

#

ikik

real acorn Dec 18, 2023, 2:08 AM

#

If the competition is ongoing, I will not be helping further, sorry

wise flax Dec 18, 2023, 2:09 AM

#

i finished the contest

#

i will send screenshot of proof

#

real acorn Dec 18, 2023, 2:09 AM

#

it's not just you, it's anyone else in that competition

#

no unfair advantages

wise flax Dec 18, 2023, 2:10 AM

#

real acorn it's not just you, it's anyone else in that competition

can u make this channel private or something

#

im j rly upset cuz i was just a few test cases off

real acorn Dec 18, 2023, 2:11 AM

#

No, I can't make private channels
I don't help in DMs, sorry

wise flax Dec 18, 2023, 2:11 AM

#

alright, sorry

#

i will delete everything to ensure competition security

gritty knotBOT Dec 18, 2023, 2:12 AM

#

@wise flax

Please Do Not Delete Posts!

Please don't delete forum posts. They can be helpful to refer to later and other members can learn from them. In the future you can use !solved to close a post and mark a post as solved.

stoic ore Dec 18, 2023, 2:12 AM

#

i don't think that's necessary

wise flax Dec 18, 2023, 2:12 AM

#

oh

#

can people still help?

stoic ore Dec 18, 2023, 2:13 AM

#

i mean that i don't think it's necessary for you to delete everything

wise flax Dec 18, 2023, 2:13 AM

#

yea but

#

i just dont want to risk competition security yk

stoic ore Dec 18, 2023, 2:13 AM

#

i don't think there are any relevant spoilers here

wise flax Dec 18, 2023, 2:13 AM

#

ok

real acorn Dec 18, 2023, 2:13 AM

#

Not here, but a working solution would be

wise flax Dec 18, 2023, 2:13 AM

#

yeah

stoic ore Dec 18, 2023, 2:14 AM

#

ofc

wise flax Dec 18, 2023, 2:14 AM

#

can i still get advice for implementaiton here

stoic ore Dec 18, 2023, 2:14 AM

#

ofc you can ask questions

#

we simply won't just write you a solution

#

that's all

real acorn Dec 18, 2023, 2:14 AM

#

and if you find a solution, we strongly advice you to not post the solution 😉

stoic ore Dec 18, 2023, 2:14 AM

#

yeah

wise flax Dec 18, 2023, 2:14 AM

#

okay

#

got it

#

kk i deleted some stuff so ill repost

stoic ore Dec 18, 2023, 2:15 AM

#

though the probability that anyone in that competition will find this thread in time to copy the code is pretty much 0 anyways

wise flax Dec 18, 2023, 2:15 AM

#

true

stoic ore Dec 18, 2023, 2:15 AM

#

but yeah, better not post a working solution

wise flax Dec 18, 2023, 2:16 AM

#

ok

#

my solution below is not working btw

#

only for first 3/13 tc

#

FJ is growing N (1 <= N <= 2*10^5) plants of asparagus on his farm! However some of his plants have genetic differences, so some plants will grow faster than others. The initial height of the i’th plant is h_i inches, and after each day, the ith plant grows by a_i inches.

FJ likes some of his plants more than others, and he wants some specific plants to be taller than others. He gives you an array of distinct values t_1,....,t_N containing all integers from 0 to N-1 and he wants the i’th plant to have exactly t_i other plants that are taller than it. Find the minimum number of days so that FJ’s request is satisfied, or determine that it is impossible.

#

Input format:
The first will contain of an integer T, denoting the number of independent test cases (1 <= T <= 10).
The first line of each test case contains of an integer N.
The second line consists of N integers h_i (1 <= h_i <= 10^9) denoting the initial height of the i’th plant in inches.
The third line consists of N integers a_i (1 <= a_i <= 10^9) denoting the number of inches the i’th plant grows each day.
The fourth line consists of N distinct integers t_i denoting the array that FJ gives you.
It is guaranteed that the sum of N over all test cases does not exceed 2*10^5.

Output format:
Output T lines, the answer to each test case on a different line. If it's not possible, output -1.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (eg. long long).

Sample input:
6
1
10
1
0
2
7 3
8 10
1 0
2
3 6
10 8
0 1
2
7 3
8 9
1 0
2
7 7
8 8
0 1
2
7 3
8 8
1 0

Sample output:
0
3
2
5
-1
-1

In the first sample input, there are 6 test cases.
In the first test case, there is only one plant, so the condition is satisfied on day 0.
In the second test case, we need the first plant to be shorter than the second plant. After day 1, the heights are 15 and 13. After day 2, the heights are both 23. After day 3, the heights are 31 and 33, and that’s the first day in which the condition is satisfied.
The third and fourth test cases are similar to the second.
In the fifth test case, both plants start with an initial height of 7 and a growth rate of 8. So they will always have identical heights, and therefore the condition is never satisfied.
In the sixth test case, the condition is not satisfied initially and the growth rates are the same. So the condition can never be satisfied.

Sample input:
2
5
7 4 1 10 12
3 4 5 2 1
2 1 0 3 4
5
4 10 12 7 1
3 1 1 4 5
2 4 3 1 0

Sample output:
4
7

#

In the second sample input, there are 2 test cases.
In the first test case, the final heights after day 4 are 19, 20, 21, 18, 16.
In the second test case, the final heights after day 7 are 25, 17, 19, 35, 36.

#

**
Scoring:
Inputs 1-3: N <= 2
Inputs 4-5: N <= 50 and a_i, h_i <= 10^3
Inputs 6-8: N <= 10^3
Inputs 9-13: No additional constraints**

#

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
using namespace std;

int main() {
    long long T;
    cin >> T;
    for (long long mc = 0; mc < T; mc++) {
        long long N;
        cin >> N;
        vector<long long> heights(N), growthRates(N), targets(N), currentCounts(N);
        for (long long i = 0; i < N; i++) {
            cin >> heights[i];
        }
        for (long long i = 0; i < N; i++) {
            cin >> growthRates[i];
        }
        for (long long i = 0; i < N; i++) {
            cin >> targets[i];
        }
        for (long long i = 0; i < N; i++) {
            currentCounts[i] = 0;
        }

        set<long long> timeStamps;
        map<long long, vector<long long>> increaseCounts, decreaseCounts;

        // Calculate the initial counts and potential changes in the future
        for (long long i = 0; i < N; i++) {
            for (long long j = 0; j < N; j++) {
                if (heights[i] > heights[j]) continue;
                if (heights[i] < heights[j]) {
                    currentCounts[i]++;
                    if (growthRates[i] > growthRates[j]) {
                        long long timeToOvertake = (long long)ceil((heights[j] - heights[i]) / (double)(growthRates[i] - growthRates[j]));
                        long long nextTime = (long long)((heights[j] - heights[i]) / (growthRates[i] - growthRates[j])) + 1;
                        decreaseCounts[timeToOvertake].push_back(i);
                        timeStamps.insert(timeToOvertake);
                        increaseCounts[nextTime].push_back(j);
                        timeStamps.insert(nextTime);
                    }
                } else if (growthRates[i] < growthRates[j]) {
                    increaseCounts[1].push_back(i);
                }
            }
        }

#

       // Check if initial condition is satisfied
        bool isSatisfied = true;
        for (long long i = 0; i < N; i++) {
            if (currentCounts[i] != targets[i]) {
                isSatisfied = false;
                break;
            }
        }
        if (isSatisfied) {
            cout << 0 << "\n";
            continue;
        }

        // Iterate over each timestamp to check if the condition is satisfied
        for (long long time : timeStamps) {
            isSatisfied = true;
            for (long long i : increaseCounts[time]) {
                currentCounts[i]++;
            }
            for (long long i : decreaseCounts[time]) {
                currentCounts[i]--;
            }
            for (long long i = 0; i < N; i++) {
                if (currentCounts[i] != targets[i]) {
                    isSatisfied = false;
                    break;
                }
            }
            if (isSatisfied) {
                cout << time << "\n";
                break;
            }
        }

        if (!isSatisfied) {
            cout << "-1\n";
        }
    }
    return 0;
}```

#

this is my code, it only works for the first 3 test cases and gets 4-8 incorrect, and times out for 9-13

#

any advice?

stoic ore Dec 18, 2023, 2:19 AM

#

i doubt anyone's gonna be bored enough to debug your code for you ^^

#

but we'll see

wise flax Dec 18, 2023, 2:19 AM

#

stoic ore i doubt anyone's gonna be bored enough to debug your code for you ^^

yeah the thing is

#

for every single case and edge case it works

#

and time complexity shouldnt really be an issue till test case 8

#

so i'm not sure what im particularly missing

stoic ore Dec 18, 2023, 2:21 AM

#

sry, i don't really have time to look into this, but you can ofc wait if someone else has

wise flax Dec 18, 2023, 2:22 AM

#

alright

#

if someon can help it would be greatly appreciated

#

like just something to start with looking at

marble gulch Dec 18, 2023, 2:25 AM

#

wise flax ```cpp // Check if initial condition is satisfied bool isSatisfie...

use ctsdint
makes code a bit cleaner

wise flax Dec 18, 2023, 2:26 AM

#

marble gulch use ctsdint makes code a bit cleaner

alright yeah

#

i can just use <bits/stdc++.h>

#

instead right?

marble gulch Dec 18, 2023, 2:26 AM

#

yes...
but I hope you know never to do that outside competitions

wise flax Dec 18, 2023, 2:27 AM

#

marble gulch yes... but I hope you know never to do that outside competitions

yeah of course

#

i was just referring to the part about making the code cleaner

marble gulch Dec 18, 2023, 2:27 AM

#

yes

wise flax Dec 18, 2023, 2:29 AM

#

marble gulch yes

kk

#

do you have any advice i should use

marble gulch Dec 18, 2023, 2:30 AM

#

didnt solve the problem in comp and haven't looked at it since

wise flax Dec 18, 2023, 2:31 AM

#

oh alr

#

if anyone can help advice would be greatly appreciated

marble gulch Dec 18, 2023, 2:34 AM

#

please dont ask for hlpe while the competition is ongoing

wise flax Dec 18, 2023, 2:35 AM

#

marble gulch please dont ask for hlpe while the competition is ongoing

pretty sure we discussed this before above

#

i also didn't make silver

wise flax Dec 18, 2023, 3:06 AM

#

!solved

#C++ Logic Implementation Help - program timing out