Competitive-Programming-and-Contests-Solution

This repository contains the solution to the problems proposed at the Course of Competitive Programming by the University of Pisa.

Table of Content

• Introduction
• Built with
• Problems with a brief discussion about them
• How to build the solutions
• How to contribute
• License

Introduction

Each solution is provided with a battery of unit tests and a code structure under the src directory that looks like the following tree:

• src
  • test
    • Main.cpp: Tests units where is possible to test the solution in local with the test result on the console.
    • *.hpp: A couple of files to implement the test tools, implemented inside the repository cpstl
  • core
    • SolutionName.hpp: a file that contains the solution of the problem
    • One or more data structure file implemented inside the repository cpstl
  • MainSite.cpp: The file that contains the solution for the online judge
  • CMakeFile

Some solutions are provided with different implementations (where is present or covered by the developer) with complete benchmarks developed with Google benchmark. The result is stored inside a JSON or a CVS file called result and the machine where there are running has the following characteristic.

• OS: Linuxmint 20.1 ulyssa
• CPU: Intel Core i5-6300U @ 4x 3GHz
• RAM: 16 GB.

Some of these benchmarks have a complete discussion with the Jupiter Notebook, see the last column of the tables below.

If you want to run the benchmark on your own computer and your computer is a personal computer, in some cases you need to disable some machine setting, but you can follow this answer on StackOverflow (If you are using a linux machine)

Built with

All the solutions are developed with C++ STD, and also with a couple of external tools reported below:

• CPSTL: Competitive Programming Standard "library", is a new project with the object to include a complete collection of algorithms and data structure to use in the Competitive Programming problem. Also, it is open to support different programming languages.
• Google benchmark: A Google framework to make cool micro benchmarks, you need to install it if you want to run the benchmarks in some problem, otherwise you can avoid installing it.

Problems with a briefly discussion about them

Name	Solved	Repository	Report
Leaders in array	✔️	Code	_
Kadane's algorithm	✔️	Code	_
Missing number in array	✔️	Code	_
Trapping rain water	✔️	Code	_
Sliding window maximum	✔️	Code	Class Report
Next larger element	✔️	Code	_
Towers	✔️	Code	_
Finding Team Member	✔️	Code	_
The Monkey and the Oiled Bamboo	✔️	Code	_
Inversion count	✔️	Code	_
Two Types of Spells	✔️	Code	_
Frogs and Mosquitoes	✔️	Code	_
Maximum path sum	✔️	Code	_
Longest k Good Segment	✔️	Code	_
Ilya and Queries	✔️	Code	_
Number of ways	✔️	Code	_
Little girl and maximum sum	✔️	Code	_
Update the array	✔️	Code	_
Nested segments (also segment tree)	3/3 ✔️	Code	_
Pashmak and Parmida's problem	✔️	Code	_
Circular RMQ	✔️	Code	Benchmarks
Triplets	✔️	Code	_
Smaller Values	1/3 ✔️	Code	_
Powerful array	✔️	Code	_
Tree and queries	✔️	Code	_
Longest common subsequence	✔️	Code	_
Minimum number of jumps	✔️	Code	_
Subset sum	4/4 ✔️	Code	_
0-1 knapsack	✔️	Code	_
Longest increasing subsequence	✔️	Code	_
Longest bitonic subsequence	✔️	Code	_
Edit distance	✔️	Code	_
Vertex cover	✔️	Code	_
Longest palindromic subsequence	✔️	Code	_
N meetings in one room	✔️	Code	_
Magic numbers	✔️	Code	_
Wilbur and array	✔️	Code	_
Alternativ e thinking	✔️	Code	_

Segment Tree report

During the Courses is developed also a small paper to introduce the Segment tree by Examples. "Segment Tree: A Complete Introduction by Examples"

Report Experiments

Name	Solved	Repository	Report
RMQ	✔️	Code	Benchmarks
Circular RMQ	✔️	Code	Benchmarks
Kth Zero	✔️	Code	_
MKTHNUM	✔️	Code	Benchmarks
Range Updates and Sums	🚧	Code	_

Appendix

Name	Solved	Repository
DQUERY	✔️	Code
FibonacciNum	✔️	Code
ClotestValueOnBST	🚧	Code
TwoNumberSum	✔️	Code

Google kikstart 2020

Name	Solved	Repository
Allocation	✔️	Code
Plates	🚧	Code

How to build the solutions

Each solution contains a complete test unit developed with a Test tool developed ad-hock as a "Copy and Paste" code, and to build the project to run the test the following commands are required

>> mkdir build && cd build
>> cmake .. && make
>> ./NameSolution

One possible output is reported below

|------------ TEST TEST_CASE_ONE_SEGMENT_TREE -------------------|
TEST_CASE_ONE_SEGMENT_TREE PASSED
|------------ TEST TEST_CASE_ONE_LAZY_SEGMENT_TREE -------------------|
TEST_CASE_ONE_LAZY_SEGMENT_TREE PASSED
|------------ TEST TEST_CASE_TWO_LAZY_SEGMENT_TREE -------------------|
TEST_CASE_TWO_LAZY_SEGMENT_TREE PASSED
|------------ TEST TEST_CASE_THREE_LAZY_SEGMENT_TREE -------------------|
TEST_CASE_THREE_LAZY_SEGMENT_TREE PASSED

How to contribute

The repository is open to receive a contribution to improving solutions or the quality of the repository, there are only a few rules to respect that are reported below.

• Each solution need to start with the C++ template project, available here
• Each code that is inside the repository needs to follow the well-formatted code guidelines, so if the solution uses the C++ classes the Google code style needs to be included in the solution. clang-format file available at the following link, otherwise is the C++ is without classes a Linux Kernel guidelines need to be included clang-format file available at the following link.
• New implementation of data structure needs to be push also in repository cpstl.
• Each solution, need to contain a Readme with some details about the implementation and the time execution on the online Judge, one example can be the following solution
• Have fun.

License

all the professor of the class Competitive Programming and Contest https://github.com/rossanoventurini/CompetitiveProgramming

Copyright (c) 2020-2021 Vincenzo Palazzo vincenzopalazzodev@gmail.com and

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.