satylogin's blog

By satylogin, history, 3 years ago, In English

I wanted to write and keep a segment tree implementation for myself, that I could use more generally (all reasonable data types, and all reasonable operations). I finally decided to write one and add it to cp-lib.

The core struct for now is:

pub struct SegTree<T, F>
where
    T: Clone + Copy,
    F: Fn(T, T) -> T,
{
    n: i32,
    default: T,
    cell: Vec<T>,
    lazy: Vec<T>,
    op: F,
}

And usage:

let mut tree = SegTree::new(10, i32::MIN, std::cmp::max);
tree.insert(1, 10);
tree.insert(2, 20);
assert_eq!(tree.query(1, 10), 20);

tree.insert_range(3, 6, 10);
assert_eq!(tree.query(5, 10), 10);

Where op is the operation that the segment tree performs (min, max, gcd, or something custom), and default is the value the should be returned as query default and gets stored during initialization.

The major benefit is that it allows for me to write more complicated segtree rather easily,
eg:
for problem: https://codeforces.me/contest/1557/problem/D
my solution (https://codeforces.me/contest/1557/submission/154901530) uses

let mut seg_tree = SegTree::new(
    points.len(),
    (0, 0),
    |left: (usize, usize), right: (usize, usize)| if left.1 > right.1 { left } else { right },
);

Sharing the full implementation here in case someone needs it.

I will keep on modifying it as needed. In case anyone do decide to use it and find some bugs, or have a feature request, do let me know.

Full text and comments »

  • Vote: I like it
  • +26
  • Vote: I do not like it

By satylogin, history, 3 years ago, In English

I started implementing a generic multiset that I could use for problems since rust std lacks one. I have an initial implementation for it: https://github.com/satylogin/cp-lib/blob/main/src/ds/multiset.rs

I will keep on adding methods as and when they are needed. Sharing here in case someone needs it. In case you do decide to use it and find some bugs, or have a feature request, do let me know.

Full text and comments »

  • Vote: I like it
  • +21
  • Vote: I do not like it

By satylogin, history, 3 years ago, In English

I was trying to come up with a generic implementation of gcd in rust that I could use by copy pasting without worrying about data type. I finally have something useful that works on sane data types.

I am sharing the implementation in case someone needs it

/// Calculates gcd for same types T that implements required traits.
/// The current implementation is tested on i32, u32, i64, u64, usize, isize
/// For any other type T, the behaviour is undefined
pub fn gcd<T>(a: T, b: T) -> T
where
    T: std::cmp::PartialEq + std::ops::Rem<Output = T> + Default + Copy,
{
    // for our required types, default evalutaes to 0 at compile time.
    // and thus have 0 cost abstraction.
    if b == T::default() {
        a
    } else {
        gcd(b, a % b)
    }
}

I am uploading such generic things in my repo as and when I need something: https://github.com/satylogin/cp-lib/

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it

By satylogin, 3 years ago, In English

I was trying out problem https://codeforces.me/contest/1526/problem/D, and its implementation required us to have next_permutation. I couldn't find any reference for it in rust std lib, and since we can't import crates, I wrote a generic implementation that I could reuse across problems.

Just sharing this in case someone needs this:


/// Finds next lexographic permutation of given slice. If next larger permutation exists, /// the slice would then have this and the return value would be true. If the slice /// represents the largest lexicographic sequence, it updates the slice with smallest one /// and returns false. /// The type whose permutation is required must implement [Ord](std::cmp::Ord) trait. pub fn next_permutation<T>(arr: &mut [T]) -> bool where T: std::cmp::Ord, { use std::cmp::Ordering; // find 1st pair (x, y) from back which satisfies x < y let last_ascending = match arr.windows(2).rposition(|w| w[0] < w[1]) { Some(i) => i, None => { arr.reverse(); return false; } }; // In the remaining later segment, find the one which is just // larger that the index found above. // SAFETY: unwrap_err whill not panic since binary search will // will never succeed since we never return equal ordering let swap_with = arr[last_ascending + 1..] .binary_search_by(|n| match arr[last_ascending].cmp(n) { Ordering::Equal => Ordering::Greater, ord => ord, }) .unwrap_err(); arr.swap(last_ascending, last_ascending + swap_with); arr[last_ascending + 1..].reverse(); true }

I added this on github: https://github.com/satylogin/cp-lib

I will probably add couple more algo and ds there as and when needed.

Submission for above problem in case someone is interested: https://codeforces.me/contest/1526/submission/119132920

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it

By satylogin, history, 6 years ago, In English

GeekHaven IIIT Allahabad is back with its annual contest. The contest is prepared by the members of the Competitive Coding Wing. This time the contest will be hosted on codechef.

This time there is cash prize worth 4000 for winners. To be eligible for the prizes, please fill the form

The contest will take place on Nov 2 2018 Friday at 10:00 PM (IST)

The contest duration is 3 hrs.

Contest link: GeekHaven Contest

We will be posting editorials on the same thread. For any other queries don't hesitate to contact the organisers. Their contact details are mentioned on the poster.

Hoping for a huge participation !!!

Editorial Link: https://discuss.codechef.com/questions/139405/geekhaven-contest

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

By satylogin, history, 7 years ago, In English

Hello guys :)

