# Competitive Programming
# Vim
# First wave of commands
| Command | Action | Observation |
|---|---|---|
i | insert mode | Get out insert ctrl C, or esc or ctrl ] |
j and j | Move up and down | |
h and l | Move left and right | |
w and b | Hop words | |
y y | Copy line | |
y | Copy to clipboard | |
p | Paste | |
d d | Delete a line | If press P after paste the line deleted |
u | Undo last command | |
Shift v | Visual Line mode - Highlight a line | Pressing D, delete the selection |
v | Highlights the place | Use W to select the words |
:w | Save | |
g g | Go to start of the document | |
G | Go to the end of the document | |
Line number G | Go to "Line number" | |
Line number g g | Go to "Line number" |
In visual mode:
| Command | Action | Observation |
|---|---|---|
d w | Delete word | |
d j | Delete your line + one down | |
y w | Copy word | |
y j | Copy your line + one down |
Commands after setting up:
| Command | Action | Observation |
|---|---|---|
| / | Incremental search | just type / and what you want to find |
n N | Look forward and backwards |
# Setting Up VIM
first vim ~/.vimrc to create the vimrc file.
syntax on
set noerrorbells
set tabstop=4 softtabstop=4
set shiftwidth=4
set expandtab
set smartindent
set nu
set nowrap
set smartcase
set noswapfile
set nobackup
set undodir=~/.vim/undodir
set undofile
set incsearch
set colorcolumn=80
highlight ColorColumn ctermbg=0 guibg=lighgrey
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
then :w and :source % to source the file.
then rm -rf ~./vim
cat ~/.vimrc
# Vim Plugins
Plug 'morhetz/gruvbox' - colorscheme
Plug 'jremmem/vim-ripgrep' - veryfast rep
Plug 'tpope/vim-fugitive' -
Plug 'vim-utils/vim-man' - man pages
Plug 'lyuts/vim-rtags' - rtags
Plug 'git@github.com:kien/ctrlp.com.git' - file finding
Plug'git@github.com:Valloric/YouCompleteMe.git' - autocomplete
Plug 'mbbill/undotree'
# Useful Math
| Command | Action | Observation |
|---|---|---|
| Sum of the first n positive integers |
# CSES Problem Set
Solving CSES Problemset [12 Hour Livestream] [150 coding problems]
# Introductory Problems
# Weird Algorithm
Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one. For example, the sequence for n=3 is as follows: 3→10→5→16→8→4→2→1
Your task is to simulate the execution of the algorithm for a given value of n.
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
cout << n << " ";
while (n != 1) {
if (n % 2 == 0) {
n = n / 2;
cout << n << " ";
} else {
n = (n * 3) + 1;
cout << n << " ";
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TIP
- Use long long for n, otherwise will not pass for long numbers.
- It prints n as first thing to do.
Another way to solve this problem:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ll int n;
cin >> n;
while(n!=1){
cout<<n<<" ";
(n%2)? (n=3*n+1):n/=2;}
cout<<1;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TIP
Very clever way to use the if/else: in this case if (n%2) is true it divides by 2 or multiply by 3 and sum 1.
Also the n/=2 is very interesting
# Missing Number
You are given all numbers between 1,2,…,n except one. Your task is to find the missing number.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ll n, s=0;
cin >> n;
//sum all the numbers entered
for (int i=1; i<n; ++i) {
int a;
cin >> a;
s+=a;
}
cout << n*(n+1)/2-s;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TIP
The sum of the first n positive numbers is n*(n+1)/2, then we just have to sum all the numbers entered and subtract from the ssum of the first n positive numbers.
Another way to solve this problem:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll n, k;
cin >> n;
ll a[n+1] = {0};
for (ll i = 0; i < n-1; ++i) {
cin >> k;
a[k] = 1;
}
for (ll i = 1; i < n+1; ++i) {
if (a[i] == 0) {
cout << i;
break;
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
TIP
In this case every number entered receives the value 1 into an array of 0's. At the end you will have an array of only 1's but the one missing which will be 0.
He also used typedef, which is an interesting alternative to #define ll long long.
# Repetitions
You are given a DNA sequence: a string consisting of characters A, C, G, and T. Your task is to find the longest repetition in the sequence. This is a maximum-length substring containing only one type of character.
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int ans=1, c=0;
char l='A';
for(char i : s) {
if(i==l) {
++c;
ans = max(c, ans);
} else {
l=i;
c=1;
}
}
cout << ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
TIP
- For the loop to work s has to be a string and l had to be a char.
fmaxfunction is for the greater float, themaxfunction but was not working on clang.
At this problem we have to keep track of the longest and assign it to ans if greater than the repetition.
Another way to solve this problem:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
string s;
cin >> s;
int len = (int)s.length();
int mx = 0, cnt = 1;
s += "#";
for (int i = 0; i < len; ++i) {
if (s[i] == s[i + 1]) {
++cnt;
} else {
mx = max(mx, cnt);
cnt = 1;
}
}
cout << mx << endl;
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
The shorter way to solve this problem:
#include<iostream>
int main() {
int a = 1, l = 1;
char p, c;
std::cin >> p;
while(std::cin >> c) {
l += c == p ? 1 : -(l - 1);
a = std::max(a,l);
p = c;
}
std::cout << a;
}
2
3
4
5
6
7
8
9
10
11
12
TIP
The interesting about this one is the while to read with cin.
# Increasing Array
You are given an array of n integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.
On each turn, you may increase the value of any element by one. What is the minimum number of turns required?
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n;
cin >> n;
int mx=0;
ll ans=0;
for(int i=0; i<n; ++i){
int x;
cin >> x;
mx=max(mx, x);
ans += mx-x;
}
cout << ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TIP
In this case we can make a "track the max algorithm", and sum to the answer the max - x; If x is the max then ans receives 0. if x is not max then ans receives the difference.
Another solution for this problem:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
long long a[t];
long long sum=0;
for(int i=0; i<t; ++i) cin >> a[i];
for(int i=0; i<t-1; ++i)
{
if(a[i]>a[i+1])
{
sum+=a[i]-a[i+1];
a[i+1]+=a[i]-a[i+1];
}
}
cout << sum << endl;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Another one:
#include <bits/stdc++.h>
int main()
{
int n;scanf("%d",&n);
long long ans=0;int last=0;
while(n--)
{
int a;scanf("%d",&a);
if(a>last)last=a;
else ans+=(last-a);
}
printf("%lld\n",ans);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
# Permutations
A permutation of integers is called beautiful if there are no adjacent elements whose difference is 1.
Given n, construct a beautiful permutation if such a permutation exists.
Input
The only input line contains an integer .
Output
Print a beautiful permutation of integers . If there are several solutions, you may print any of them. If there are no solutions, print "NO SOLUTION".
Constraints
Example 1
Input: 5
Output: 4 2 5 3 1
Example 2
Input: 3
Output: NO SOLUTION
# Solution:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ll int n;
cin >> n;
if(n==1){
cout << 1;
return 0;
}
if(n==2||n==3){
cout << "NO SOLUTION";
return 0;
}
//treat this as an even or odd case
if(n%2==0){
for(int i=2; i<n; i+=2)
cout << i <<" ";
for(int i=1; i<n; i+=2)
cout << i <<" ";
} else {
for(int i=n-1; i>0; i-=2)
cout << i <<" ";
for(int i=n; i>0; i-=2)
cout << i <<" ";
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Other solutions:
# Blind 75 Must Do Leetcode
# 1. Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
2
3
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
2
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
2
Constraints:
- 2 <= nums.length <= 104
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- Only one valid answer exists.
Follow-up:
Can you come up with an algorithm that is less than O(n2) time complexity?