livw's blog

By livw, history, 2 months ago, In English,

Hi everyone.

This is my template for debugging in C++. I was inspired by Tourist's source code and modified it to my style. Here is it:

Template

To debug, just type: debug(x, y, z...). It requires C++ 11 or above.

It can work with:

  • Primitive data types: bool, int, long long, float, ...

  • std::pair, std::string

  • Collection types: std::vector, std::map, std::set, ...
  • Expressions

It also support multiple arguments.


How to use

Primitive data types:

bool a = true;
debug(a);

int b = 1;
float c = 2.5;
long long d = LLONG_MAX;
char e = 'e';
debug(a, b, c, d, e);

Output:
'[a] = [true]'
'[a, b, c, d, e] = [true, 1, 2.5, 9223372036854775807, 'e']'

std::pair and std::string:

pair<int, int> a = {1, 2};
pair<string, bool> b = {"abcd", false};
pair<char, float> c = {'x', 0.5};
string d = "This is a string";
pair<int, pair<int, int> > e = {1, {2, 3}};
debug(a, b, c, d, e);

Output:
'[a, b, c, d, e] = [{1, 2}, {"abcd", false}, {'x', 0.5}, "This is a string", {1, {2, 3}}]'

Note: You should only debug a pair of simple data types. For example, the debug won't work if one of pair's elements is collection type (std::vector, std::map, std::set...).


Collection types:

Basically, the debug works with collections types which you can iterate by for (auto i: a). So the debugger won't work with collection types like std::queue or std::stack.

vector<int> a = {1, 2, 3, 4};
set<int> b = {1, 2, 2, 3, 3, 4, 4, 5};
map<string, int> c;
c["string 1"] = 1;
c["string 2"] = 2;
debug(a, b, c);

unordered_map<string, int> d;
d["string 3"] = 3;
d["string 4"] = 4;
multiset<int> e = {5, 5, 4, 3, 1, 1, 2};
vector<vector<int> > f = {{1, 2, 3}};
debug(d, e, f);

Output:
'[a, b, c] = [{1, 2, 3, 4}, {1, 2, 3, 4, 5}, {{"string 1", 1}, {"string 2", 2}}]'
'[d, e, f] = [{{"string 4", 4}, {"string 3", 3}}, {1, 1, 2, 3, 4, 5, 5}, {{1, 2, 3}}]'

Note: I haven't tried the debug with other complex data types nested in collection types.


Expressions:
int a = 1;
int b = 2;
debug(a + b, a * b, a / b, a - b, a / (float)b, 2019, 2019 - 1);

Output:
'[a + b, a * b, a / b, a - b, a / (float)b, 2019, 2019 - 1] = [3, 2, 0, -1, 0.5, 2019, 2018]'


You can use the template and change it's style to what you want. Hope it would help you debug in C++ easier.

Read more »

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

By livw, history, 9 months ago, In English,

Hi. I had created a small Java tool called "Codeforces Collection" which can help get accepted submissions on codeforces, except submissions of gym contests. If you feel interesting, you can check it out and read the instruction here.

Hope you enjoy it!

Screenshots:

Read more »

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

By livw, history, 18 months ago, In English,
Hi!

Many of you may have heard about shortest path problems of unweighted graph problems which are solved by 'meet in the middle' technique (MITM), and also solved them. My teacher taught me the implementation, but understanding it correctly hadn't been easy for me, until now. I also tried to modify my teacher's implementation in a clean way, and it worked (at least it helped me get accepted solutions), which made me feel excited.

So i'm writing this blog to share with you my implementation and how does it work, because i believe that some of you might be also having problem in understanding and implementing it, and what i'm writing could help you. I will write everything based on my experience, so there might be some mistakes, but i'm trying my best.

Introduction

Simple MITM Problem

Unweigthed graph problems

Now we have more interesting problems. They are unweighted graph problems.

Problem
  • For a permutation p1, p2, ..., pn of n integer from 1 to n (1 ≤ n ≤ 10). You can swap two consecutive elements pi and pi + 1 (1 ≤ i < n). Find minimum number of swaps to change p to another permutation p' = p'1, p'2, ..., p'n.

