Kattis Problem with Algorithm Analysis Issue

PiggiesGoSqueal (167)
Hello everyone! I'm trying to solve this problem:
https://open.kattis.com/problems/tutorial

And I got it to work with all the test cases provided by kattis as a download on that link. However, when I try to submit it then it doesn't work and I can't figure out why.

I would greatly appreciate some help to figure out what I'm doing wrong.

Please Note: This is for a homework assignment, however, by the time I figure out the issue it will have been already due so this is for learning rather than for points.

Thanks!

Code: https://pastebin.com/YpbAG90x
Trying to submit it to kattis:
https://gyazo.com/d63f6b77488e140593b6da2c6e5dc620

Please Note: While I'll try to reply within 24 hours, it may take me a few days to reply depending how busy I am. Thanks for understanding!
Last edited on
ne555 (10692)
> I got it to work with all the test cases provided by kattis as a download on that link.
your code has a comment that says «CASE 6 AND ONLY CASE 6 FAILS. Using test 5.in and 5.ans»
¿so does it work or not?

> what I'm doing wrong.
it's probably an issue with precision total <= maxOperations
`total' is a `double', try with integer arithmetic
you'll need to create your own `pow()' and `log2()' functions for that, be careful with overflow
also, you should probably interrupt the n! and 2^n functions when then exceed 1e9

1
2
 
            total = std::log2(num);
            total *= num;
«nine friends want to do a trip, ¿how many motorcycles do they need?» the answer is 5, not 4.5

apart from that
1
2
 
        std::cin >> m >> n >> t;
        // ^ max num of operations, num that must pass in algorithm, max seconds for time limit
if `m', `n' and `t' are not descriptive names so you feel the need of that comment, ¿why don't simply change the name of the variables?

> solve for O(n) (constant)
O(n) is lineal
O(1) is constant
Last edited on
PiggiesGoSqueal (167)
Thanks for the reply ne555!

ne555 wrote:
your code has a comment that says «CASE 6 AND ONLY CASE 6 FAILS. Using test 5.in and 5.ans»
¿so does it work or not?

Apologies, sometimes I forget to update my comments. All test cases do pass with the current code. The issue that caused it to not pass originally was because total was an int not a double which changed the answer in the calculation of total in case 6 of the switch statement.

Also, I don't understand what you mean for your suggested solution. :/ I spent an hour trying to figure it out and still haven't, just lots of assert() failures. I tried finding powers using my own code instead of std::pow() but that caused assert cases to fail. For example:
1
2
3
4
5
6
7
8
9
10
11
12
 
        // if typeOfAlgoUsed == 3 on kattis graph, then O(n^4):
        case 3: 
            //total = std::pow(num, 4);
            
            total = num;
            for (int numOfPowersToGo = 4; numOfPowersToGo > 0; --numOfPowersToGo) {
                total *= num;
                std::cout << total << '\n';
            }
            
            
            break;

Then ran "./a.out test" and it gave the output:
9
27
81
243 (idk why it repeats)
9
27
81
243
a.out: icpc2.cpp:236: void test(): Assertion `solve(81, 3, 3) == "AC"' failed.


I also tried making my own solution for log without using double data types. That didn't work either:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
        // if typeOfAlgoUsed == 6 on kattis graph, then O( n logb2(n) ):
        case 6: {
            // To Find log base 2 (n) example: log(32) --> 32/2 = 16/2 = 8/2 = 4/2 = 2/2 = 1 --> so log(32) = 5 b/c 5 divisions to get to 1.
            // Then multiply by n for nlog(n) with base as 2. However, C++ comes with a log2() function.
            //total = std::log2(num);
            //total *= num;
            unsigned long int tempNum = num;
            int count = 0;
            while (tempNum > 1) {
                tempNum /= 2;
                ++count;
                std::cout << "tempNum = tempNum / 2 --> " << tempNum << '\n';
                std::cout << "count = " << count << "\n";
            }

            total = num * count;
            std::cout << "total = " << total << "\n\n";
            break;
        }


$ ./a.out test
tempNum = tempNum / 2 --> 2
count = 1
tempNum = tempNum / 2 --> 1
count = 2
total = 8

tempNum = tempNum / 2 --> 2
count = 1
tempNum = tempNum / 2 --> 1
count = 2
total = 8