Competitive coding wing of GEEKHAVEN IIIT Allahabad is organising a contest on hackerearth on saturday 12th august. The contest is mainly centred for second year students, although I hope that everyone will be able to enjoy the problem set. The contest is prepared by the members of the wing.

It has Balanced problemset with some interesting problems to simulate the grey cells and great to start the weekend.

The link of the contest is — https://www.hackerearth.com/challenge/college/codemania-20/

The contest duration is 24 HRS.

I hope for an huge participation. :)

UPD: (EDITORIAL)

1. https://www.hackerearth.com/challenge/college/codemania-20/algorithm/cross-the-stairs/
hint
2. https://www.hackerearth.com/challenge/college/codemania-20/algorithm/honey-bees/
hint
3. https://www.hackerearth.com/problem/algorithm/modern-game/
hint
4. https://www.hackerearth.com/problem/algorithm/an-excursion-in-mathematics/
hint
5. https://www.hackerearth.com/problem/algorithm/coin-toss/
hint
6. https://www.hackerearth.com/problem/algorithm/ben-and-the-omnitrix/
hint
7. https://www.hackerearth.com/practice/basic-programming/input-output/basics-of-input-output/practice-problems/algorithm/play-with-numbers-2/
Hint
8. https://www.hackerearth.com/problem/algorithm/alex-and-the-substring/, https://www.hackerearth.com/problem/algorithm/alex-and-the-substring-med/
hint
9. https://www.hackerearth.com/practice/data-structures/disjoint-data-strutures/basics-of-disjoint-data-structures/practice-problems/algorithm/owl-fight/
10. https://www.hackerearth.com/practice/basic-programming/implementation/basics-of-implementation/practice-problems/algorithm/clock-1/
hint

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

By satylogin, history, 8 years ago, In English

I realised that there is only one way improve one's skill, and that is through practice. So I decided to practice more topics and more problems on codeforces and different judges. This is simply a daily record for what I did through my vacation.

I also want to tell you about stopstalk.com . It is a good site to make and keep you daily coding record.

16 MAY 2017

Problems Solved -
1. http://codeforces.me/problemset/problem/535/D
This was a simple problem and it used Z function for prefix length calculation
solution linkhttp://codeforces.me/contest/535/submission/27152004
2. http://codeforces.me/problemset/problem/551/B
Although the problem was simple, I had some trouble in understanding the language of the problem. It took time more than required.
solution linkhttp://codeforces.me/contest/551/submission/27160921


Participated Contest -

I participated in a virtual contest ( Round 308 DIV 2 ). I was able to solve all the problems, but then last problem was accepted just 2 min before the contest ended.

A. http://codeforces.me/problemset/problem/552/A
The problem was fairly simple, but then rather than simply adding the area, I made a 2-D hash map. Guess I have to practice a little more for problem A.
solution linkhttp://codeforces.me/contest/552/submission/27165795
B. http://codeforces.me/problemset/problem/552/B
The problem was mathematical. I solved it by forming a series. Got one WA for not using long long.
solution linkhttp://codeforces.me/contest/552/submission/27165912
C. http://codeforces.me/problemset/problem/552/C
I solved the problem using meet in middle. But the editorial talked about an another wonderful way to solve that. Do watch the editorial solution. It is an excellent concept in itself.
solution linkhttp://codeforces.me/contest/552/submission/27166275
D. http://codeforces.me/problemset/problem/552/D
This was another interesting problem to solve. I used concept of slopes to generate triangle. Got 4 WA. Was not taking care of slope sign and was not handling 0 slope and inf slope cases.
solution linkhttp://codeforces.me/contest/552/submission/27166893
E. http://codeforces.me/problemset/problem/552/E
Pretty interesting problem to solve both by greedy and by DP. I used the later N*N approach. Initially thought of using multiplication as boundaries, but then didn't wanted to take risk. Got 4 WA because of simple mistakes in the loops. Got accepted just before 2 min from end.
solution linkhttp://codeforces.me/contest/552/submission/27167519

