CSES Introductory Problems Editorial
[cp
]
This post contains solutions for problems in the CSES Introductory Problems. For any feedback, feel free to contact me.
Table of Contents
- Weird Algorithm
- Missing Number
- Repetitions
- Increasing Array
- Permutations
- Number Spiral
- Two Knights
- Two Sets
- Bit Strings
- Trailing Zeroes
- Coin Piles
- Palindrome Reorder
- Gray Code
- Tower of Hanoi
- Creating Strings
- Apple Division
- Chessboard and Queens
- Digit Queries
- Grid Paths
Weird Algorithm
A brute force solution is sufficient for this problem. Whether or not every natural number eventually reduces to 1 is called the Collatz conjecture. Time and space complexity is O(n).
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n; cin >> n; // note: range of int is insufficient for this problem
while(n > 1){
cout << n << ' ';
if(n&1) n = n*3 + 1; // bit hack to check if a number is odd
else n /= 2;
}
cout << 1 << endl;
}
Missing Number
We know that the sum of numbers from \(1\) to \(n\) is \(\frac{n(n+1)}{2}\). We can then sum up the numbers given then subtract it from the sum of all numbers from \(1\) to \(n\). We then get the missing number. Time complexity is \(O(n)\). Space complexity is \(O(1)\).
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n; cin >> n;
long long sum = 0;
for(int i=0,k;i<n;i++){
cin >> k;
sum += k;
}
cout << n*(n+1)/2 - sum << endl;
}
Repetitions
We store when the last change occurred, then for each character we check if it is larger than the running maximum. Time and space complexity is O(n).
#include <bits/stdc++.h>
using namespace std;
int main(){
string s; cin >> s;
int last = 0;
int cur_max = 1;
for(int i=1;i<(int)s.size();i++){
if(s[i] != s[i-1]) last = i;
cur_max = max(cur_max, i - last + 1);
}
cout << cur_max << endl;
}
Increasing Array
We increase each number until it is at least as large as the previous number. Time and space complexity is O(n).
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; cin >> n;
int a[n];
for(int i=0;i<n;i++) cin >> a[i];
long long cnt = 0; // note: range of int is insufficient for this problem
for(int i=1;i<n;i++){
if(a[i] < a[i-1]){
cnt += a[i-1] - a[i];
a[i] = a[i-1];
}
}
cout << cnt << endl;
}
Permutations
I print all odd numbers first, then all even numbers. Time and space complexity is O(n). There are special cases for n = 2, 3 and 4.
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; cin >> n;
if(n == 2 || n == 3){
cout << "NO SOLUTION" << endl;
return 0;
} else if(n == 4){ // There are methods which doesn't require this special case
cout << "3 1 4 2" << endl;
return 0;
}
for(int i=1;i<=n;i+=2) cout << i << ' ';
for(int i=2;i<=n;i+=2) cout << i << ' ';
cout << endl;
}
Number Spiral
The \(n\)th outer layer consists of numbers in the range \(((n-1)^2, n^2]\). The maximum of \(x\) and \(y\) determines the layer, and if it is on the horizontal or vertical edge.
#include <bits/stdc++.h>
using namespace std;
int main(){
int T; cin >> T;
while(T--){
long long x,y; cin >> x >> y; x--; y--;
if(y > x && y % 2 == 0) cout << (y+1)*(y+1) - x << endl;
if(y > x && y % 2 == 1) cout << y*y + x + 1 << endl;
if(y <= x && x % 2 == 0) cout << x*x + y + 1 << endl;
if(y <= x && x % 2 == 1) cout << (x+1)*(x+1) - y << endl;
}
}
Or, combining all together into one line:
#include<bits/stdc++.h>
using namespace std;
int main() {
int T; cin >> T;
while(T--){
long long x,y; cin >> x >> y; x--; y--;
cout << (max(x,y) + 1)*(max(x,y) + 1) + ((max(x,y)%2==0)?1:-1) * (y-x) - max(x,y) << endl;
}
}
Two Knights
We can find the number of ways to place two knights on the board, which is \({k^2 \choose 2}\), then subtracting the number of ways where they attack each other.
Note that when they attack each other, they stand in a \(2\times3\) rectangle. In each \(2\times3\) rectangle, there are two ways to place them such that they attack each other. Hence the number of ways they attack each other is \(2\times2\times(k-1)\times(k-2)\).
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; cin >> n;
for(long long k=1;k<=n;k++){
cout << (k*k)*(k*k-1)/2 - 4LL*(k-1)*(k-2) << endl;
}
}
Two Sets
Note that if we can seperate \(1, 2, 3, \ldots, n\) into two sets, then the sum of them, \(n(n+1)/2\) must be divisible by 4. Hence, n must be divisible by 4 or (n+1) must be divisible by 4.
We can then prove that we can split 1 to n into two sets in both these cases.
If n is divisible by 4, let us split the numbers into pairs of \((i,n+1-i)\). Then we have \(\frac{n}{2}\) pairs of numbers that sum to \(n+1\). We can now split them into two sets, and we are done.
If (n+1) is divisible by 4, let us split the numbers into pairs of \((i,n-i)\), and \(n\) by itself. Then we have \(\frac{n+1}{2}\) sets of numbers that sum to \(n\). We can now split them into two sets, and we are done.
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; cin >> n;
if(n%4 != 0 && (n+1)%4 != 0){
cout << "NO" << endl;
return 0;
}
cout << "YES" << endl;
vector<int> a,b;
if((n+1)%4==0){ b.push_back(n); }
for(int i=1;i<=n/2;i++){
if(i&1) { a.push_back(i); a.push_back(n/2*2+1-i); }
else { b.push_back(i); b.push_back(n/2*2+1-i); }
}
cout << a.size() << endl;
for(int k : a) cout << k << " ";
cout << endl;
cout << b.size() << endl;
for(int k : b) cout << k << " ";
cout << endl;
}
Bit Strings
Since every digit can be 0 or 1, the number of possible bit strings is \(2^{n}\). We can use binary exponention modulo a number to compute our result mod \(1\text{e}9+7\)
#include <bits/stdc++.h>
using namespace std;
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
int main(){
int n; cin >> n;
cout << binpow(2,n,1e9+7) << endl;
}
Trailing Zeroes
A trailing zero appears when it can be divided by 10. Hence, the number of trailing zeroes is the number of times we can divide the number by 5. (There are more 2 than 5, so we don’t need to count them.)
We can use Legendre’s formula to compute the number of trailing zeroes in \(n!\).
Time complexity is \(O(\log n)\).
#include <bits/stdc++.h>
using namespace std;
int main(){
int cnt = 0;
int n; cin >> n;
while(n){
cnt += n /= 5;
}
cout << cnt << endl;
}
Coin Piles
The total number of coins must be a multiple of 3, since we take away exactly 3 coins at a time. The larger of the piles must have at most double of coins than the smaller of the piles, since for every coin we take away at the smaller pile, we can only take at most two from the larger pile.
We can easily prove that all other combinations are possible, since we can do both operations at once each time and take 3 from both tiles, until one becomes double the other and we can do one operation until both becomes empty.
Time complexity is \(O(T)\), where T is the number of test cases.
#include <bits/stdc++.h>
using namespace std;
int main(){
int T; cin >> T;
while(T--){
int a,b; cin >> a >> b;
if(max(a,b) <= 2*min(a,b) && (a+b)%3 == 0) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
Palindrome Reorder
If the string has an even number of characters, then all characters must appear an even number of times. Then we can print half of each character in the first half, then attach the other half in reverse order.
If the string has an odd number of characters, then exactly one character appear an odd number of times. Then we can do the same as above, but attach the extra character in the middle.
Time and space complexity are both O(n).
#include <bits/stdc++.h>
using namespace std;
int a[26];
int main(){
string s; cin >> s;
for(char c : s) a[c-'A']++;
int odd = 0; char extra = ' ';
for(int i=0;i<26;i++){
if(a[i]%2 == 1){ extra = 'A'+i; odd++; }
}
if(odd > 1){
cout << "NO SOLUTION" << endl;
return 0;
}
string res;
// first half
for(int i=0;i<26;i++) res += string(a[i]/2, 'A'+i);
cout << res;
// middle character
if(odd) cout << extra;
// second half
reverse(res.begin(),res.end());
cout << res << endl;
}
Gray Code
Refer here for finding the \(n\)th Gray code.
We can turn a number to binary by checking each bit of a number.
Time and space complexity is \(O(2^n)\).
#include <bits/stdc++.h>
using namespace std;
string tobin(int n, int d){ // n = number, d = digits
string s(d,'0');
for(int i=0;i<d;i++) s[d-1-i] = '0' + bool(n&(1<<i));
return s;
}
int main(){
int n; cin >> n;
for(int i=0;i<(1<<n);i++){
cout << tobin(i^(i>>1), n) << endl;
}
}
Tower of Hanoi
This can be solved using recursion as follows:
- Move the first (n-1) disks from the source to the auxiliary tower.
- Move the last disk from the source to the destination.
- Move the (n-1) disks from the auxiliary tower to the destination.
Time and space complexity is \(O(2^n)\).
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> steps;
// l = source, m = auxiliary, r = destination, num = number of disks
void solve(int l, int m, int r, int num){
if(num==0) return;
solve(l,r,m,num-1);
steps.push_back({l,r});
solve(m,l,r,num-1);
return;
}
int main(){
int n; cin >> n;
solve(1,2,3,n);
cout << steps.size() << endl;
for(pair<int,int> x : steps) cout << x.first << " " << x.second << endl;
return 0;
}
Creating Strings
We can use STL’s std::next_permutation
to solve the problem.
Time and space complexity is \(O(n!)\).
#include <bits/stdc++.h>
using namespace std;
int main(){
string s; cin >> s;
sort(s.begin(),s.end());
vector<string> k;
do {
k.push_back(s);
} while(next_permutation(s.begin(),s.end()));
cout << k.size() << endl;
for(auto t : k) cout << t << endl;
}
Apple Division
Since \(n \le 20\), we can brute force all combinations and check if they are valid. We will use bitmasks.
Time complexity: \(O(n2^n)\).
Refer here for more details.
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; cin >> n;
int a[n]; for(int i=0;i<n;i++) cin >> a[i];
long long total = 0; for(int i=0;i<n;i++) total += a[i];
long long cur_min = 1e9;
for(int mask=0;mask<(1<<n);mask++){
long long cur = 0;
for(int i=0;i<n;i++) if(mask&(1<<i)) cur += a[i];
cur_min = min(cur_min, abs(total - 2 * cur));
}
cout << cur_min << endl;
}
Chessboard and Queens
This has appeared in the backtracking section in the book. To prune the search, we do not place queens in the same row, column or diagonal with any other queens.
#include <bits/stdc++.h>
using namespace std;
bool a[8][8];
int cnt = 0;
void solve(vector<int> n){ // n[i] = row of queen in column i
if(n.size()==8){
cnt++; return;
}
vector<bool> ok(8,true);
for(int i : n) ok[i] = false;
for(int i=0;i<8;i++){
if(!a[n.size()][i]) ok[i] = false;
}
for(int i=0;i<8;i++){
if(!ok[i]) continue;
bool cont = true;
for(int x=0;x<(int)n.size();x++){
if(abs((int)n.size()-x) == abs(i-n[x])){
cont=false; break;
}
}
if(!cont) continue;
n.push_back(i);
solve(n);
n.pop_back();
}
return;
}
int main(){
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
char c; cin >> c;
a[i][j] = (c=='.'?1:0);
}
}
solve({});
cout << cnt << endl;
}
Digit Queries
Given a \(k\), we first determine if it lies on the 1-digits, 2-digits, etc. We can do that by precomputing the number of digits after each final n-digit number.
For example, the number of n-digits is \(10^{n} - 10^{n-1}\). Hence the number of total digits after all n-digits \(f(n)\) is \(f(n) = f(n-1) + n\times(10^{n} - 10^{n-1})\). We then binary search (upper_bound
) to determine the right number of digits, find the exact number, then find the exact digit.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N = 18;
vector<ll> a(N+1,0);
vector<ll> pre(N+1,0);
ll binpow(ll a, ll p){
ll ans = 1;
while(p){
if(p&1) ans *= a;
a *= a;
p >>= 1;
}
return ans;
}
void solve(){
ll k; cin >> k; k--;
int n = upper_bound(pre.begin(),pre.end(),k) - pre.begin(); // number of digits
// minimum number with n digits = 10^(n-1)
// each number has n digits
ll left = (k - pre[n-1]);
string num = to_string(binpow(10,n-1) + left/n);
cout << num[left%n] << endl;
}
int main(){
for(int i=1;i<=N;i++){
a[i] = (binpow(10,i) - binpow(10,i-1)) * i;
pre[i] = pre[i-1] + a[i];
}
int q; cin >> q;
while(q--) solve();
}
Grid Paths
An almost equivalent version has appeared in the backtracking section in the book, page 52. Apart from symmetric paths, the other optimization techniques remains the same.
We terminate a search when:
- We have found a valid path
- We should have terminated but haven’t (we reached the destination cell/we walked 48 steps)
- We hit a wall but two sides are empty (there is no way we can travel both sides)
#include <bits/stdc++.h>
using namespace std;
bool board[7][7];
char s[48];
int ans = 0;
inline bool valid(int x, int y){
return x >= 0 && y >= 0 && x < 7 && y < 7 && !board[x][y];
}
void solve(int x, int y, int steps){
// we are not on a valid square
if(!valid(x,y)) return;
// if we are at the end, we have found a valid path
if(x == 6 && y == 0 && steps == 48){ ans++; return; }
// we should have terminated but haven't
if((x == 6 && y == 0)|| steps == 48){ return; }
// if two sides are seperated, then return
if(!valid(x-1,y) && !valid(x+1,y) && valid(x,y+1) && valid(x,y-1)) return;
if(valid(x-1,y) && valid(x+1,y) && !valid(x,y+1) && !valid(x,y-1)) return;
board[x][y] = true;
// the path is not set
if(s[steps] == '?') {
solve(x+1,y,steps+1);
solve(x-1,y,steps+1);
solve(x,y+1,steps+1);
solve(x,y-1,steps+1);
}
// the path is set
else if(s[steps] == 'U') solve(x-1,y,steps+1);
else if(s[steps] == 'D') solve(x+1,y,steps+1);
else if(s[steps] == 'L') solve(x,y-1,steps+1);
else if(s[steps] == 'R') solve(x,y+1,steps+1);
board[x][y] = false;
}
int main(){
for(int i=0;i<48;i++) cin >> s[i];
solve(0,0,0);
cout << ans << endl;
}