15 Replies
⌛
This post has been reserved for your question.
Hey @Lantanggamer! Please useTIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here./close
or theClose Post
button above when your problem is solved. Please remember to follow the help guidelines. This post will be automatically marked as dormant after 300 minutes of inactivity.
I am doing a problem on DMOJ: https://dmoj.ca/problem/ccc15s2
ive been trying to figure out why its slow but I am unable to get to a solution
💤
Post marked as dormant
This post has been inactive for over 300 minutes, thus, it has been archived.
If your question was not answered yet, feel free to re-open this post or create a new one.
In case your post is not getting any attention, you can try to use /help ping
.
Warning: abusing this will result in moderative actions taken against you.
.
what are the current times vs how fast do you want it to be
The last case is over 5 seconds
It needs to be under
Here’s the test cases
hmmmmmmmmmmmmm
i think you can simplify the code
and maybe make it faster
put all the jerseys in 1 hashmap
and all the requirements in another hashmap
and then you could loop over the players requirements table
looking for the size and number
and check in the other hashmap if its available
if its available you set the value of the jersey to taken or however you want it
and then you add +1 to the possibilities
this could be quite fast cuz you can just check
Wouldn’t that pretty much be the same as my code but using hashmap instead of ArrayList?
i think it would be less operations
and only two loops to check the possibilities instead of 3 that you have
It will have more bytecode/processing overhead.
Maps and lists only get faster when you get into really large sets of data
Largely due to the boxing/unboxing that lists and maps necessitate as opposed to sticking with primatives
Speed & Efficiency:
Arrays & Primitives are super fast because they store data in a contiguous block of memory. This means quick access and better cache performance.
HashMaps & Lists have extra layers (like hashing or node traversal) which add overhead and can slow things down.
Memory Usage:
Arrays use less memory since they hold data directly.
Collections like HashMaps often use wrapper objects (e.g., Integer vs. int), which take up more space and can lead to autoboxing/unboxing overhead.
Access & Operations:
Arrays offer constant-time access with simple indexing.
HashMaps require computing hash codes and handling collisions, while Lists (especially linked lists) might need to traverse elements, making operations slower.
CPU & Optimization:
Arrays benefit from better cache locality and allow the JVM’s JIT compiler to optimize code more effectively.
HashMaps & Lists have less predictable memory access patterns, leading to cache misses and fewer optimization opportunities.
Garbage Collection:
Collections generate more temporary objects, increasing the garbage collector’s workload and potentially impacting performance.
Arrays & Primitives are more lightweight, putting less strain on the GC.
.
So to optimise this, I'd recommend to rewrite it in a way that uses primatives and Arrays. Stear clear of boxing/unboxing as much as possible.
I'd say primitives vs arrays is probably not the issue here - more like that most of the code seems to do a lot of unnecessary stuff
like having arrays of singleton lists for counts
there are up to 10 to the power of 6 - as mentioned by ayylmao, your best chances are with a proper mapping from jersey numbers to information on what is available for that number
and then you can iterate through all requests once and obtain the availability information for the jersey number and only check 3 values (S/M/L) per iteration - always using the smallest jersey possible
or just use an array or list to store the sizes for each jersey number since you only have one
and then process it request by request obtaining the jersey for any given number
also fix your variable names
Yeah I was more responding to the suggestion of hashmaps.
That's all true too though.
💤
Post marked as dormant
This post has been inactive for over 300 minutes, thus, it has been archived.
If your question was not answered yet, feel free to re-open this post or create a new one.
In case your post is not getting any attention, you can try to use /help ping
.
Warning: abusing this will result in moderative actions taken against you.