Seem like there is nothing related to graph in the statement. But let's see: Assume one permutation is one vertex, then every swaps of a permutation's elements is an edges which connect this vertex with another vertex. So finding minimum number of swaps now becomes a simple BFS/shortest path problem.

Now let's analyze time complexity. We have n! vertices, each vertex has n - 1 adjacent vertices. We also have to store vertices's visited state by map, because their representations are hard to be stored by normal arrays. So total time complexity is o(nlog(n!) × n!). Of course, this complexity can not pass 1 second time limit. That why we need MITM technique to make the solution faster.

MITM solution

Let's remember the BFS algorithm to find shortest distance of a path start from vertex start to vertex finish:

  • Push start into queue's back, visitedstart = true, let root = start.

  • Let Du be the shortest distance from root to vertex u, Droot = 0,.

  • While queue is not empty, pop queue's front which is vertex u, then push all vertices v which are adjacent with u and haven't visited yet (visitedv = false) into queue's back, then let Dv = Du + 1 and visitedv = true.

  • Result = Dfinish.

MITM solution is similar to BFS solution. Below is my implementation:

  • Let both start and finish be roots. We BFS on 2 roots start and finish at the same time, but using only one queue.

  • Push start and finish into queue's back, visitedstart = visitedfinish = true.

  • Let srcu be the root of vertex u in BFS progression. So srcstart = start and srcfinish = finish.

  • Let Du be the shortest distance from vertex u to it's tree's root. So Dstart = Dfinish = 0.

  • While queue is not empty, pop queue's front which is vertex u, then push all vertices v which are adjacent with u and haven't visited yet (visitedv = false) into queue's back, then let Dv = Du + 1, srcv = srcu and visitedv = true. Especially, if v was visited and then we can immediately return Result = Du + Dv + 1.

Instead of pushing only start vertex into queue at first, we push both start and finish into queue. That means we will go from start and finish at the same time. It's like we BFS with 2 different trees, but using the same queue, not 2 separate queues at the same time. Also for each vertex u, we know which is it's root, and shortest distance from root to it (srcu and Du).

Then for a vertex u in front of queue, if there is an adjacent vertex v which has different root (assume it is finish) of u's root, which means they were from different BFS trees, then we return result = Du + Dv + 1.

So with BFS you have to travel in a tree with depth = S to find the anwser, now you just have to travel in two trees with smaller depths, later we will prove that the smaller depth is about . It sounds like MITM!