17 MAY 2017

Solved very few problems. Found a lot of problems hard to solve.

Problems Solved -
1. http://codeforces.me/problemset/problem/551/C
It was a good problem of binary search. Although I found it a little hard for problem C Div 2. Guess I have practice still more. It used an standard NlogN solution using binary search where we have to binary search over the completion time of the task and then check the users required. Good problem for practice.
solution link — http://codeforces.me/contest/551/submission/27175198
2. http://codeforces.me/problemset/problem/549/A
Fairly easy problem. Requires direct implementation
solution link — http://codeforces.me/contest/549/submission/27181042
3. http://codeforces.me/problemset/problem/534/E
very good problem for practice. I was missing a lot of corner cases while solving. Had to search for a method to find mismatch in logN time in the array. I think this problem was worth solving.
solution link — http://codeforces.me/contest/534/submission/27184116
Problems Unsolved -
1. http://codeforces.me/problemset/problem/534/F
2. http://codeforces.me/contest/549/problem/H
It would be a great help if someone could help me with the unsolved problems.

18 MAY 2017

Problems Solved -

I solved some simple problems on hackerearth and URI. One problem that I liked was from URI —

1. https://www.urionlinejudge.com.br/judge/en/problems/view/1469
This was a good problem where we had to swap nodes. I used map for mapping and index function and an inverse index function for getting position of a node and getting value at any position. for swapping, I swapped those two.
solution link — https://code.hackerearth.com/a4c9b2Y

Then some problems on codeforces

1. http://codeforces.me/problemset/problem/549/H
Finally solved the matrix problem. Used binary search for reducing the size of squares.
solution link — http://codeforces.me/contest/549/submission/27189164
2. http://codeforces.me/problemset/problem/519/A
Direct implementation
solution link — http://codeforces.me/contest/519/submission/27193319
3. http://codeforces.me/problemset/problem/519/B
Direct implementation
solution link — http://codeforces.me/contest/519/submission/27201264
4. http://codeforces.me/problemset/problem/519/C
Turned out to be easy for problem C. Just travel over one possible value, then find the value of other and then maximise the sum.
solution link — http://codeforces.me/contest/519/submission/27201384
5. http://codeforces.me/problemset/problem/519/D
Had fun while solving this. Used map to store pairs of character and prefix sum values. Then used a linear algorithm to add values for all location while deleting previously occurred nodes. Did in NlogN.
solution link — http://codeforces.me/contest/519/submission/27202224
Problems unsolved -
1. http://codeforces.me/problemset/problem/519/E

19 MAY 2017

I only participated in a virtual contest on URI. Few of the good problems were —

1. https://www.urionlinejudge.com.br/judge/en/problems/view/2049
Hint
2. https://www.urionlinejudge.com.br/judge/en/problems/view/1923
Hint
3. https://www.urionlinejudge.com.br/judge/en/problems/view/1580
Hint

20 MAY 2017

Today I solved problems on snackdown qualifiers and hackerearth circuits. In night, I participated in round 415 DIV 2. The results were not very good. Was only able to solve 3 problems. I feel like I have difficulty with interactive problems. Will have to practice more.

Apart from the contests, I solved an extra problem on hackerrank.

  1. https://www.hackerrank.com/challenges/kth-ancestor
Hint

21 MAY 2017

Today I practise some problems on codeforces and spoj.

1. http://www.spoj.com/problems/LCA/
Hint
2. http://codeforces.me/problemset/problem/192/E
Hint
3. http://codeforces.me/problemset/problem/556/A
Hint
4. http://codeforces.me/problemset/problem/556/B
Hint
5. http://codeforces.me/problemset/problem/556/C
Hint
6. http://codeforces.me/problemset/problem/556/D
Hint

22 MAY 2017

