Google Code Jam C++ Parallelization Template (Linux) After a long and arduous search, I was not able to find a Google Code Jam template that fulfilled the following properties: 1. Written in C++ 2. Parallelizes test cases 3. Executes each test case in a separate process so I don't have to re-initialize global variables after each test case. I decided to write my own template below. The boilerplate template code below solves the following sample problem: You are given the number of test cases T You are given an integer n, followed by n integers a_i. Please output the sum of the n integers as "Case #TEST_CASE_NUMBER: SUM". Instructions: Step 1: Write code to parse one test case in readOneTestCase(). Step 2: Write your code in solve(). Step 3: Compile and run with no arguments. Pass test data into stdin. Results are passed to stdout. Step 4: If you want to debug test case X, run the executable with X as its only argument, where X is some positive integer. To modify the input test case, look fo...

Full text and comments »

Falsely accused of plagiarism [Submissions are not at all similar] **In yesterday's [contest:1632], I was falsely accused of plagiarism where as none of the people in question have codes similar to one another.** I received the following message. <spoiler summary="Problem C"> <a href='https://www.linkpicture.com/view.php?img=LPic61f7873debc2c1045477817'><img src='https://www.linkpicture.com/q/C_2.png' type='image'></a> </spoiler> <spoiler summary="Problem D"> <a href='https://www.linkpicture.com/view.php?img=LPic61f7876063257829672565'><img src='https://www.linkpicture.com/q/D.png' type='image'></a> </spoiler> Submissions of all the users for Problem C. <spoiler summary="codebuster_10"> ~~~~~ #include <bits/stdc++.h> #define int int64_t //be careful about this using namespace std; namespace IN{ template<class T> void read(vector<T> &A); template<class S,class T> void read(pair<S,T> &A); template<class T,size_t N> void read(array<T,N> &A); template<class T> void read(T& x){ cin >> x;} template<cla...

Full text and comments »

Topcoder STL article summary ### Vector: []++ #### Declaration - empty vector: `vector<int> v;` - array of _10 `vector<int>`s_: `vector<int> v[10];` - vector with _10 int_ elements: `vector<int> v(10);` #### Initialisation ~~~~ vector<int> v1; // … vector<int> v2 = v1; // make a copy? vector<int> v3(v1); // identical to v2's init // … vector<int> v4(1000); // specific size: 1000 0's // … vector<int> v5(20, "Unknown"); // initial value // … vector<int> v6(v1.begin(), v1.end()); // [begin,end) int data[] = { 1,2,3,…,8,9 }; vector<int> v7(data, data+(sizeof(data)/sizeof(data[0]))); // data+length=.end() vector<int> v8(v1.begin(), v1.begin()+(v1.size()/2)); // 1st half of v1 // 1st half of v1, ordered back-to-front vector<int> v9(v1.rbegin()+(v.size()/2), v.rend()); ~~~~ [cut] #### Methods **size()** - unsigned: macro `#define sz(C) return (int) C.size()` - use `empty()` instead of `size() == 0`, because of runtime complexity **push_back(elem)** **resize(new_siz...

Full text and comments »

