Back to General discussions forum
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!
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)
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!
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
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!
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).
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.
Interesting.
I had a go over at CA4Pro and I am pretty sure that my Python solutions is O(n)
yet it times out.
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 :(
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.
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("---")
?
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.
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).
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!
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.