ca4pro - Moving average on Metrics

Back to General discussions forum

aszaloki     2024-09-06 09:04:54

Hi Rodion!

I have implemented the Moving average on Metrics problemon on ca4pro, but I do not know how I should prepare the code for getting the server-side generated input data. Should I read from the standard input? Or create a web request like in the interactive problems?

Thanks!

Rodion (admin)     2024-09-06 10:57:30
User avatar

Hi, and thanks for testing it!

Yes, read from stdin, print to output, similar to the simplified version here (just with newlines instead of spaces).

It is executed on the server side like this:

./data-generator-script | ./your-code

i.e. input is simply fed via "pipe" operator. this is a new feature, with running code in any language available in sandbox, so please don't hesitate to complain about whatever issues you may encounter

(it also means the same code which you submit should work with sample input when you just click "run" button)

aszaloki     2024-09-09 07:13:04

Hi,

I think I have done it the right way, with test data it passes (I found that the input contains "\n" character at the end of each line), clicking the "Run it" button my program results the correct answer, although I cannot make it accept by submitting: The checker says "Non-zero exit code!" - so there is run-time error in my code somewhere, but with lack of any error message, it is difficult to investigate, even I cannot write messages for myself for debugging, I get just the "Non-zero exit code".

Could you please look into my code? Or could you tell me the exact structure of the input with an example? Or change the checker in order to give more proper error message?

Thank you in advance!

TestUser     2024-09-09 07:26:47
User avatar

Hi! I tried the code - it seems there is output below the "Non-zero-exit code" - just it went unnoticed (perhaps due to compiler producing spare new-line). I've found it by simply dragging the area with the answer downwards :)

Added printing of stdout in this case too (but in this specific situation there is nothing in stdout):

Non-zero exit code!
STDOUT: 
STDERR: 
Unhandled Exception:
System.IndexOutOfRangeException: Index was outside the bounds of the array.
  at ConsoleApp1.Program.Main (System.String[] args) [0x00064] in <c5d5c8afb1e747e6ad15b0a58250ad16>:0 
[ERROR] FATAL UNHANDLED EXCEPTION: System.IndexOutOfRangeException: Index was outside the bounds of the array.
  at ConsoleApp1.Program.Main (System.String[] args) [0x00064] in <c5d5c8afb1e747e6ad15b0a58250ad16>:0 
aszaloki     2024-09-09 11:15:56

Hi,

ok thank you, now I could trace what was happening. The input is a little bit confusing, the last line is an empty line as far as I could see (need to discard it). Now the current message is that my algorithm is judged too slow, although I iterate the records backwards (until the difference of timestamps is smaller than 1 minute), so I do not know how to make it faster for now. But probably this is the challenge of this problem :)

The problem statement mentions that the server may be slower than computers nowadays. I keep on trying :)

Thanks!

TestUser     2024-09-09 12:12:37
User avatar

Hm-m-m, the last line should be exactly --- 0 0 (i.e. with three dashes instead of metric name) which is a signal to stop... I checked data generator - it seems still to be there :)

As regarding to speed, the input size is chosen so that slow languages like Python won't allow too simple and straightforward approach. But C#, Java and natively compiled languages should be much faster so perhaps even plain array may work with them, perhaps with some care. However I thought the main idea of the problem was there is opportunity to sacrifice precision and avoid keeping whole data in-memory (which also may speed up calculations).

gardengnome     2024-09-09 16:04:10
User avatar

Have a look at the sliding window concept.

Rodion (admin)     2024-09-09 17:23:27
User avatar

by "straightforward" approach I meant the sliding window without tricks... but now I think my pythonic implementation was somewhat lame - so yes, it should work too.

Pity. It seems not possible to impose interesting memory limit because the limited running time won't allow filling any reasonable amount of megabytes.

gardengnome     2024-09-09 18:15:17
User avatar

Interesting. I had a go over at CA4Pro and I am pretty sure that my Python solutions is O(n) yet it times out.

Rodion (admin)     2024-09-09 18:21:54
User avatar

my Python solutions is O(n) yet it times out.

limit was chosen tightly, e.g. that reference solution itself (in python) takes perhaps half the time limit or more... it is not very good, but I have no good idea how to improve this situation... thus there could be some "flakiness" in accepting/rejecting results anyway :(

gardengnome     2024-09-09 18:34:54
User avatar

No worries. Need to improve my constant factor. :)

Rodion (admin)     2024-09-09 19:48:13
User avatar

During dog walks some ideas sometimes come. I just returned and tried this code:

import time
import random
t0 = time.time()
a = []
s = 0
for i in range(2000000):
    x = random.randint(10000, 99999)
    s += x
    #a.append(x)
print(time.time() - t0)

Comparing time with the append commented and uncommented doesn't make big difference with standard python, but sandbox uses pypy3 as we remember - and with it difference seems to be more dramatic.

gardengnome     2024-09-09 20:11:51
User avatar

Yes, appending to a list will take some time but it should be O(1). And when using a deque, appending first/last and popping first/last should all be O(1) with good speed. Details here: TimeComplexity: Python Wiki. Can I just check what your code uses for detecting the stopping condition? Something like x.startswith("---")?

Rodion (admin)     2024-09-09 20:21:35
User avatar

let's see... not exactly like this

while True:
    name, t, v = input().split()
    if name == '---':
        break

Appending is O(n) I guess in most languages for sure, I just didn't noticed before it may be that slow... ruining constant factor :) So my approach probably quite saves on this.

Rodion (admin)     2024-09-10 14:45:46
User avatar

To aszaloki - I'm not much acquainted with C# but it may be useful to review discussions on some general pitfalls for competitive programmers: https://codeforces.com/blog/entry/22602 - for example I remember that in rival Java there was typical issue with reading input using Scanner class (otherwise handy) instead of some BufferedStream etc (poorly remember details myself).

gardengnome     2024-09-10 18:34:05
User avatar

Stupid me, should have used the following code at the start of my python program to speed up reading data from stdin (have never needed that on CodeAbbey but default on other sites):

import sys
input = lambda: sys.stdin.readline().rstrip()  # faster!
Rodion (admin)     2024-09-10 19:12:01
User avatar

That is curious, thanks for teaching the trick :) I can't at once understand why is it faster (because I don't know how default input() works), but I tried quick test:

-- generator.lua
for i = 1,10000000 do
    print(math.random(), math.random(), math.random())
end
print('---', 0, 0)

# test.py
sum = 0
while True:
    a, b, c = input().split()
    if a == '---':
        break
    sum += float(b)*float(c)
print(sum)

Now luajit generator.lua > /dev/null completes in 4 seconds, while luajit generator.lua | pypy3 test.py is 6.

Adding your snippet at the top turns it to 4.3... Impressive speed-up.

have never needed that on CodeAbbey

Yep, we generally don't need those tricks popular at competitive programming... original problem statement (saved in readme here) laked such restrictions but I thought that without restriction it wouldn't be very useful.

Please login and solve 5 problems to be able to post at forum