GNU C++ 11, Compilation Error to_string() + Tutorial According to [this](http://stackoverflow.com/questions/12975341/to-string-is-not-a-member-of-std-says-so-g), we can use `to_string()` only with compiler higher than _GCC 4.8.0_ and with _C++ 11_. But I submitted with _GNU C++ 11 4.9.2_ ([submission:12720137]) and got this error.  I know there are other solutions to convert `int` to `string`, but I want to know what is problem with this one. I am using compiler _GNU C++ 11 5.1.0_ and it's working on my computer. Thanks. #### UPD: Tutorial This will be a quick tutorial about **stringstream**, **istringstream** and **ostringstream**. It may be usefull for someone. `istream` and `ostream`: Interfaces to streaming data (files, sockets, etc.). `istringstream`: An `istream` that wraps a `string` and offers its contents. `ostringstream`: An `ostream` that saves the content written to it as a `string`. `stringstream`: An `iostream...

Full text and comments »

Codeforces Round #789 Editorial [problem:1678A] Idea: [user:tokitsukaze,2022-05-08] <br /> Prepare: [user:tokitsukaze,2022-05-08] <spoiler summary="Tutorial"> We observe that when there is $0$ in the sequence, it is optimal to choose $0$ and any number other than $0$ for each operation. Therefore, when there is $0$ in the sequence, let $cnt$ be the number of $0$s, the answer is $n - cnt$. Otherwise, when $0$ does not exist in the sequence, there are two situations: 1. When there exist two equal numbers in the sequence, we can perform the operation $1$ time to convert it into the situation of having $0$ in the sequence. So the answer must be $n$. 2. When all numbers in the sequence are distinct, we can perform the operation $2$ times to convert it into the situation of having $0$ in the sequence. So the answer must be $n + 1$. </spoiler> <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main(){ int t; scanf("%i",&t); while(t--){ int n; scan...

Full text and comments »

About the Complete Search <p>   <em> &quot;Complete search exploits the brute force, straight-forward, try-them-all method of finding the answer. This method should almost always be the first algorithm/solution you consider. If this works within time and space constraints, then do it: it's easy to code and usually easy to debug. This means you'll have more time to work on all the hard problems, where brute force doesn't work quickly enough. </em></p><p><em>In the case of a problem with only fewer than a couple million possibilities, iterate through each one of them, and see if the answer works. &quot;</em>   <em>    </em>                                                                            </p><p align="right"><em>--USACO</em></p><p>    In the Codeforces Round #104 (Div. 2),problem B .Lucky Mask is just a brut force problem.In the contest, I didn't realize that. </p><p><em>    &quot;Petya calls a <span class="tex-font-style-it">mask</span> of a positive integer <span class="tex-span"><font size="4"...

Full text and comments »

Printing string through ostringstream is faster than printing directly string ? Let's take a look at my 2 submissions for problem [681C](http://codeforces.com/problemset/problem/681/C) [20333485](http://codeforces.com/contest/681/submission/20333485) &mdash; TLE, don't use ostringstream [20333517](http://codeforces.com/contest/681/submission/20333517) &mdash; AC, use ostringstream Briefly, the answer of the problem is a string has 1e6 lines, each line has maximum 20 characters. In the first submission, I stored the answer in string res, then I sum "res = res + line". Finally I printed "cout << res" and got TLE But in the second submission, I stored the answer in sout object ( an ostringstream), sum "sout << line", and printed "cout << sout.str()" and got AC ( even 4 times faster than the first submission) I don't understand the reason behind this. Anyone could explain it ? Thank you in advance

Full text and comments »

[Reserach] The application of ML techniques on certain problems (i.e. How to make crazy hard problems that nobody can solve) Background ================== The idea of this article originated from a contest (Petrozavodsk Summer-2016. Petr Mitrichev Contest 14), which I believe is attributed to [user:Petr,2018-07-25]. In this contest, an interesting problem is proposed: "Cosider this process: pick a random number $n_i$ uniformly at random between $10$ and $100$. Generate $n_i$ random points with integer coordinates, picking each coordinate independently and uniformly at random from all integers between $0$ and $10^9$, inclusive. Find the convex hull of those points. Now you are given $10000$ polygons generated by this program. For each polygon, you need to guess the value $n_i$ that was used for generating it. Your answer will be accepted if the average (over all $10000$ hulls) absolute difference between the natural logarithm of your guess and the natural logarithm of the true $n_i$ is below $0.2$." Unfortunately, I didn't really manage to work this one out during our 5-hour training session. ...

Full text and comments »

NEED HELP : WA (CSES) HELo GUts hand girlS me NOw HAVE pROBLem WIth THS COde FOR CSes>fi THIS is THE oRBLEMOSo : https://cses.fi/problemset/task/1068 (VeRY exTREme HArdn probleM (GM-LGM LEvel) oNLY for PRos) THIS is The CODE fOR SOlvING : // #define ONLINE_JUDGE 69 #include <bits/stdc++.h> #include <chrono> using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; // Macros #define int long long // #define ll long long #define ld long double #define vt vector #define vi vector<int> #define vvi vector<vi> #define vii vector<pair<int,int>> #define pok(ok) print(ok ? "YES" : "NO"); #define pii pair<int,int> // Constants constexpr ll SZ = 2e5 + 7; constexpr ll inf = 9e18; constexpr ll mod = 1e9 + 7; constexpr ll MOD = 998244353; constexpr ld PI = 3.141592653589793238462; const ld scale = 1e6; ...

Full text and comments »