Java

Loading...

Из курса от партнера Saint Petersburg State University

Competitive Programmer's Core Skills

13 оценки

Explore Related Videos

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

Saint Petersburg State University

Competitive Programmer's Core Skills

13 оценки

During the course, you’ll learn everything needed to participate in real competitions — that’s the main goal. Along the way you’ll also gain useful skills for which competitive programmers are so highly valued by employers: ability to write efficient, reliable, and compact code, manage your time well when it’s limited, apply basic algorithmic ideas to real problems, etc. We start from the very beginning by teaching you what competitions there are, what are their rules, what specifics problems have, how to read problem statements, how to organize your work, and what you should and shouldn’t do. So it’s fine if you’ve never taken part in programming competitions before. We’ll focus on skills essential to competitive programming: inventing solutions and proving their correctness, estimating their running time, testing and debugging programs, how to benefit from structuring code. We’ll also cover basic algorithmic ideas: brute force search, dynamic programming, greedy algorithms, segment trees. On competitions, there are a lot of specific pitfalls, perilous to beginners — but that’s not to worry, as we’ll go through the most common of them: integer overflow and issues with fractional numbers, troubles of particular programming languages, how to get unstuck in general. And, you’ll hone all these skills by solving practice problems, which are just like problems on real competitions. You could use any of the following programming languages: C, C++, C#, Haskell, Java, JavaScript, Python 2, Python 3, Ruby, Rust, Scala. We assume that you already know how to write simplest programs in one of these.

Из урока

COMMON STRUGGLES 2

We continue considering common struggles arising in competitive programming. We start by learning how to prove that a natural greedy algorithm is correct. We also discuss programming languages: what features are most helpful on competitions, and what are the advantages and pitfalls of several frequently used languages. Finally, we study an essential and easy-to-implement data structure: the segment tree.

Basic Data Structures5:44

Advanced Data Structures and I/O7:51

Comparing Languages4:54

Познакомьтесь с преподавателями

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Alexander Logunov
Competitive Programming Co-coach at SPbSU
Kirill Simonov

In this video, we'll talk about specifics of Java.

We'll start with Input/Output.

The most convenient way to rate values is by using Scanner class.

But the issue is, it's very slow.

It can only be used for small inputs like 10,000 integers or

less and there is no any other alternative with the same functionality.

So, we need to construct it.

Which does create input fast is the BufferedReader class.

But, it only reads whole lines without splitting on [inaudible] numbers or words.

So, we need to parse the lines aligned by

BufferedReader to an instance of StringTokenizer which will split them into tokens.

After that, we could easily parse integers or

what else we need with functions like Integer.parseInt or similar ones.

And so, all that together makes a fast alternative for the Scanner.

It makes sense to put everything in one class and define

methods with Scanner-like names like nextInt or nextDouble.

It's also useful to write it once and then put it in your template code,

so as not to write it every time from scratch.

With output, it's simpler as

the standard PrintWriter class has all necessary functions and is fast enough.

Next, Java has a large variety of containers, data structures.

But, they always store objects and they would often,

I would like to store primitives like Ints.

Of course, we could use primitive wrappers like Capital Integer.

But, as the object,

they take much more space than just Ints.

For example, Capital Integer takes 16 bytes while Int just four bytes.

So, when using Collections with primitives,

we get substantial object overheads in terms of space and time.

And thus for example,

ArrayList of integers is much worse than just an array of Ints.

And so, you should use Arrays when you can,

when you work in script with primitives.

Also, Collections come in two kinds, synchronised and unsynchronised.

For example, Vector and ArrayList,

they do basically the same, only the first one is

synchronised and the second not synchronised.

The difference is, synchronised Collections are designed for more detailed performance.

And unsynchronised, on the other hand,

are optimized for single threads.

And so, on competitions as it's always

single threads then we should use unsynchronised Collections like ArrayList.

Next, about Strings, the basic string class is fine enough.

The only issue is, its instances are immutable.

It means that each time an object changes, a new copy of it is created.

And particularly, if we append character by character to a string each time,

there is a new object and so,

linear number of appends leads to a chaotic time.

In fact, there is another class just for that.

It's called StringBuilder and it

has append methods which just appends a single character.

But, it does it in constant time.

Of course, you could also use like other list of characters,

but the StringBuilder, there is no object overhead.

Finally, some other remarks you need to keep in mind when

estimating memory of custom classes that an object of custom class takes space,

takes more space than just the sum of its fields,

at least by eight bytes.

So, you need to be careful with memory.

Another thing, there are in fact two different sorting algorithms in Java.

One is Collections.sort and the second is Arrays.sort. They are different.

Collections.sort is a merge sort and so it works always

when you go often against time and it's stable.

In contrast, Arrays.sort is quick sort and so,

it's not stable but what's worse,

there are special cases where it's going to take time.

So, it makes sense to randomly shuffle an array before doing Arrays.sort, just in case.

Next, as objects are always assigned by reference,

do not forget to clone them when needed.

Because, if you have several different pointers to assign an object,

then changing one, changes also the others.

And clone it to various separate box when

you don't expect something to change and it changes.

So, watch for it. And, that's all for Java.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play