integer

integer

This is a nice problem! I can see this really putting good use on multithreaded techniques.Can we assume the input integers are strictly positive and less than (2^31)-1?
And is there an upper bound on the size of a potential tiling set?

18 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

Quoting mdma
This is a nice problem! I can see this really putting good use on multithreaded techniques.Can we assume the input integers are strictly positive and less than (2^31)-1?
And is there an upper bound on the size of a potential tiling set?

...and also the maximum number of input sets and/or a maximum size of the input file? 

Yes, the input integers would be postive values and problem size would be upper bound by an unsigned 32-bit integer.

Thanks
-Rama

An unsigned integer? That's going to be difficult for languages without unsigned support. In Java, I will have to use the next largest type, which is a 64-bit long.I was hoping for (2^31)-1 as the upper bound - a signed integer.

Hi,
No problem. Go ahead and used signed integer and 64-bit. But note that the input integers would be positive.

Thanks
-Rama

We'll, that puts me and anyone using signed types at considerable disadvantage having to use a 64-bit type while others can use 32-bit type. Can we simply set the largest integer to be 2^31-1, so that I can use a signed 32-bit type to represent rectangle dimensions?
Also, will the width/height and/or area of a rectangle fit within a signed 32-bit value?

Hi,
For this problem statement, we don't anticipate that the dimensions would be larger than a 32-bit unsigned value. So, you can stick to that assumption. I don't see the necessity of using a signed 32-bit value. Feel free to code as you deem necessary and best. The largest rectangle dimension wouldn't be more than 32-bit signed integer. I hope this info helps and clarifies this post.

Thanks
-Rama

"The largest rectangle dimension wouldn't be more than 32-bit signed integer"Thanks, that's what I needed to hear!The difference is significant.If you say that the largest size is 232-1 (largest value for a unsigned 32-bit value) then coders using languages with only signed types have to use a larger type.If you say the largest size is 231-1 then languages where only signed types are available can also compete.Thanks,mat.

Quoting mdma
This is a nice problem! I can see this really putting good use on multithreaded techniques.

Humm... Isn't it going to be IO bound?

All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
http://www.1024cores.net

Thank you. This range is very clear

写字楼里写字间,写字间里程序员
程序人员写程序,又拿程序换酒钱
酒醒只在网上坐,酒醉还来网下眠
酒醉酒醒日复日,网上网下年复年

Quoting Dmitriy Vyukov

Quoting mdma
This is a nice problem! I can see this really putting good use on multithreaded techniques.

Humm... Isn't it going to be IO bound?

I seriously doubt it. Unless there is some short-cut, finding all valid encodings is a O(2^n) time algorithm.

Quoting mdma

Quoting Dmitriy Vyukov

Quoting mdma
This is a nice problem! I can see this really putting good use on multithreaded techniques.

Humm... Isn't it going to be IO bound?

I seriously doubt it. Unless there is some short-cut, finding all valid encodings is a O(2^n) time algorithm.

Can you please elaborate where you can find so many options to get the exponential time?
There are at most n possible widths of rectangle and when the dimensions are set 
the encoding validity test seems to take an order of O(n) operations:
the location of the upper-left corner of every consequent square 
starting with the first one is determined uniquely by all squares placed before that,
so they are placed into the rectangle, one by one, if they fit the rest of free space.
The very first one that will not fit means that the set is not suitable for this rectangle
- there is no way to undo a placement and try the other one.
Thus at very maximum O(n^2) time in total. Or am I missing something?

Quoting gk4v07
Can you please elaborate where you can find so many options to get the exponential time?

All possible splittings of a sequence?

All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
http://www.1024cores.net

Quoting Dmitriy Vyukov

Quoting gk4v07
Can you please elaborate where you can find so many options to get the exponential time?

All possible splittings of a sequence?

Yes, but we don't need to check them all - 
if the first k squares don't fit the width of rectangle 
we can drop the rest, and the same is true for the next "row" to fill.

Quoting Dmitriy Vyukov

Quoting gk4v07
Can you please elaborate where you can find so many options to get the exponential time?

All possible splittings of a sequence?

That's what I was thinking - number pf partitions of a set/sequence.

It's just a casual guess - I've not though much about the algorithm, so a shortcut (such as discarding many improbable solutions) might reduce this to polynomial time. But I'd be surprised if it becomes I/O bound..but then it might...wel'll just have to code and see!

Computational complexity tend to be O(record_count*record_number_count), which is O(total_number_count), that is, computational complexity is linear relative to input size. So it's indeed IO bound. The good news is that target machines are able to cache dozens of GB in memory.

All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
http://www.1024cores.net

You're right - I've sketched an algorithm and it's not exponential. Although it's not linear either - there are multiple solutions for each input, so isn't it quadratic worst case?

I believe there are some corner cases that yield quadratic complexity.

All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
http://www.1024cores.net

Leave a Comment

Please sign in to add a comment. Not a member? Join today