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.