But there is one thing that made me confused: Shortest path from start to u + shortest path from finish to v may be not equals shortest path from start to finish (let's ignore 1 of the formula), so why can we return the anwser immediately when we meet a pair (u, v) like above? It took me a long time to find the anwser.

My proof

See the description of the queue below:

  • Si is set of vetices which have shortest distance from root start equals i.

  • Fi is set of vetices which have shortest distance from root finish equals i.

  • Sets are placed in chronology order. Set which is placed before another set means the vertices of that set were pushed into queue earlier.

  • Sets have red color means their vertices were poped out of the queue.

  • Set has yellow color means there is one vertex belong to that set being in front of queue and being processed. Of course there is only one set which has yellow color.

  • Sets have green color means their vertices were pushed into queue and are waiting to be processed.

There is one property that you need to remember:

  • When a vertex u are in front of queue, the maximum possible Dv which v has been pushed into queue is  ≤ Du + 1 (1).

Okay. Now we are going to find out why we can return the answer like what i said in my implementation. Let u be the vertex in front of queue (being processed), S is the length of shortest path, and v is the ajdacent vertex which has different root of u's root.

  • If there is one shortest path with length 4 (even) then we get the queue state like this:

  • If the shortest path has length 5 (odd) then we get another queue state:

In both cases, and , so Du ≤ Dv.

Now, if there were a vertex u' which Du' < Du (be pushed into queue earlier), and has an ajdacent vertex v' which was visited, has different root and Du' + Dv' + 1 = S, then Dv' > Dv. So Dv' - Du' ≥ Dv + 1 - (Du - 1) = Dv - Du + 2 ≥ 2, then Dv' ≥ Du' + 2. That is wrong because of property (1).

So we can prove two things:

  • We can immediately return the answer at the first time we meet a satisfied pair (u, v).

  • If shortest length is S then and , then the depths of two BFS trees of MITM technique is about .

Pseudo code for my implementation:

visited[start] = visited[finish] = true;
D[start] = D[finish] = 0;
src[start] = start; src[finish] = finish;
queue.push(start); queue.push(finish);
while (!queue.empty()) {
    vertex u = queue.front(); queue.pop();
    for (vertex v: adjacent(u)) {
        if (!visited[v]) {
            visited[v] = true;
            src[v] = src[u];
            D[v] = D[u] + 1;
            queue.push(v);
        } else if (src[u] != src[v]) return D[u] + D[v] + 1;
    }
}

Now it's easy to implement it. Notice that instead of using visited and D, you can use just only D to do both by assiging Dstart = Dfinish = 1. Of course we need to adjust the returned result.

Here is one problem which can solve by MITM technique. Everything is similar, except finding adjacent vertices, which is a little bit complex. It can also be solve by simple BFS, so you can do both to compare their run times. In case you need my implementation,

here is it

by the way,

need a rest?
Extended problem

The above problem is simply find shortest path between to vertices in graph. The next problem is also finding shortest path, but has a few differences:

  • For a graph G with n vertices numbered from 1 to n, m edges and set S of k source vetices S1, S2, ..., Sk (1 ≤ Si ≤ n). Find a shortest path with different start and finish vertices, and those vertices are belong to S.

Firstly we push all source vertices into queue, set each of their src equals themself. After that we will do everything like the implementation we did. The proving is similar to what i did above.

The end

That is everything i want to share with you. I tried my best to help you understand the idea of my implementation and how does it work. Again, my knowledge is limited, so i may missed something, or made some mistakes in this blog.

Thanks for reading!

Read more »

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

By livw, history, 19 months ago, In English,

Hi!

I'm writing a C++ program to generate testcases. It has a class Task which contains:

fstream in, out;

and contructor

Task(string fileIn, string fileOut) {
    this->fileIn = fileIn;
    this->fileOut = fileOut;
    in.open(fileIn.c_str(), ios::in);
    out.open(fileOut.c_str(), ios::out);
}

This class will read input from file fileIn (which was generated), solve problem, then write output to file fileOut. No error so far, but the problem is that the program can just read and write with file, while i'm also wanting to do it with standard input/output stream, so that i can also use the program to submit. All i can do now is using a variable bool isFile and if/else statements, which mean i would have to write the input/output parts twice. I'm thinking about a way which i can change from file stream to standard stream directly but i don't know if it were possible.

If you have an efficient way, please help me :( I appreciate all your help!

Read more »

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

By livw, history, 21 month(s) ago, In English,

Hi everyone :D

This is .conf file (codeforces.conf) of codeblocks which is the theme of Codeforces's code preview (the theme when you click at submission's numbers at submission tab). I tried my best to make this, it should be ~ 90.8% similar. If you want to try something new when code with Codeblocks, and you also love Codeforces, you should try this :D (or just try it for no reason).

If you don't know how to apply this config, here is some help:

  • Open cb_share_config (\Program Files (x86)\CodeBlocks\cb_share_config).
  • At Destination configuration file, choose default.conf (It should be at \Users\(your_user)\AppData\Roaming\CodeBlocks\default.conf).
  • At Source configuration file, choose my codeforces.conf, then choose all 2 boxes.
  • Choose Tranfer >>, then Save.
  • Done!
  • Now go to Codeblocks, open Setting > Editor... > Syntax highlighting > Colour theme. You should see my theme already wait there.

This is how it looks like:

Hope you enjoy it!

Read more »

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

By livw, history, 21 month(s) ago, In English,

Problem:

There are N stores, store i-th has a gift with value fi. There are M one-way roads, i-th road go from store ui to store vi takes ti times to travel. Our trip will look like that: Start from an arbitrary store, go to at least 1 another store, then back to the beginning store. Every time you come to a store, if there is a gift here then we take it, and this store no longer has gift.

For every trip, let R be ratio between total value of all gifts we take and total travel time. We have to find maximum possible R.

Constraints: 1 ≤ N ≤ 1000, 1 ≤ M ≤ 5000, 1 ≤ fi ≤ 1000, 1 ≤ ti ≤ 1000.

Do you have any idea?

Our trip can be represented by an array u1, u2, ..., uk, uk + 1 (k > 1), which is visit order of vertices and uk + 1 = u1 and there is an one-way road from store ui to store ui + 1 . We can also visit one store for more than one time.

Read more »

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

By livw, history, 22 months ago, In English,

(Sorry for my bad english!!)

Problem (QBSEGPAR — Vietnam Olympiad of Informatics 2005): For an integer array a1, a2, ..., an and a integer k. Determine the smallest integer M to divide the array into k non-empty parts so that the sum of the elements in each parts does not exceed M.

  • Constraints: k ≤ n ≤ 15000, |ai| ≤ 30000.

UPD: For example, we have n = 5, k = 3, and the array is 4, 3, 2, 1, 5. Then here is one way to divide the array into 3 parts: [4, 3], [2], [1, 5]. You can also represent one way to divide the array into k parts by an array x1, x2, ..., xk (1 ≤ x1 < x2 < ... < xk = n) which part ith (i > 1) is subarray [xi - 1 + 1..xi] (first part is subarray [1..x1]).

I have an solution, which we do binary seaching for M, and dp to check if this M could satisfy (let f(i, j) = true means you could divide array a[1..i] into j parts so that the sum of the elements in each of j parts does not exceed M. Otherwise, f(i, j) = false. Then we can divide array a[1..n] into k satisfied parts if f(n, k) = true). Of course this couldn't pass all tests.

Then I checked for the solution. Here is it, we also do binary searching for M, but for each M, we do a different dp:

  • fi = minimum number of parts which has sum of elements does not exceed M that you could divide from array a[1..i].
  • gi = maximum number of parts which has sum of elements does not exceed M that you could divide from array a[1..i].

Required complexity is o(nlogn2). We can calculate f and g by o(nlogn) dp, which need segment tree or Fenwick tree (i haven't done it), or simple o(n2) dp. Okay, now here is the checking part, which is unclear to me: The solution said that array a[1..n] could divide into k satisfied parts if fn ≤ k ≤ gn. I think this might not be right. In my opinion, we can divide array a[1..n] into minimum fn satisfied parts, maximum gn satisfied parts, but it doesn't mean we can divide the array into k satisfied parts which fn ≤ k ≤ gn.

Could you tell me how to prove this solution right or wrong? Thanks for your help!

Read more »

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

By livw, history, 23 months ago, In English,

Fermat point of a triangle is the point which total distance from it to 3 vertices of the triangle is minimum. Someone in our programing group said that it can be found by ternary search: first, ternary search for x, then y. Is that true?

Read more »

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

By livw, history, 2 years ago, In English,

Given a tree with n vertices (n <= 1e5), n-1 egdes with positive weight (length). For every vertex that are not leaves, find the longest path from it to a leaf.

I have just come up with an o(n^2) brute-force algorithm, that is for every leaf, we dfs from it and update the result. Can we solve it with better complexity?

Read more »

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

By livw, history, 3 years ago, In English,

A pupil asks a Candidate master: "How can you get purple color?" The master anwsers: "Use your time to learn".

Read more »

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

By livw, history, 3 years ago, In English,

Here is my submission of problem C round 362: http://www.codeforces.com/contest/697/submission/19127392

I was WA by test 38. It said that my output was 102 and the anwser is 97. But when I tested the input again with the same code, my output was 97? Is that a error or I was just hacked?

Read more »

 
 
 
 
  • Vote: I like it
  • -16
  • Vote: I do not like it