Today was an extremely bad day for me. I participated in a virtual contest and was able to solve only 2 problems. Realised how bad I am at geometry. So tomorrow is going to be an extensive practice session. I also solved one problem on hackerearth circuits. A bad day :(

23 MAY 2017

Today I solved a few problems and participated in a virtual contest. Guess something went wrong with CF. In the middle of virtual contest, It dumped me out of the contest, and when 45 min were left, It again brought back me in. I solved One problem on hackerearth circuits.

solved problems
1. http://codeforces.me/problemset/problem/471/A
Hint
2. http://codeforces.me/problemset/problem/471/B
Hint
3. http://codeforces.me/problemset/problem/471/C
Hint
4. http://www.codeforces.com/problemset/problem/471/D
Hint
5. http://codeforces.me/problemset/problem/208/E
Hint
6. https://www.hackerrank.com/challenges/inverse-rmq
Hint

24 MAY 2017

Still doing hackerearth circuits. Unable to do consecutive remainder. Still have to practice more maths.

25 MAY 2017

Practiced some easy problems on hackerearth and codeforces. The problems that I practiced on hackerearth were very easy. I cannot say the same for codeforces. Today's question were a bit harder.

1. http://codeforces.me/problemset/problem/609/E
Hint
2. http://codeforces.me/problemset/problem/519/E
Hint
3. http://codeforces.me/problemset/problem/560/C
Hint
4. http://codeforces.me/problemset/problem/560/D
Hint
5. http://codeforces.me/problemset/problem/560/E
Hint

26 MAY 2017

1. https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/practice-problems/algorithm/little-monks-interviews/
Hint
2. https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/practice-problems/algorithm/rjit-need-leaves/
Hint
3. https://www.codechef.com/problems/COOK82D
Hint

27 MAY 2017

1. http://codeforces.me/problemset/problem/811/B
Hint
2. http://codeforces.me/problemset/problem/558/B
Hint
3. http://codeforces.me/problemset/problem/557/A
4. http://codeforces.me/problemset/problem/557/B
Hint
5. http://codeforces.me/problemset/problem/557/C
Hint
6. http://codeforces.me/problemset/problem/811/A
Hint
7. http://codeforces.me/problemset/problem/811/C
Hint

28 MAY 2017

1. https://www.codechef.com/problems/DIVGAME
Hint
2. https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/practice-problems/algorithm/little-monk-and-his-toy-story/
Hint
3. https://www.hackerearth.com/problem/algorithm/even-sum/
Hint
4. https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/practice-problems/algorithm/little-monk-and-library/
Hint

29 MAY 2017

1. https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/sorted-string/
Hint
2. https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/caesars-cipher-1/
Hint
3. https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/marut-and-strings-4/
Hint
4. https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/secret-messages/
Hint
5. https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/remove-duplicates-3/
Hint
6. https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/lexical-analyzer-3/
Hint
7. https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/ashish-and-binary-matrix-1/
Hint
8. https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/palindromes-3/
Hint
9. https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/xenny-and-partially-sorted-strings-7/
Hint

30 MAY 2017

1. https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/find-the-substrings/
Hint
2. https://www.hackerearth.com/problem/algorithm/benny-and-her-school-reports/
Hint
3. http://codeforces.me/problemset/problem/558/C
HInt
4. http://codeforces.me/problemset/problem/558/D
Hint

31 MAY 2017

1. http://codeforces.me/problemset/problem/558/E
Hint
2. http://codeforces.me/problemset/problem/567/A
Hint
3. http://codeforces.me/problemset/problem/567/B
Hint
4. http://codeforces.me/problemset/problem/567/C

1 JUNE 2017

Just gave the contest on codeforces

2 JUNE 2017

1. http://codeforces.me/problemset/problem/577/C
Hint
2. http://codeforces.me/problemset/problem/577/B
Hint
3. http://codeforces.me/problemset/problem/577/A
Hint
4. http://codeforces.me/problemset/problem/567/E
Hint

3 JUNE 2017

Doing Codechef Long Challange

4 JUNE 2017

1. https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/missing-alphabets-1/
Hint
2. https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/change-string/
Hint

5 JUNE 2017

Did codechef long and participated in education codeforces round

6 JUNE 2017

1. http://codeforces.me/problemset/problem/570/A
Hint
2. http://codeforces.me/problemset/problem/221/B
Hint
3. http://codeforces.me/problemset/problem/121/A
Hint

7 JUNE 2017

Did contest on codeforces

8 JUNE 2017

1. http://codeforces.me/problemset/problem/570/C
Hint
2. http://codeforces.me/problemset/problem/456/D
Hint

9 JUNE 2017

1. http://codeforces.me/problemset/problem/13/E
Hint
2. http://codeforces.me/problemset/problem/404/A
Hint

10 JUNE 2017

Practised some simple problems on CF.

11 JUNE 2017

Solved MKTHNUM on spoj.

1. http://codeforces.me/problemset/problem/579/C
Hint

Full text and comments »

  • Vote: I like it
  • +79
  • Vote: I do not like it