Much harder than what I thought. I was reasoning about inverse sorting permutations (which can be computed in linear time) but I couldn't figure out the solution so I looked it up online and it has nothing to do with it.
I'm curious, is there any "off the shelf" algorithm that use this jump strategy?
result[i] += result[i+result[i]]
Assuming you went to a university to study computer science, you should have been given the knowledge of how to design algorithms on your own, and how to evaluate their time complexity and space complexity. You should also have been given plenty of assignments to practice your ability to do this with a wide variety of problems. Although you would not be shown every problem, you would have the skills to adapt to new problems.
You DID do all of your homework, right? And you did it yourself instead of asking someone to do it for you, or googling for the answers, right?
You don't need to be able to learn every kind of problem, you just need to be able to learn how to approach algorithmic problems in general so you can figure out a solution yourself.
Be honest, are you be able to solve this exercise (in linear time) without looking at the solution?
2 years ago
Anonymous
yes. there are a number of other problems analogous to it that you should have encountered in an undergraduate computer science class that it should be straightforward to solve for anyone who paid attention and is capable of actually *thinking* rather than just regurgitating memorized snippets of code.
2 years ago
Anonymous
>there are a number of other problems analogous to it that
feel free to list some
2 years ago
Anonymous
> Falling for the memorization is bad meme this hard
2 years ago
Anonymous
memorization isn't bad, it's just not intelligence. everybody needs memorization on some level but if that's all you've got you're probably moronic
>sort
You dumb fricking moron.
People like you is the reason why software is so shit these days.
Do the world a favour and quit programming or just kys.
The whole point is to model how the complexity grows with input size, which is why n is assumed to be large.
2 years ago
Anonymous
No the whole point is there is some finite number for which the big O function begins to grows faster than the algorithm. It has nothing to do with infinity you fat butthole.
result = [0] * len(temperatures)
stack = []
for i, t in enumerate(temperatures):
while stack and stack[-1][0] < t:
j = stack[-1][1]
result[j] = i - j
stack.append((t, i))
print(result)
Oh I think I get it. You walk right maintaining every element you see. Then for each new element you see, you check whether it can eliminate some elements from the ones you've seen so far recent first. Because of the elimination, the elements you maintain are necessarily in decreasing order.
It's O(n) because we advance one element each step and each element is "eliminated" once. Something like that.
I don't code as my job so I might be missing some clever way to do this, but it seems that you can keep track of an index for each entry and then have another tracker which scans ahead of the entry, increments a counter until it hits a next greater value. Reset the index at the next loop. Sounds like it'd be slow, though.
Yes, worst case scenario being an all decreasing list of temperatures, with the last element being the largest temperature. e.g. (54, 53, 52, 51, ... ,70).
So I see a monotonic stack solutions to this. But can someone explain the complexity of that solution? Is it supposed to be O(n)? It seems like O(n^2) to me.
Aren't there bots that can solve most of these programming puzzles now? Why do people still attempt to do them manually?
To me, it's like doing long division when calculators exist.
Or expanding/factorizing long polynomials.
Why not practice a useful skill instead? Like agriculture? Or painting?
because school teaches you how to reach the solution by your own, and not the solution itself. imagine if civil engineering schools drilled you on how to build bridges of specific, exact lengths and capacities instead of teaching general principles of materials science and structural engineering which, when applied correctly, let you design bridges for any kind of purpose.
the downside of this kind of teaching is if you're mentally deficient you simply can't reach the solution by your own. sorry OP.
import random
n = 50
temp_range = (30, 100)
temperatures = [random.randint(*temp_range) for _ in range(n)]
stack = []
answer = [0]*n
for i in range(n):
if stack:
j=stack.pop()
while temperatures[j]<temperatures[i]:
answer[j] = i-j
if not stack:
break
j=stack.pop()
else:
stack.append(j)
stack.append(i)
print(temperatures)
print(answer)
godson thread now.
Much harder than what I thought. I was reasoning about inverse sorting permutations (which can be computed in linear time) but I couldn't figure out the solution so I looked it up online and it has nothing to do with it.
I'm curious, is there any "off the shelf" algorithm that use this jump strategy?
result[i] += result[i+result[i]]
>Much harder than what I thought
Yeah monotonic stack problems are always unintuitive to me
Assuming you went to a university to study computer science, you should have been given the knowledge of how to design algorithms on your own, and how to evaluate their time complexity and space complexity. You should also have been given plenty of assignments to practice your ability to do this with a wide variety of problems. Although you would not be shown every problem, you would have the skills to adapt to new problems.
You DID do all of your homework, right? And you did it yourself instead of asking someone to do it for you, or googling for the answers, right?
I've never encountered a monotonic stack problem in textbooks or exams
You don't need to be able to learn every kind of problem, you just need to be able to learn how to approach algorithmic problems in general so you can figure out a solution yourself.
Be honest, are you be able to solve this exercise (in linear time) without looking at the solution?
yes. there are a number of other problems analogous to it that you should have encountered in an undergraduate computer science class that it should be straightforward to solve for anyone who paid attention and is capable of actually *thinking* rather than just regurgitating memorized snippets of code.
>there are a number of other problems analogous to it that
feel free to list some
> Falling for the memorization is bad meme this hard
memorization isn't bad, it's just not intelligence. everybody needs memorization on some level but if that's all you've got you're probably moronic
kys
zoomer memes are so fricking bad jesus christ
basedjack is more of a late-millenial meme than a zoomer meme
O log n to sort
O n to find the days
Amirite?
>sort
You dumb fricking moron.
People like you is the reason why software is so shit these days.
Do the world a favour and quit programming or just kys.
>O log n to sort
It's n log n to sort.Which is, strictly speaking, more than n.
not for sufficiently small values of n
Then why bother sorting at all? Just use a bunch of if else to solve it
moron
Big-O notation is defined for n -> +infty.
That doesn't make any sense
The whole point is to model how the complexity grows with input size, which is why n is assumed to be large.
No the whole point is there is some finite number for which the big O function begins to grows faster than the algorithm. It has nothing to do with infinity you fat butthole.
wrong.
Fat
Short.
Why would you sort?
The only thing school really teaches you is how to follow a boss
result = [0] * len(temperatures)
stack = []
for i, t in enumerate(temperatures):
while stack and stack[-1][0] < t:
j = stack[-1][1]
result[j] = i - j
stack.append((t, i))
print(result)
oops, should be
j = stack.pop()[1]
Assuming the input array is Input and the output is Answer:
for(int i = Input.size()-1;i > 0;i--){
if(Input[i] > Input[i-1])
Answer[i-1] = 1;
else
Answer[i-1] = Answer[i] != 0 ? Answer[i] : 0;
}
Oh I think I get it. You walk right maintaining every element you see. Then for each new element you see, you check whether it can eliminate some elements from the ones you've seen so far recent first. Because of the elimination, the elements you maintain are necessarily in decreasing order.
It's O(n) because we advance one element each step and each element is "eliminated" once. Something like that.
vector<int> dailyTemperatures(constvector<int>& temperatures) {
const size_t n = temperatures.size();
vector<int> res(n);
int hottest = 0;
for (int i = n-1; i >=0; i--) {
int c = temperatures[i];
if (c >= hottest) {
hottest = c;
} else {
int d = 1;
for (d = 1; temperatures[i+d] <= c; d += res[i+d]);
res[i] = d;
}
}
return res;
}
Presumably because you weren't competing in ioi, this crap gets taught at highschool prep for ioi.
I don't code as my job so I might be missing some clever way to do this, but it seems that you can keep track of an index for each entry and then have another tracker which scans ahead of the entry, increments a counter until it hits a next greater value. Reset the index at the next loop. Sounds like it'd be slow, though.
Isn't that O(n^2)?
Yes, worst case scenario being an all decreasing list of temperatures, with the last element being the largest temperature. e.g. (54, 53, 52, 51, ... ,70).
Just go backwards through it you fricking brainlet shit thread
So I see a monotonic stack solutions to this. But can someone explain the complexity of that solution? Is it supposed to be O(n)? It seems like O(n^2) to me.
>can someone explain the complexity of that solution?
Each element is pushed exactly once and popped at most once.
Aren't there bots that can solve most of these programming puzzles now? Why do people still attempt to do them manually?
To me, it's like doing long division when calculators exist.
Or expanding/factorizing long polynomials.
Why not practice a useful skill instead? Like agriculture? Or painting?
Programming bots and painting bots still make elementary mistakes. No idea about agriculture bots.
What a weird looking dog.
>import solution
>solution.solve()
done
because school teaches you how to reach the solution by your own, and not the solution itself. imagine if civil engineering schools drilled you on how to build bridges of specific, exact lengths and capacities instead of teaching general principles of materials science and structural engineering which, when applied correctly, let you design bridges for any kind of purpose.
the downside of this kind of teaching is if you're mentally deficient you simply can't reach the solution by your own. sorry OP.
import random
n = 50
temp_range = (30, 100)
temperatures = [random.randint(*temp_range) for _ in range(n)]
stack = []
answer = [0]*n
for i in range(n):
if stack:
j=stack.pop()
while temperatures[j]<temperatures[i]:
answer[j] = i-j
if not stack:
break
j=stack.pop()
else:
stack.append(j)
stack.append(i)
print(temperatures)
print(answer)
>stack
>append
whoever wrote the stdlib deserves a painful death
It's only 10^5. Doesn't even matter.
f(t) = @views map(i -> something(findfirst(x -> x - t[i] > 0, t[(i + 1):end]), 0), eachindex(t))
Next.
not finished yet
Fricking finally
Don't care about O(n) or the constraints
I just wanted a bullshit problem
use strict;
use warnings;
use v5.10;
my @temp=(73, 74, 75, 71, 69, 72, 76, 73);
my @answer;
my $wait;
my $curr;
my $j;
for (my $i=0; $i < @temp; $i++) {
$wait=0;
$curr=$temp[$i];
for ($j=$i+1; $j < @temp; $j++) {
$wait++;
if ($curr < $temp[$j]) {
last;
}
}
if ($j < @temp) {
if ($curr < $temp[$j]) {
$answer[$i]=$wait
}
else {
$answer[$i]=0
}
}
else {
$answer[$i]=0
}
}
say join ", ", @answer;
to make this ugly bastard
I lost a day on this.
In the end, 2 conditions were inverted, and a label was misplaced
; nasm -f elf64 temperature.asm && ld temperature.o -o temperature -dynamic-linker /lib64/ld-linux-x86-64.so.2 -lc && ./temperature
; ebx $i
; ecx $curr / $wait (wait_days)
; edx $j
global _start
extern printf
section .data
temp: dd 73, 74, 75, 71, 69, 72, 76, 73
answer: dd 0, 0, 0, 0, 0, 0, 0, 0
temp_length: dd 8
wait_days: dd 0 ; wait: is an error
curr: dd 0
format: db "%d", 0xa, 0x0
section .text
_start:
; for (my $i=0; $i < @temp; $i++) {
mov ebx, 0 ; $i = 0
loop_i:
mov dword [wait_days], 0 ; $wait = 0
mov ecx, [temp, 4*ebx] ; $curr = $temp[$i]
mov dword [curr], ecx
; for ($j=$i+1; $j < @temp; $j++) {
mov edx, ebx ; $j=$i+1
inc edx
loop_j:
inc dword [wait_days] ; $wait++
cmp ecx, [temp + 4*edx] ; if ($curr < $temp[$j])
jl last ; last
inc edx
cmp edx, [temp_length]
jl loop_j
; }
last:
cmp edx, [temp_length]
jnl else
cmp ecx, [temp + 4*edx]
jnl else
; this overwrite $curr, but we don't need it anymore
mov ecx, [wait_days]
mov dword [answer + 4*ebx], ecx
jmp end_if
else:
mov dword [answer + 4*ebx], 0
end_if:
inc ebx
cmp ebx, [temp_length]
jl loop_i
; }
; say for @answer
mov ebx, 0
loop:
mov rdi, format
mov rsi, rbx
mov rsi, [answer + 4*ebx]
call printf
inc ebx
cmp ebx, [temp_length]
jl loop
; exit(0)
mov rax, 60
mov rdi, 0
syscall
I thought this was stupid easy and OP was trolling until I saw it's for all i not just a specific i
Go backwards and use a stack