Algorithmic notations

[adam2016]

Hey guys,

So my question may sound strange but it isn't a question about algorithm time complexity such as big O notation,

my question is about the notation that you are given in order to fill complete an algorithm, maybe algorithm specification would be the correct way of putting it?


so lets say in this example - https://www.codechef.com/FEB19A/problems/MAGICJAR

the constraints and input section look like gibberish to me

so what does this notation mean? and where can I study it, I can obviously decipher greater and less than signs and also spotted a sigma character( sum of all)

thanks

1≤T≤1,000
1≤N≤105
1≤Ai≤109 for each valid i
the sum of N over all test cases does not exceed 106

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers A1,A2,…,AN.

[helios]

I don't understand. Which notation in particular are you referring to? The whole problem statement is just using standard mathematical notation. It doesn't use anything unusual that I can see.

As for the Input and Constraints sections, I think they're fairly straightforward:

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers A1,A2,…,AN.

In other words, the input looks like

an_integer_called_T
an_integer_called_N
an_integer_called_A1 an_integer_called_A2 [etc] an_integer_called_An
an_integer_called_N
an_integer_called_A1 an_integer_called_A2 [etc] an_integer_called_An
[etc]

and the code to read the input would be

typedef std::vector<int> testcase;

std::vector<testcase> testcases;
size_t T;
std::cin >> T;
testcases.reserve(T);
while (testcases.size() < testcases.capacity()){
    size_t N;
    std::cin >> N;
    testcase t;
    t.reserve(N);
    while (t.size() < t.capacity()){
        int Ai;
        std::cin >> Ai;
        t.push_back(Ai);
    }
    testcases.emplace_back(std::move(t));
}

[Duthomhas]

Familiarity with basic (secondary) mathematics is prerequisite; unfortunately, a lot of beginning programmers lack that.

The other half is simply familiarity with the format of these kinds of things; they become easier to grok the more you read them.

That said, it is not uncommon for many of these problems to be poorly-phrased. Every author has his own way of writing stuff, as there is no One True Standard, just common practices. And people get out of it (and put in to it) what they want, no more or less.

[adam2016]

thanks guys,

so in order to really become an efficient programmer one should have a good grasp of mathematics?

what would you need to focus on mainly?

linear algebra, probability , number theory , calculus , sets?

[Duthomhas]

Yes*

Discrete math, theory of computation, set theory, graph theory, basic calculus, linear algebra, statistics/probability, geometry

*many good programmers don't even remember high-school math
But you are definitely improved by knowing what you are doing; domain specific, of course.

[helios]

"Efficient" programmer? I suppose that depends on what specific metric you're optimizing for.

Duthomhas was talking about the particular context of codechef (and related sites) problems. In general, at least in my experience, most problems I find myself solving are engineering problems, not mathematical problems.

[jonnin]

so in order to really become an efficient programmer one should have a good grasp of mathematics?

sort of. It honestly depends on what you are doing. It always helps, but how much it helps varies a lot. A good grasp of boolean logic is going to serve you well no matter what you do. Discrete is useful to avoid trying to do things that you can't do more than anything else, its just an understanding of things that prevents derp moments (and even having had the class and decades of coding, I still mess those up sometimes). And then there are the math heavy jobs; I used to support aerospace engineers and had to have a decent grasp of calculus, numerical methods, linear algebra, and more. You don't need that stuff to build a text processing piece of code, say a c++ back end that writes HTML does not generally require a differential equation. Writing a flight simulator or controls system does.

Big O notation isnt even used a lot in the workplace in my experience. Its just a quick metric of how much work a solution does to get an answer. Numerical problem statements are used when required but more often than not I get those in equation format than math lingo format, and as a result my math notation is a little rusty. An engineering shop might provide your requirements in math notation, or a R&D PHD heavy shop, but most places that I know of keep it simple enough that the jr programmer from the community college with 1/2 a degree can still do the work.

The more stuff you know, the better you will be at crafting efficient code, this is true. But in my experience, you will get more from studying algorithms than math on that front. I learned more about coding stuff from my algorithms class than I did in differential equations class, in other words. If you want to study math, get into the numerical methods side of it. Doing problems in code is unlike doing them on paper, more often than not.

[Duthomhas]

+1 on signing up for a class on design and analysis of algorithms. You will be completely lost if you dont have some basic discrete math and computational theory under your belt, though. Oh, and a good understanding of logarithms, which seems to be increasingly forgotten in elementary ed.