quest/wrong

[MattC98]

i have this quest : https://csacademy.com/contest/round-76/task/candy-boxes/
why is this code wrong?

#include <iostream>

using namespace std;

const int MAXN = 100005;

int v[MAXN], x[MAXN], aux[MAXN], s[MAXN];

int main()
{
int n, t, i, minim, poz, j;
cin >> n >> t;
for (i = 1; i <= n; ++i)
{
cin >> aux[i];
s[i] = aux[i];
}
for (i = 1; i <= t; ++i)
{
cin >> v[i];
if (v[i] == 1) cin >> x[i];
}
for (i = 1; i <= t; ++i)
{
if (v[i] == 1)
{
--aux[x[i]];
}
else
{
for (j = 1; j <= n; ++j) s[j] = aux[j];
for (j = i + 1; j <= t; ++j)
{
if (v[j] == 2) break;
if (v[j] == 1)
{
--s[x[j]];
}
}
minim = 20000000;
for (j = 1; j <= n; ++j)
{
if (s[j] < minim)
{
minim = s[j];
poz = j;
}
}
++aux[poz];
cout << poz << '\n';
}
}
return 0;
}

[doug4]

First, please use code tags. Edit your previous post, highlight the code, and click the Format button that looks like "<>". This will insert tags that make your code look prettier and make it easier for us to comment on. And if you use code tags, the page will give us a link to compile and run your program.

why is this code wrong?

Why don't you tell us what it is doing incorrectly?

Make it easier for us to help you. Posting a link to a question and some poorly formatted code with the question "why is this code wrong?" makes it difficult for VOLUNTEERS who have other jobs to want to dive into your code to figure out what is wrong, much less how to fix it.

More detail in your question, please.

[MattC98]

you dont help, anyone else?

[Ganado]

Do not abuse the report function, doug4 is not breaking any rules. You should format your code in your OP, edit it and put [code] and [/code] around your code. This helps people read and run your code; the more effort you put in your post, the more effort people will respond with.

You ask why it's wrong, but you don't say how it's wrong or provide more detail. Many of the people here are glad to help, but learning how to ask a good question will bring you much more success than just saying "tell me what's wrong".

[dhayden]

MattC98, please also explain how your code is supposed to work. In other words, what is your algorithm for solving this problem? It's possible that the algorithm is valid and your implementation is bad, but it's also possible that your algorithm is bad to begin with. With problems like this, coming up with the right algorithm can be harder than writing the code..

[MattC98]

First of all its my decision how I make the post, I tried formatting the source like 100 times and it doesnt work, and second of all , the quest is clear because I left a link to it and my code is super short so its easy to read, but i guess

[dhayden]

I just coded up a solution that uses just one array (to represent number of candies in each of the N boxes). There are no nested loops.

[tpb]

I just coded up a solution that uses just one array

Who in their right mind would use more than one array???

[doug4]

I tried formatting the source like 100 times and it doesnt work,

Which is why 2 of us described how to edit your post and make the formatting nicer.

second of all , the quest is clear because I left a link to it and my code is super short so its easy to read,

I run the risk of getting reported again, but I will consider the source.

Your code may be super short, but because it's not formatted (and we gave you instructions on how to do that, but they remain unheeded), it's difficult to read and understand, despite your claims to the contrary.

But most importantly, all you asked why it was wrong. Tells us what results your are getting and what you expect, and it will give us a hint as to where to look. I have enough haystacks to look for needles in here at work--I don't need to add more haystacks here.

[dhayden]

Who in their right mind would use more than one array???

Well, the OP uses four.

[dhayden]

tl;dr: Your algorithm is faulty.

Matt, I don't want you to have a bad experience on this site. Here is your code, formatted and with my comments on how it seems to work:

#include <iostream>

using namespace std;

const int MAXN = 100005;

// s[] temporary to store #candies in bins
// v[i] is event number i
// x[i] is bin number to remove from on event i
// aux[] is current count of candies in bins.
int v[MAXN], x[MAXN], aux[MAXN], s[MAXN];

int
main()
{
    int n, t, i, minim, poz, j;

    // Read the whole input
    cin >> n >> t;		// N and T
    for (i = 1; i <= n; ++i) {	// Get initial count of candies in bins
	cin >> aux[i];
	s[i] = aux[i];
    }
    for (i = 1; i <= t; ++i) {	// read T events
	cin >> v[i];
	if (v[i] == 1)		// If event==1, read the bin to pick from
	    cin >> x[i];
    }

    // Now run the algorithm. Each time we see an event #2, we read
    // forward to the next event 2, tracking the bin counts in s[].
    // Once we find a future event 2, we find the bin that will have
    // the fewest candies at that time. We'll put the current candy
    // into that bin.
    for (i = 1; i <= t; ++i) {
	if (v[i] == 1) {
	    --aux[x[i]];
	} else {
	    // set s to current counts
	    for (j = 1; j <= n; ++j)
		s[j] = aux[j];
	    // Go forward looking for the NEXT "put" (event 2)
	    // keep track of how much will be in bins until then
	    // in s[]
	    for (j = i + 1; j <= t; ++j) {
		if (v[j] == 2)
		    break;
		if (v[j] == 1) {
		    --s[x[j]];
		}
	    }
	    // Find the bin with the fewest candies
	    minim = 20000000;
	    for (j = 1; j <= n; ++j) {
		if (s[j] < minim) {
		    minim = s[j];
		    poz = j;
		}
	    }
	    // put the current candy in that bin.
	    ++aux[poz];
	    cout << poz << '\n';
	}
    }
    return 0;
}

My comments on lines 30-34 describe your algorithm as best I can figure it. Your program works for each of the sample inputs on the website you posted in the OP.

To make sure you came up with a valid solution, I added the following after line 37:

if (aux[x[i]] < 0) {
    cout << "Event " << i << " picks from empty bin #" << x[i] << '\n';
}

Your code fails in the following input:

2 11
1 1
2
2
1 2
1 2
1 2
2
1 2
2
1 1
1 1
2

Here the first 2 "puts" have to go into bin #2. But you won't know that until you see that you're taking 2 candies from bin #2 right at the beginning.

Here's a hint: You may have to print the bins for each event type 2 in order, but that doesn't mean that you have to determine the bin when you process the event. Why not hold onto the candy until you know where it must go (because you attempt to pick from an empty bin)?