kattis ICPC tutorial c++

TheJast (42)
so i'm working on the kattis problem ICPC tutorial for my cs3 class but since everythings online now i dont really have anyone to ask. but i can't for the life of me figure out why it's accepting only 10/16 test cases i've been going through them for hours and every time i try to change things i get more test cases wrong so i dont know which of my switch cases is the problem. any help would be much appreciated. my 2nd and 3rd asserts also fail but i'm less concerned about those. thank you in advance.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cassert>

using namespace std;

int mainSwitch();
//string testSwitch(int, int, int);
//void test();

int main()
{
	mainSwitch();
	//test();
	return 0;
}

int mainSwitch()
{
	int m, n, t;
	cin >> m >> n >> t;
	int temp = n;
	int factorial = 1;
	switch (t)
	{
	case 1:
		for (int i = n; i > 0; i--)  
		{
			if (factorial > m)
			{
				cout << "TLE" << endl;
				return 0;
			}
			factorial *= i;
		}
		//cout << factorial << endl;
		break;

	case 2:
		for (int i = 1; i < n; i++)
		{
			temp *= n;
			if (temp > m)
			{
				cout << "TLE" << endl;
				return 0;
			}
		}
		cout << temp << endl;
		break;

	case 3:
		for (int i = 1; i < 4; i++)
		{
			temp *= n;
			if (temp > m)
			{
				cout << "TLE" << endl;
				return 0;
			}
		}
		break;

	case 4:
		for (int i = 1; i < 3; i++)
		{
			temp *= n;
			if (temp > m)
			{
				cout << "TLE" << endl;
				return 0;
			}
		}
		break;

	case 5:
		for (int i = 1; i < 2; i++)
		{
			temp *= n;
			if (temp > m)
			{
				cout << "TLE" << endl;
				return 0;
			}
		}
		break;
	case 6:
		if ((n * log2(n)) > m)
		{
			cout << "TLE" << endl;
			return 0;
		}
		break;

	case 7:
		if (n > m)
		{
			cout << "TLE" << endl;
			return 0;
		}
		break;
	}
	cout << "AC" << endl;
}

string testSwitch(int x, int y, int z)
{
	int temp = y;
	int factorial = 1;
	string ans;
	switch (z)
	{
	case 1:
		for (int i = y; i > 0; i--)
		{
			if (factorial > x)
			{
				ans = "TLE";
				
			}
			factorial *= i;
		}
		break;

	case 2:
		for (int i = 1; i < y; i++)
		{
			temp *= y;
			if (temp > x)
			{
				ans = "TLE";
				
			}
		}
		break;

	case 3:
		for (int i = 1; i < 4; i++)
		{
			temp *= y;
			if (temp > x)
			{
				ans = "TLE";
				
			}
		}
		break;

	case 4:
		for (int i = 1; i < 3; i++)
		{
			temp *= y;
			if (temp > x)
			{
				ans = "TLE";
				
			}
		}
		break;

	case 5:
		for (int i = 1; i < 2; i++)
		{
			temp *= y;
			if (temp > x)
			{
				ans = "TLE";
				
			}
		}
		break;
	case 6:
		if ((y * log2(y)) > x)
		{
			ans = "TLE";
			
		}
		break;

	case 7:
		if (y > x)
		{
			ans = "TLE";
		
		}
		break;
		ans = "AC";
	}
	
	return ans;
}

void test()
{
	int x, y1, y2, y3, z1, z2, z3;
	x = 100000000;
	y1 = 75;
	y2 = 750;
	y3 = 1500;
	z1 = 1;
	z2 = 6;
	z3 = 4;
	assert(testSwitch(x, y1, z1) == "TLE");
	assert(testSwitch(x, y2, z2) == "AC");
	assert(testSwitch(x, y3, z3) == "AC");
	cout << "all tests passed" << endl;
}
lastchance (6980)
so i'm working on the kattis problem ICPC tutorial

Maybe you are ... but I don't think anyone else is ... so perhaps you could tell us what the "kattis problem ICPC tutorial" actually is.

It would also help if you removed all the code that is NOT being used, so people can avoid having to hunt through irrelevant material.


Be aware that factorials get very large very fast and will soon exceed the capacity of an int.
Last edited on
Handy Andy (5051)
Hello TheJast,

