Блог пользователя tantam75

Автор tantam75, история, 5 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +39
  • Проголосовать: не нравится

Автор tantam75, история, 7 лет назад, По-английски

(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!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится