Just A Thought - Codeforces

23 месяца назад, # ^ |

← Rev. 2 →

There was one problem where numbers had size $$$4\cdot 10^{36}$$$ (see 1656H - Одинаковые НОК подмножеств), but I don't think the time limit is very Python-friendly either case, and C++ already has __int128; though one thing to note is that you still have to read input as a string and then convert it to a 128-bit int; output had similar concerns.

By the way, I'm pretty sure that you can't read a 100000-digit integer as a Python int because I don't know of a way to convert a number of length $$$n$$$ to binary in faster than $$$O(n^2)$$$ time.

→ Ответить

balalaika

23 месяца назад, # ^ |

+14

I'm pretty sure that you can't read a 100000-digit integer as a Python int

Sure you can read 100000-digit integer in python (161330597).

I think there is something smarter than plain $$$O(n^2)$$$ algorithm ($$$2^{32}$$$ base for digits already should give some speed-up, and maybe you can do some cool optimizations from fact that for parsing you need multipliing only by ten).

→ Ответить

23 месяца назад, # ^ |

Wow, thanks for telling me!

However, even given the simplicity of the code, it took the code over 1 second to run; I won't count on the other operations to be anywhere near efficient, because of all the binary conversions.

→ Ответить

23 месяца назад, # ^ |

← Rev. 2 →

oh, also, in addition to my explanation below, let me note that this amount of runtime is likely not entirely an issue of computing numbers! there were $$$100$$$ lines of input, $$$100 000 + 6 = 100 006$$$ bytes each, which comes to a maximum input size of a whopping $$$10 000 603$$$-byte ($$$10 MB$$$!) input. considering that he did not use Fast IO, I think about half the runtime went to processing the input. see my submission (161178040) for a solution that uses PyPy 3 and Fast IO.

→ Ответить

23 месяца назад, # ^ |

reading a 100000-digit integer, isn't a very big issue by itself in Python, noting that Python integers are essentially big arrays of 64-bit integers. neither is addition or subtraction a big issue. however, big integer multiplication can (and usually do) be a pain in the arse for Python! Python uses the Karatsuba algorithm to multiply big integers, and this algorithm has a $$$O(n^{log_2 3})$$$ time complexity, which can still escalate quite quickly, though faster than an $$$O(n^2)$$$ time complexity multiplication. (using the Decimal type is a possible circumvention to this time complexity, as it is known to be using a Number Theoretic Transform-based implementation for very large numbers). so the point is, while big integer support is a very convenient feature of Python, we at least need to know how fast (or SLOW in some cases!) it works before we use it.

→ Ответить

Raowl

23 месяца назад, # |

Can't agree more

→ Ответить

master_fool

23 месяца назад, # |

Yo!

→ Ответить

adityagamer

23 месяца назад, # |

Which language do u prefer to train ML models?

→ Ответить

xericha

23 месяца назад, # ^ |

bash xd

→ Ответить

Bungmint

23 месяца назад, # ^ |

Punch cards duh

→ Ответить

19 месяцев назад, # ^ |

-21

Is this a reference to this year's GCJ Quals :thinking:

→ Ответить

adityagamer

23 месяца назад, # |

→ Ответить

fried-chicken

23 месяца назад, # |

I think it's not wise to say some languages are good/bad without a specific field.

Just like you won't use python for CP, and won't use C/C++ for Web application(well, I know CGI) and deep learning(still, I know Caffe).

→ Ответить

Tet

23 месяца назад, # |

++++++++++ [>+>+++>+++++++> ++++++++++<<<<-] >>>----.>+++++++ +++++++.------ -----------.++++++++ .+++++.--------. +++++++++++++++.--- ---------------.+++++ +++.<<++.>>--.++ ++++++++.<<.>>++.- ------.------ ----.+.++++ +++++++++..-- ------------- --.++++++++++++++++ +++.----------- ----.-.<<++++ ++++++++++.

→ Ответить

udta_kouwa

23 месяца назад, # ^ |

-[--->+<]>-.-[--->+<]>+.+++.++[->+++<]>.

→ Ответить

Abito

19 месяцев назад, # ^ |

Ah yes, Brainfuck

→ Ответить

19 месяцев назад, # |

-18

Python is terrible,its high precison calculations make the contest unfair.Hope Codeforces can forbidden python in contests.

→ Ответить

Lyrith

19 месяцев назад, # ^ |

← Rev. 2 →

+22

Think before you speak.

→ Ответить

19 месяцев назад, # ^ |

-9

So you want to use Python in CSP,NOIP and NOI?If that happens,nobody will learn other programming languages.

→ Ответить

19 месяцев назад, # ^ |

Other competitions that do support Python clearly exist. OIs on a few countries (i.e. South Korea) and the ICPC WF are great examples.

→ Ответить

19 месяцев назад, # ^ |

-9

WTF,IOI allows using Python?!!As if I hadn't said anything.Use international standards as the standard

→ Ответить

19 месяцев назад, # ^ |

bruh do you think the ICPC World Finals is not an international standard

→ Ответить

candy_king

19 месяцев назад, # ^ |

← Rev. 2 →

ni bu wan yuan shen, ni ma si le.

→ Ответить

19 месяцев назад, # ^ |

← Rev. 2 →

You: "forbid Python please"

Java, Ruby, and the several more languages with BigInteger support: Allow us to introduce ourselves.

C++ Technical Specification P1889 aka "Numerics TS 1": Yes I am indeed jealous of this feature

→ Ответить

19 месяцев назад, # ^ |

-8

But Python's high precison calculations has no limits.C++'s __int128 can only store about 40 digits at most

→ Ответить

19 месяцев назад, # ^ |

Sir would you kindly look at the C++ Technical Specification P1889R1

→ Ответить

19 месяцев назад, # ^ |

Part of what makes a good coder is knowing when to use what language. Plus, with C++ you can copy a bigint template somewhere either way.

→ Ответить

19 месяцев назад, # ^ |

-8

Then that's more troublesome because you have to write it yourself.And using Python in contests may make the contest unfair.

→ Ответить

freehandle

19 месяцев назад, # ^ |

What's your point? Every language provides slightly different libraries anyways. Also, writing a simple BigInteger class yourself only takes a few minutes.

→ Ответить

19 месяцев назад, # ^ |

← Rev. 2 →

Maybe he's just too short-sighted on things about built-in features. Now I am curious on how he will react when he realized that calculating prefix sums and adjacent difference arrays (literally one half of the solution on 1738B - Упоротые префиксные суммы) was a built-in feature on C++.

→ Ответить