Here is another tutorial for you.

Give your variables a proper name and not a single letter that only you know what it means. This is mostly for your benefit, but is does help others who read your code because they do not have to waste time trying to figure out what some of the variables mean.

In your code:
1
2
3
4
 
int mainSwitch()
{
	int m, n, t;
	cin >> m >> n >> t;

This works until someone runs the program and does not have access to the code to see what needs to be entered. You know what to enter because you wrote the program, but no one else does. You need a prompt before the "cin" to let the user know what to enter and how to enter it.

A few blank lines also helps. As an example:
1
2
3
4
5
6
7
 
int mainSwitch()
{
	int m, n, t;
	cin >> m >> n >> t;
	int temp = n;
	int factorial = 1;
	switch (t)


But easier to read as:
1
2
3
4
5
6
7
8
9
10
11
12
 
int mainSwitch()
{
	int m, n, t;

        //  <--- Needs a prompt.
	cin >> m >> n >> t;

	int temp = n;

	int factorial = 1;

	switch (t)


One last point. With the lines:
1
2
 
        //  <--- Needs a prompt.
	cin >> m >> n >> t;

Provide numbers that work and shat the expected output should be. Then for the problem numbers show what does not work.

Something to work on while i get the program loaded and see what happens.

Andy
TheJast (42)
Thank you, here's a link to the kattis problem https://open.kattis.com/problems/tutorial
I would normally use variables with better names, but the teacher who assigned it specifically said to use the variables from the problem. i understand why that could be confusing though. i normally get to go to the tutoring center and can explain what the variables are. but for future posts i'll make changes before posting. thank guys for the help. i really appreciate it.
TheJast (42)
m is the number of operations the computer makes in one second n is the number of operations in big o algorithm and t is which case in the switch it is. it's supposed to measure whether or not o(n) operations would exceed the time limit doing m actions for each case (t).
lastchance (6980)
All you have to do is decide if
ft(n) <= m
where ft is whatever function corresponds to type t in the table in your link. If true you output "AC", if not you write "TLE".

That's it!

No assert statements ... just answer the question by writing one of those two things.

Please:
- vastly simplify your code to remove all the stuff that you aren't using;
- remove the "assert" statements - they are completely irrelevant.
TheJast (42)
thank you i'll try to look at it from that perspective. i have to keep the 3 asserts, it's a requirement for the class not the kattis problem. they're worth 30 % of the programs total grade.
ne555 (10692)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
int main(){
	int m, n, t;
	cin >> m >> n >> t;
	if (under_limit(m, n, t))
		cout << "AC\n";
	else
		cout << "TLE\n";
}

bool under_limit(int limit, int n, int type){
	switch(type){
		case 1:
			return factorial(limit, n);
		case 2:
			return exp2_to_n(limit, n);
		case 3:
			return power(limit, n, 4);
		case 4:
			return power(limit, n, 3);
		case 5:
			return power(limit, n, 2);
		case 6:
			return nlgn(limit, n);
		case 7:
			return constant(limit, n);
	}
}
use that skeleton, it will be easier to analyse each case separately
be careful with overflow and rounding


¿what's the difference between mainSwith() and testSwitch()?
Last edited on
TheJast (42)
the testSwitch just doesn't have a cin for my asserts. it might not be perfect, i've been trying to teach myself cassert my cs2 class didn't teach asserts and my cs3 teacher expects them on everything but didn't teach them. I can't figure out how to run my asserts through my main switch with the cin.
lastchance (6980)
The assert statements are just to check specific answers.

Ignore them to start with - they are irrelevant to the actual problem. You can soon see whether your code outputs TLE or AC, can't you? You can put assert statements in - if you really have to - once everything is working.
TheJast (42)
i did that, i did all of the switch originally in main, it all seems like it's working it out puts correctly. i was cout'ing the values to check them and they were correct. but when i run it through kattis it gets stuck on test case 11 but doesn't tell me what that is so i dont know where the problem is. everything i've tried to change has made me fail earlier in the kattis test cases. atleast one of my switch cases is wrong but i can't find it. after i spent the last few days trying to trouble shoot that i gave up and made my asserts so that i'd atleast get partial credit for them. posting on here was something i did as a last ditch effort to figure it out. my programs due in a few hours.
lastchance (6980)
Well, looking at mainswitch() (no idea whether testswitch() is different):
- case 1 would give you n * n!, not n!
- case 2 would give you nn, not 2n
etc.

Why don't you check by hand?
TheJast (42)
i think it has to be my switch case 2 thats wrong. but when i change it i get wrong answers on kattis earlier. i feel like it should be pow(2, n) that outputs the correct value but kattis seems to think it's wrong.
TheJast (42)
case 1 is correct for factorials i think factorial 10 is 3628800, and that what i get when i cout the value. i've changed case 2 got rid of the for loop and just made it 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
switch (t)
	{
	case 1:
		for (int i = n; i > 0; i--) 
		{
			if (factorial > m)
			{
				cout << "TLE" << endl;
				return 0;
			}
			factorial *= i;
		}
		break;

	case 2:
			temp = pow(2, n);
			if (temp > m)
			{
				cout << "TLE" << endl;
				return 0;
			}
		break;


which i is outputting the correct value but immedietly fails kattis
lastchance (6980)
Many of these calculations are likely to overflow an int. You should take steps to avoid that.

For example,
2n > m
if and only if
n log 2 > log m
but the latter is considerably less likely to overflow.
TheJast (42)
Thank you for all the help everyone, i solved it. i really appreciate everyone who took the time to assist, seeing it from all the different ways you guys looked at it helped me find the problem, or problems as there were more than a couple.

final code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
 
/*

This program is designed to test big O algorithms and see if when O(n) actions are taken will it exceed the maximum amount of actions
the computer can make in one second m depending on which algorithm you use t.
*/

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cassert>

using namespace std;

string testSwitch(int, int, int);
void test();

int main()
{
	test();
	int m, n, t;
	cin >> m >> n >> t;
	int temp = n;
	int factorial = 1;
	switch (t)
	{
	case 1:
		for (int i = n; i > 0; i--)
		{
			if (factorial > m)
			{
				cout << "TLE" << endl;
				return 0;
			}
			factorial *= i;
		}
		break;

	case 2:
			if (pow(2,n) > m)
			{
				cout << "TLE" << endl;
				return 0;
			}
		
		break;

	case 3:
		if (pow(n, 4) > m)
			{
				cout << "TLE" << endl;
				return 0;
			}
		
		break;

	case 4:
		if (pow(n, 3) > m)
			{
				cout << "TLE" << endl;
				return 0;
			}
		
		break;

	case 5:
		if (pow(n, 2) > m)
			{
				cout << "TLE" << endl;
				return 0;
			}
		
		break;
	case 6:
		if ((n * log2(n)) > m)
		{
			cout << "TLE" << endl;
			return 0;
		}
		break;

	case 7:
		if (n > m)
		{
			cout << "TLE" << endl;
			return 0;
		}
		break;
	}
	cout << "AC" << endl;
	return 0;
}

string testSwitch(int x, int y, int z)
{
	int factorial = 1;
	string ans = "AC";
	switch (z)
	{
	case 1:
		for (int i = y; i > 0; i--)
		{
			if (factorial > x)
			{
				ans = "TLE";
				
			}
			factorial *= i;
		}
		break;

	case 2:
		if (pow(2, y) > x)
		{
			ans = "TLE";
			
		}

		break;

	case 3:
		if (pow(y, 4) > x)
		{
			ans = "TLE";
			
		}

		break;

	case 4:
		if (pow(y, 3) > x)
		{
			ans = "TLE";
			
		}

		break;

	case 5:
		if (pow(y, 2) > x)
		{
			ans = "TLE";
			
		}

		break;
	case 6:
		if ((y * log2(y)) > x)
		{
			ans = "TLE";
		
		}
		break;

	case 7:
		if (y > x)
		{
			ans = "TLE";
			
		}
		break;
	}
	
	return ans;
}

void test()
{
	int x, y1, y2, y3, z1, z2, z3;
	x = 100000000;
	y1 = 31;
	y2 = 750;
	y3 = 1500;
	z1 = 2;
	z2 = 6;
	z3 = 4;
	assert(testSwitch(x, y1, z1) == "TLE");
	assert(testSwitch(x, y2, z2) == "AC");
	assert(testSwitch(x, y3, z3) == "TLE");
	cout << "all tests passed" << endl;
}
Topic archived. No new replies allowed.