Given a set *S* of *n* distinct integers, print the size of a maximal subset *S’* of *S* where the sum of any 2 numbers in *S’* are not evenly divisible by* k*.

time complexity is O(N)

space complexity is O(N)

This is by all means not an easy task and is also reflected by the high failure ratio of the participants. For a sum of two numbers to be evenly divisible by k the following condition has to hold. If the remainder of *N1%k == r* then *N2%k = k-r* for* N1+N2 % k == 0*. Let us calculate the set of all numbers with a remainder of *r* and *k-r *and pick the larger set. If the remainder is half of k such as 2 % 4 = 2 or exactly k such as 4 % 4 = 0, just one number from each of these sets can be contained in* S’.*

def solveSubset(S, k, n): r = [0] * k for value in S: r[value%k] += 1 result = 0 for a in xrange(1, (k+1)//2): result += max(r[a], r[k-a]) if k % 2 == 0 and r[k//2]: result += 1 if r[0]: result += 1 return result n, k = map(int, raw_input().split()) S = map(int, raw_input().split()) print solveSubset(S, k, n)

use std::io; fn get_numbers() -> Vec<u32> { let mut line = String::new(); io::stdin().read_line(&mut line).ok().expect("Failed to read line"); line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect() } fn calculate_nondivisible(a: Vec<u32>, n: usize, k: usize) -> u32 { let mut result = 0; let mut r = vec![0; k]; for val in a { r[(val as usize)%k] += 1; } for idx in 1..(k+1)/2 { result += std::cmp::max(r[idx as usize], r[(k-idx) as usize]); } if k % 2 == 0 && r[k/2] != 0 { result += 1; } if r[0] != 0 { result += 1; } result } fn main() { let line = get_numbers(); let a = get_numbers(); println!("{}", calculate_nondivisible(a, line[0] as usize, line[1] as usize) ); }

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

For each city, determine its distance to the *nearest* space station and *print the maximum* of these distances.

time complexity is O(N)

space complexity is O(N)

This is a two pass algorithm. First, measure the distance to the last station on the left. And on the second pass measure the distance to the nearest station on the right. Pick the minimum of both values. Remember that the first and last position are not necessarily stations.

use std::io; use std::cmp; fn get_numbers() -> Vec<u32> { let mut line = String::new(); io::stdin().read_line(&mut line).ok().expect("Failed to read line"); line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect() } fn find_distance(c: Vec<u32>, n: usize) -> u32 { let mut solution = 0; let mut distances = vec![n as u32; n]; // first pass let mut last_seen = 0; let mut seen_one = false; for i in 0..n { if c[i] == 1 { seen_one = true; last_seen = 0; } else { last_seen += 1; } if seen_one { distances[i] = last_seen; } } // second pass let mut last_seen = 0; let mut seen_one = false; for i in (0..n).rev() { if c[i] == 1 { seen_one = true; last_seen = 0; } else { last_seen += 1; } solution = cmp::max(solution, match seen_one { true => cmp::min(last_seen, distances[i]), false => distances[i], } ); } solution } fn main() { let line = get_numbers(); let n = line[0] as usize; let c = get_numbers(); let mut v = vec![0; n]; for station in c { v[station as usize] = 1; } println!("{}", find_distance(v, n)); }

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

There are two kangaroos on an x-axis ready to jump in the positive direction (i.e, toward positive infinity). The first kangaroo starts at location x1 and moves at a rate of v1 meters per jump. The second kangaroo starts at location x2 and moves at a rate of v2 meters per jump. Given the starting locations and movement rates for each kangaroo, can you determine if they’ll ever land at the same location at the same time?

time complexity is O(1)

space complexity is O(1)

There is no need to simulate the movement. We can reason that the two kangaroos either meat at the smallest common multiply or never.

use std::io; fn get_numbers() -> Vec<u32> { let mut line = String::new(); io::stdin().read_line(&mut line).ok().expect("Failed to read line"); line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect() } fn main() { let numbers = get_numbers(); let x1 = numbers[0]; let v1 = numbers[1]; let x2 = numbers[2]; let v2 = numbers[3]; if x1 == x2 && v1 == v2 { println!("YES"); } else if x1 == x2 && v1 > v2 { println!("NO"); } else if x1 <= x2 && v1 <= v2 { println!("NO"); } else { if (x2 - x1) % (v1 - v2) == 0 { println!("YES"); } else { println!("NO"); } } }

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

A jail has N prisoners, and each prisoner has a unique id number,S , ranging from 1 to N. There are M sweets that must be distributed to the prisoners. But wait—there’s a catch—the very last sweet S is poisoned! Can you find and print the ID number of the last prisoner to receive a sweet so he can be warned?

time complexity is O(1)

space complexity is O(1)

This challenge is painlessly trivial.

use std::io; fn get_number() -> u32 { let mut line = String::new(); io::stdin().read_line(&mut line).ok().expect("Failed to read line"); line.trim().parse::<u32>().unwrap() } fn get_numbers() -> Vec<u32> { let mut line = String::new(); io::stdin().read_line(&mut line).ok().expect("Failed to read line"); line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect() } fn solve_prisoner(n: u32, m: u32, s: u32) -> u32 { ((s - 1 + m - 1 ) % n) +1 } fn main() { let t = get_number(); for _ in 0..t { let line = get_numbers(); println!("{}", solve_prisoner(line[0], line[1], line[2])); } }

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

Emma is playing a new mobile game involving clouds numbered from 1 to n. There are two types of clouds, ordinary clouds and thunderclouds. The game ends if Emma jumps onto a thundercloud, but if she reaches the last cloud, she wins the game!

time complexity is O(N)

space complexity is O(N)

Theoretically your solution can depend on the fact that the win condition is guaranteed, but I don’t like such solutions. Here I present a semi-DP approach that keeps track of the optimal number of jumps it takes to reach each cloud.

use std::io; use std::cmp; fn get_number() -> u32 { let mut line = String::new(); io::stdin().read_line(&mut line).ok().expect("Failed to read line"); line.trim().parse::<u32>().unwrap() } fn get_numbers() -> Vec<u32> { let mut line = String::new(); io::stdin().read_line(&mut line).ok().expect("Failed to read line"); line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect() } fn calculate_jumping(a: Vec<u32>, n: usize) -> u32{ let mut v = vec![100; n]; v[0] = 0; for i in 1..n { //println!("{} {} {:?}", i, a[i], v); if a[i] == 1 { continue; } if i == 1 { v[i] = v[i-1] + 1; } else { v[i] = cmp::min(v[i-1], v[i-2]) + 1; } } v[n-1] } fn main() { let n = get_number() as usize; let a = get_numbers(); println!("{}", calculate_jumping(a, n) ); }

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

Aerith is playing a cloud game! In this game, there are clouds numbered sequentially from 1 to n. Each cloud is either an *ordinary cloud* or a *thundercloud*. Given the values of *n* and* k* the configuration of the clouds, can you determine the final value of *e* after the game ends?

Jumping on the Clouds: Revisited

time complexity is O(N)

space complexity is O(1)

Simulate the game in a loop.

#!/bin/python def solveCloudRevisited(c, n, k): pos = 0 cnt = 0 while cnt == 0 or pos != 0: pos += k pos %= n if c[pos] == 0: cnt += 1 else: cnt += 3 return 100 - cnt if __name__ == '__main__': n,k = map(int,raw_input().strip().split(' ')) c = map(int,raw_input().strip().split(' ')) print solveCloudRevisited(c, n, k)

use std::io; fn get_numbers() -> Vec<u32> { let mut line = String::new(); io::stdin().read_line(&mut line).ok().expect("Failed to read line"); line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect() } fn calculate_jumping(a: Vec<u32>, n: usize, k: usize) -> u32 { let mut e = 0; let mut pos = 0; while e == 0 || pos != 0 { e += match a[pos] { 0 => 1, 1 => 3, _ => panic!("invalid input"), }; pos += k; pos %= n; } 100 - e } fn main() { let line = get_numbers(); let (n, k) = (line[0], line[1]); let a = get_numbers(); println!("{}", calculate_jumping(a, n as usize, k as usize) ); }

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

John Watson performs an operation called a *right circular rotation* on an array of integers.

time complexity is O(Q)

space complexity is O(1)

Calculate the offset for every query. Watch out for index overflows and negative modulo.

use std::io; fn get_number() -> u32 { let mut line = String::new(); io::stdin().read_line(&mut line).ok().expect("Failed to read line"); line.trim().parse::<u32>().unwrap() } fn get_numbers() -> Vec<u32> { let mut line = String::new(); io::stdin().read_line(&mut line).ok().expect("Failed to read line"); line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect() } fn main() { let line = get_numbers(); let (n,k,q) = (line[0], line[1], line[2]); let a = get_numbers(); for _ in 0..q { let m = get_number(); let idx = ((m-(k%n)+n)%n) as usize; println!("{}", a[idx]); } }

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

Alice and Bob each created one problem for HackerRank. A reviewer rates the two challenges, awarding points on a scale from 1 to 100 for three categories: *problem clarity*, *originality*, and *difficulty*.

time complexity is O(1)

space complexity is O(1)

This is a warmup. Follow specification.

use std::io; use std::cmp::Ordering; fn get_numbers() -> Vec<u32> { let mut line = String::new(); io::stdin().read_line(&mut line).ok().expect("Failed to read line"); line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect() } fn main() { let a = get_numbers(); let b = get_numbers(); let mut alice = 0; let mut bob = 0; for idx in 0..3 { match a[idx].cmp(&b[idx]) { Ordering::Less => bob += 1, Ordering::Greater => alice += 1, Ordering::Equal => {}, } } println!("{} {}", alice, bob); }

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

You are given an array of n integers and a positive integer, k. Find and print the number of (i,j) pairs where i < j and ai + aj is evenly divisible by k.

time complexity is O(N^2)

space complexity is O(1)

Brute force search.

n,k = raw_input().strip().split(' ') n,k = [int(n),int(k)] a = map(int,raw_input().strip().split(' ')) count=0 for i in xrange(len(a)): for j in xrange(i+1,len(a)): if (a[i]+a[j]) % k == 0: count+=1 print count

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>

In the previous parts of the series we look at Trivial cases and Non-virtual inheritance. Now, it is time to look at the actual content of the series. I repeat the citation we are verifying here:

Whenever a class itself

contains virtual functions or overrides virtual functions from a parent classthe compiler builds a vtable for that class. This means thatnot all classes have a vtablecreated for them by the compiler. The vtable contains function pointers that point to the virtual functions in that class. There can only be one vtable per class, and all objects of the same class will share the same vtable. [1]

We have shown that classes without a virtual function indeed contain no virtual pointer and no virtual table is constructed. A virtual table is an array of **function pointers** although other data types are also possible. The layout is generally compiler-specific (or ABI-specific where multiple C++ compilers share an ABI) and somewhat stable. All the virtual function tables are in the memory associated with your process. In case of GDB all your virtual function tables are stored in **read-only memory** which protects it from unintentional overwrites. The functions themselves (their assembly instructions) are stored in the .text section of the elf binary.

class Base { public: virtual ~Base() { } virtual void method() = 0; }; class Derived: public Base{ public: virtual ~Derived() {} void method() {} }; int main() { Base* m = new Derived(); delete m; }

(gdb) info vtbl m vtable for 'Base' @ 0x400af0 (subobject @ 0x603010): [0]: 0x400986 [Derived::~Derived()] [1]: 0x4009c0 [Derived::~Derived()] [2]: 0x4009e6 [Derived::method()]

The entries for virtual destructors are actually pairs of entries. The first destructor, called the *complete object destructor*, performs the destruction without calling delete() on the object. The second destructor, called the *deleting destructor*, calls delete() after destroying the object. Both destroy any virtual bases; a separate, non-virtual function, called the base object destructor, performs destruction of the object but not its virtual base subobjects, and does not call delete().

Non-virtual functions are dispatched statically, as we have shown in the first blog entry, and therefore do not require a entry in the virtual table.

Let us examine where the virtual table is located. We will ignore many intricacies of ELF that are not relevant for this explanation. First, let us examine the borders of each section in the file.

readelf --sections a.out There are 36 section headers, starting at offset 0x6420: Section Headers: [Nr] Name Type Address Offset Size EntSize Flags Link Info Align [ 0] NULL 0000000000000000 00000000 0000000000000000 0000000000000000 0 0 0 [13] .text PROGBITS 00000000004007a0 000007a0 0000000000000302 0000000000000000 AX 0 0 16 [14] .fini PROGBITS 0000000000400aa4 00000aa4 0000000000000009 0000000000000000 AX 0 0 4 [15] .rodata PROGBITS 0000000000400ac0 00000ac0 00000000000000d0 0000000000000000 A 0 0 32 Key to Flags: W (write), A (alloc), X (execute), M (merge), S (strings), l (large) I (info), L (link order), G (group), T (TLS), E (exclude), x (unknown) O (extra OS processing required) o (OS specific), p (processor specific)

The address space boundaries of this particular ELF binary are as follows:

- [0x04007a0-0x0400aa4] – is the text section containing
**disassembly of functions**(0x400986) ~~[0x0400aa4-0x0400ac0]~~- [0x0400ac0-0x0400b90] – is the read only section containing the
**vtables**(0x400af0)

Let us look at the objdump of the read only memory containing the virtual table. We will later compare it with the disassembly from gdb. Somewhere we should see the value 0x400af0.

objdump -s -j .rodata ./a.out ./a.out: file format elf64-x86-64 Contents of section .rodata: 400ac0 01000200 00000000 00000000 00000000 ................ 400ad0 00000000 00000000 00000000 00000000 ................ 400ae0 00000000 00000000 600b4000 00000000 ........`.@..... 400af0 86094000 00000000 c0094000 00000000 ..@.......@..... 400b00 e6094000 00000000 00000000 00000000 ..@............. 400b10 00000000 00000000 00000000 00000000 ................ 400b20 00000000 00000000 800b4000 00000000 ..........@..... 400b30 32094000 00000000 60094000 00000000 2.@.....`.@..... 400b40 80074000 00000000 37446572 69766564 ..@.....7Derived 400b50 00000000 00000000 00000000 00000000 ................ 400b60 f0206000 00000000 480b4000 00000000 . `.....H.@..... 400b70 800b4000 00000000 34426173 65000000 ..@.....4Base... 400b80 90206000 00000000 780b4000 00000000 . `.....x.@.....

When looking at the line 0x400af0 we notice that the values are not what we expect. The byte order is reversed in objdump compared to the disassembly. The raw bytes are [0x86, 0x9, 0x40, 0x0] with big endian byte order this results in 0x400986 and in little endian byte order this results in 0x860940. Is it the same we are seeing in GDB?

(gdb) x/6x 0x400af0 0x400af0 [_ZTV7Derived+16]: 0x00400986 0x00000000 0x004009c0 0x00000000 0x400b00 [_ZTV7Derived+32]: 0x004009e6 0x00000000

It indeed is. Those are out function pointers.

Amongst other things this section of the ELF binary contains the disassembly of all the virtual (and non-virtual functions). If you look at their addresses you will realise that the values indeed correspond to the entries in the virtual table.

objdump -d a.out a.out: file format elf64-x86-64 Disassembly of section .text: 0000000000400986 [_ZN7DerivedD1Ev] 00000000004009c0 [_ZN7DerivedD0Ev] 00000000004009e6 [_ZN7Derived6methodEv]

(gdb) disas 0x400986 Dump of assembler code for function Derived::~Derived(): 0x0000000000400986 [+0]: push %rbp 0x0000000000400987 [+1]: mov %rsp,%rbp 0x000000000040098a [+4]: sub $0x10,%rsp 0x000000000040098e [+8]: mov %rdi,-0x8(%rbp) 0x0000000000400992 [+12]: mov -0x8(%rbp),%rax 0x0000000000400996 [+16]: movq $0x400af0,(%rax) 0x000000000040099d [+23]: mov -0x8(%rbp),%rax 0x00000000004009a1 [+27]: mov %rax,%rdi 0x00000000004009a4 [+30]: callq 0x400932 [Base::~Base()] 0x00000000004009a9 [+35]: mov $0x0,%eax 0x00000000004009ae [+40]: test %eax,%eax 0x00000000004009b0 [+42]: je 0x4009be [Derived::~Derived()+56] 0x00000000004009b2 [+44]: mov -0x8(%rbp),%rax 0x00000000004009b6 [+48]: mov %rax,%rdi 0x00000000004009b9 [+51]: callq 0x400730 [_ZdlPv@plt] 0x00000000004009be [+56]: leaveq 0x00000000004009bf [+57]: retq End of assembler dump.

Why is it important that the virtual table is in the read only memory? The virtual pointer is located at the beginning of each object. It is possible to hack this pointer to point to any other table (maliciously created by an adversary). Is it possible to manipulate the table itself? If this would be possible we would be able to corrupt ALL objects.

int main() { Derived* m = new Derived(); long ***mVtable = (long ***)&m; printf("Derived VTABLE: %p\n", **mVtable); printf("First entry of Derived VTABLE: %p\n", (void*) mVtable[0][0][0]); printf("Second entry of Derived VTABLE: %p\n", (void*) mVtable[0][0][1]); printf("Third entry of Derived VTABLE: %p\n", (void*) mVtable[0][0][2]); printf("Address of FCT: %p\n", (void*) &assignableFct1); mVtable[0][0][2] = (long)&assignableFct1; }

Derived VTABLE: 0x400af0 First entry of Derived VTABLE: 0x400986 Second entry of Derived VTABLE: 0x4009c0 Third entry of Derived VTABLE: 0x4009e6 Address of FCT: 0x4007ad Segmentation fault

The code above might look a bit complicated but it is not. mVtable is dereferenced three times to reach the first entry in the vtable.

- the value of the pointer is the address of the variable on the stack
- (long ***) 0x7fffffffe3b0

- the first dereference of mVtable gives us the address of the actual object on the heap
- (long **) 0x603010

- the second dereference of of mVtable gives us the address of the vtable we are looking for
- (long *) 0x400af0 [vtable for Derived+16]

- the third dereference of of mVtable gives us the address of the first entry in the vtable
- (void *) 0x400986 [Derived::~Derived()]

Fortunately this function will segfault. **Writing over read only memory is not allowed**. Pfuh.

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

]]>