tempNum = tempNum / 2 --> 500000
count = 1
tempNum = tempNum / 2 --> 250000
count = 2
tempNum = tempNum / 2 --> 125000
count = 3
tempNum = tempNum / 2 --> 62500
count = 4
tempNum = tempNum / 2 --> 31250
count = 5
tempNum = tempNum / 2 --> 15625
count = 6
tempNum = tempNum / 2 --> 7812
count = 7
tempNum = tempNum / 2 --> 3906
count = 8
tempNum = tempNum / 2 --> 1953
count = 9
tempNum = tempNum / 2 --> 976
count = 10
tempNum = tempNum / 2 --> 488
count = 11
tempNum = tempNum / 2 --> 244
count = 12
tempNum = tempNum / 2 --> 122
count = 13
tempNum = tempNum / 2 --> 61
count = 14
tempNum = tempNum / 2 --> 30
count = 15
tempNum = tempNum / 2 --> 15
count = 16
tempNum = tempNum / 2 --> 7
count = 17
tempNum = tempNum / 2 --> 3
count = 18
tempNum = tempNum / 2 --> 1
count = 19
total = 19000000

a.out: icpc2.cpp:251: void test(): Assertion `solve(19931568, 1000000, 6) == "TLE"' failed.
Aborted (core dumped)


ne555 wrote:
«nine friends want to do a trip, ¿how many motorcycles do they need?» the answer is 5, not 4.5

In line 194 of my original code (https://pastebin.com/YpbAG90x) I tried a solution with the same thought process but it didn't fix the issue when submitting it to Kattis. I would convert it to int before comparing it to maxOperations.

ne555 wrote:
also, you should probably interrupt the n! and 2^n functions when then exceed 1e9

Putting this part on hold until we figure out the log & power issues. (Mainly a note to self).

ne555 wrote:
if `m', `n' and `t' are not descriptive names so you feel the need of that comment, ¿why don't simply change the name of the variables?

Done. :)

ne555 wrote:
> solve for O(n) (constant)
O(n) is lineal
O(1) is constant

Oh.. Well, I think my code is still correct right? Even if it wasn't a constant:
1
2
3
4
 
        // if typeOfAlgoUsed == 7 on kattis graph, then O(n):
        case 7:
            total = num;
            break;



Edit: Latest code is: https://pastebin.com/hbux9Kwv
Note to Self: This code is in icpc2.cpp
Last edited on
ne555 (10692)
I was wrong, you shouldn't use integer arithmetic for the lg(n) part
the idea is to obtain ceil(n lg n), but with you comparison total <= maxOperations that's already take care of

Also, run some tests and the precision of `double' seems good enough in the range that you need
so you may keep double total and use cmath functions


now, looking at your last code you have
1
2
3
4
5
 
            total = num;
            for (int numOfPowersToGo = 4; numOfPowersToGo > 0; --numOfPowersToGo) { //this executes 4 times
                total *= num;
                std::cout << total << '\n';
            }
you are doing n^5 there
start with total = 1

you make the same mistake with the 2^n part
1
2
3
4
5
 
		total = 2;
		// for each num in n, multiply original2Num by 2:
		for(unsigned int i = 1; i <= num; ++i) {
			total *= 2;
		}
you are computing 2^(n+1)
which makes me wonder who gived you the testcases
1
2
3
 
	// For Algo Type 2:
	assert(solve(10, 3, 2) == "TLE"); //2^3 = 8, this should be "AC"
	assert(solve(16, 3, 2) == "AC");

there is function exp2() for that.


> also, you should probably interrupt the n! and 2^n functions when then exceed 1e9
>> Putting this part on hold until we figure out the log & power issues. (Mainly a note to self).
you are doing a loop on the factorial, your code will take too much time to compute 1000000000!
jonnin (11437)
not critical, but consider making friends with lookup tables.
2^n for integer ns ... the table is only going to be 64 entries or less most likely.
n! ... same, a few entries gives the answer assuming you are not using big int objects (?).
looping/computing stuff like this is inefficient.

2 is kind of magic as our computers are based of binary, powers of 2, etc.

consider powers again.. the exponent's bits tell you how to group the multiplications to do less work. It turns out that looping is just as good, but seeing this may help you think about other bits of what you are doing from another angle. See how it uses powers of 2 to do 2^64 in only 13 multiplies (if I counted right)? It looks at the bit and multiples the answer by 1 (doing nothing) when its zero and by the correct (x, x*x, x^4, x^8, ...) power when its 1. Anywhere you are using powers or multiply/divide by 2 specifically, there are often some tricks you can pull, and for integer powers, and many other places... I know this is schoolwork, but it seems like advanced schoolwork, so I am just tossing out things to think about that may help get it finished. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
inline long long ipow(long long p, unsigned long long e) //fast for big powers (> 8)
{ 
  const long long one = 1;
  const long long *lut[2] = {&p,&one};
  register long long result = 1;
    result *= lut[!(e&1)][0]; p *= p;
	result *= lut[!(e&2)][0]; p *= p;
	result *= lut[!(e&4)][0]; p *= p;
	result *= lut[!(e&8)][0]; p *= p;
	result *= lut[!(e&16)][0]; p *= p;
	result *= lut[!(e&32)][0]; p *= p;
	result *= lut[!(e&64)][0]; 	
	return result;
}

Last edited on
Topic archived. No new replies allowed.