Due to technical reasons Codeforces may be unavailable on April 21st from 01:00-07:00 (MSK). ×

By duckladydinh, history, 2 weeks ago, ,

Hi everyone,

as many of you know, interpolation is the study of approximating functions given a number of points. Currently I want to do a project but it is required to join. I would really appreciate it if someone can help me find a quick start guide to grasp the concepts (Bilinear, Spline, Polynomial interpolation...) at the most basic level and at least be able to do some exercises in this area (about math, not coding). I find some books but their math blows me away :'( given the time I have.

I understand that there is no royal way to learning, but please, could someone please share your experience in learning this wonder of math?

Thanks.

•
• -1
•

By duckladydinh, history, 2 months ago, ,

Hi everyone,

I am working on a problem like this:

"""

Given a graph and a number K, divide the graph into 2 groups A and B such that size of A is exactly K. Find the best division such that the distance between A and B is minimal and every node in B must be mapped to exactly one node in A. Let's say node x in B is closer to node y than to node z in A, then x will be mapped to y, NOT z, and the distance between x and y will be counted in the total distance.

"""

Does anyone know how I can tackle such a problem?

My initial idea is to randomly selecting a group of K nodes and measure the distance and repeat for a number of steps to take the highest. In each step, a new solution is born by mutating the old one, but that is the only solution I can come up with.

I am really interested in such problems. Have you got any experience? Would you mind sharing me your methods? Do you recommend any papers or libraries in Java or Python which allow me to experiment with such non-deterministic problems?

Thank you very much for your time and consideration. I am looking forward to hearing from you.

•
• +5
•

By duckladydinh, history, 2 months ago, ,

Hi Codeforcers,

I often hear people talking about the greatness of VIM and that many red coders use VIM for competitions and VIM is so extensible and powerful of all sorts with numerous plugins available. I also tried some default configurations on the Internet and it looked not that terrible, but since VIM depends so much on plugins to be a great IDE, I am really curious how you installed them during a contest without Internet connection?

Can VIM users share your experience in using VIM for CP :)? I really want to find a good IDE for C++ :V. Even CLion is not too nice :'( .

Thank you so much.

•
• +17
•

By duckladydinh, history, 5 months ago, ,

Hi everyone,

for the past few days, I am reading implementations from Per Austrin. I hate to admit but his code is so clean, neat, short, efficient, aesthetic, intellectual, well-organized... and professional that I believe I have never read anything even close to his code.

I can find only some from NWERC solutions. Does anyone know where I can see more of his incredible code? His code gives me more insights into the problem that the official tutorials could not convey.

Thank you very much Thuan

•
• +35
•

By duckladydinh, history, 5 months ago, ,

Hi everyone,

I am learning this relatively new data structure with a Kattis problem called Palindromes. In this problem, we are given a string and multiple [l, r] segments and must find the number of palindromic substrings in each segment. The number of queries and length of the string are all 10^5. My question is: Is it possible to achieve this with Palindromic Tree and if yes, how can we do that?

I am not absolutely sure if this DS can handle such problems, but at least, I know that for [1, r] segments, it is possible, Is this variant possible? If it is possible, please give me your guidance.

Thank you very much :). Happy Coding

•
• +4
•

By duckladydinh, history, 7 months ago, ,

Hallo Codeforces Hackers,

could you tell me what can possibly go wrong with the following submission? I even changed all ints to long long just in case, but I cannot seem to find out why. It passed all except for test 4_hand_3, what can be in that test? My solution looks the same as that in the tutorial (though I do not know Japanese).

Thank you very much.

•
• +3
•

By duckladydinh, history, 7 months ago, ,

Hello, do you know Kotlin?

It is a promising language that can be a perfect alternative to Java? Using Kotlin, you can access any Java libraries and benefit greatly from its elegant syntax. It was even acknowledged by Google for Android development. And above all, Kotlin has been officially recognized for ACM ICPC. Why don't you give it a try?

Unfortunately, for Competitive Programmers like us, multidimensional array is a must, while Kotlin still has no good support for it. Please put your votes for this feature on https://youtrack.jetbrains.com/issue/KT-21670 . Your vote will surely help bring forth a new possibility for Competitive Programming.

Maybe if Kotlin has more CP users, Jetbrains may give us more free offers :D ? Everyone will benefit in every way. :)

Thank you.

•
• +70
•

By duckladydinh, history, 9 months ago, ,

Hello, everyone

FB HackerCup 2018 just passed in my sorrow. During problem 2, I encountered a very strange exception when running a dfs on a graph of merely 200000 vertexes and create an empty set at each vertex, which is absolutely strange. As you can see in my dfs(int i), there is basically nothing extraordinary in it, and this exception, I really do not understand where it comes from. I wonder if this is a problem with my code, my laptop or the compiler or the structure of the test...?

I run it on 10000 vertexes and it was still fine :V

Thank you so much.

#define llint int64_t
const int MAX = 200002;

llint A, B, n, m;
vector<int> g[MAX];

void dfs(int i) {
set<int> u;

for (int j: g[i]) {
dfs(j);
}
}

void run() {
cin >> n >> m >> A >> B;
for (int i = 0; i <= n; ++i) {
g[i].clear();
}

for (int i = 1, p; i < n; ++i) {
cin >> p;
g[p].emplace_back(i);
}
dfs(0);
}

void solve() {
int T;
cin >> T;
FOR (t, 1, T) {
cout << "Case #" << t << ": ";
run();
cout << "\n";
}
}


•
• -30
•

By duckladydinh, history, 10 months ago, ,

[Updated] Hello everyone,

do you know if there is any data structure (like std::set) that allows querying on 2 parameters and adding elements? The use case is I have a list of (a[i], b[i]). I want perform a query with parameter MAXB that returns the pair with the maximum value by a[i] but the corresponding b[i] value is less than or equal to MAXB. I also want to perform an update by adding a pair.

Do you know any? Thank you.

•
• +3
•

By duckladydinh, history, 10 months ago, ,

[Updated] it seems that LaTex is the way to go, but my sense of design is a bit terrible. Do you know any available configurations for the listings package so that it will looks great like in CLion or VSCode? Thank you. Hello everyone,

I am looking for some software that can (ideally) process the C++ source files and automatically generate me a notebook with syntax highlighting and numbering. Do you know any?

If automation is not possible, doing it by hand is fine, but I cannot seem to find any tool that allows both good syntax highlighting and line numbering. At the moment, I am using Visual Studio Code and Word and the line numbering takes a lot of time. It would be great if some automation tools exist.

Thank you very much.

•
• +11
•

By duckladydinh, history, 11 months ago, ,

Updated: Thank to marX, my old question has found its answer, but a new one's just arrived. I hope you all can continue helping me in understanding this.

Hello everyone,

I am sure that many of you have known this algorithm. As far as I am concerned, it is one of the most popular techniques in AI. I am learning it and I have a lot of questions regarding the intuition behind it, and hence I am writing today, with hope that some of you can share your experience with me.

To summarize a bit, a MCTS algorithm is consisted of 4 phases — Select, Expand, Simulate and Propagate, and is based on a formula called UCB1 to balance between exploitation and exploration.

[NEW QUESTION] My new question is: does MCTS have memory, by which I mean if it does learn to form its experience, save that experience somewhere and retrieve it for query? I asked this because even after understanding how the tree is formed, I find no information for how to query the tree. The only example with clear code and real serious problem I have found (which confused me and made me doubt MCTS) is after analyzing this (the main body) and this (the tree node). In this case, for every time we want to make an action (in the process()), they "create a completely new tree" and only take action after that by considering actions from "only the root" node ("all" other codes in that website use the same idea). In other words, each action is somewhat "independent" of the previous one. Is this the true nature of MCTS? If not (hopefully), could you please give me some references for how I can efficiently use all MCTS past experience and make a query? Thank you so much.

[ANSWER FOUND] My first concern is about the UCB1 formula, that is UCB1 = (total wins / total visits) + C * sqrt(ln(total visits in parent node) / total visits in current node). My question is what will change if I, instead of using "total number of wins", use something like "total reward" (which may be HP loss, energy increase and so on)? In such case, will the term sqrt(ln(total visits in parent node) / total visits in current node) stay the same?

Thank you for your time and consideration. I am looking forward to hearing from you.

•
• +42
•

By duckladydinh, history, 12 months ago, ,

Updated: Thank everyone for your helps, but it seems that I missed a certain condition of the problem, and my version maybe really just impossible to solve :v, the original problem with that condition is a thousand time easier than this and is straight-forward to CP coders like us (The original problem description was a bit confusing to me :'( )

Hi everyone,

today, I am stuck with a problem. I hope you can help me with it. I think this is a very interesting problem and I am not even sure there exists a deterministic solution to it. The problem is as follows:

" Given n (n <= 1000, but O(n^3) is also fine) distinct integers, group them into sets of at least 4 elements, and each set is an Arithmetic Sequences. "

Example:

Input: 1250, 3748, 6246, 8744, 2493, 4993, 7493, 9993, 2497, 4996, 7495, 9994, 2498, 4997, 7496, 9995, 2499, 4998, 7497, 9996

Output: (1250, 3748, 6246, 8744), (2493, 4993, 7493, 9993), (2497, 4996, 7495, 9994), (2498, 4997, 7496, 9995), (2499, 4998, 7497, 9996)

In this test, if you find the longest sequence first, then the rest will not form any valid sequence anymore.

(Assumption: For the given input, there always exists at least one solution that satisfies the constraints and no number is left)

I have spent hours working on this problem but unfortunately I cannot think of any ideas that will work well in general. What do you think?

Thank you.

•
• +15
•

By duckladydinh, history, 13 months ago, ,

Hello,

I am having a problem with problem D, Picking Strings in VK Cup 2018, I cannot find out why I keep getting WA on test 11. Can someone tell me what is wrong with my code? I tried many test cases and all were okay.

Following is my check function which input the number of 'B' (a) and the suffix length of 'A' (b) of the first string and similar c, d of the second string. It output 1 if it is possible to transform.

int check(int a, int b, int c, int d) {

if (b == 0 && d == 0) {
return (a <= c && (c - a) % 2 == 0);
} else {
if (b == 0) {
return 0;
}
if (d == 0) {
return check(a + 2 * (b % 3 != 0), 0, c, 0);
}
int e = min(b, d);
return check(a, b - e, c, d - e);
}
}


Thank you.

By duckladydinh, history, 14 months ago, ,

Dear coders,

Last weekend, there was a Machine Learning contest on Hackerrank, namely GS CodeSprint 2018. It was my first time participating on a Machine Learning contest, so the result was horrible, but the important thing is: it is fun. During the contest, I only attempted to solve the easy problem, Car Popularity Prediction, but failed to solve it perfectly. It is simply a multi-classification problem: Given m features, map it to one of the 4 classes.

I saw many people perfectly completed it. Therefore, I wonder if it is possible to share your approach? In my solution, what I did was to use a simple sklearn SVM and a grid search on C from 0.001 to 100. Only these few line of codes could get me 0.92. Run it a few more times and I get 0.94, but it was not possible to get 1.

I would be thankful if you can share with me what you have done to solve such problem perfectly. Thank you. Besides, is there anyone knowing how to resubmit the problem? I tried to resubmit but their server did not accept?

Thank you for your time and consideration. I am looking forward to hearing from you.

•
• +2
•

By duckladydinh, history, 17 months ago, ,

Hallo, everyone.

If a[n] = b[k] * a[n-k] for k = 1..n, then the generating function A(x) = a[0] / (1 — B(x)) We can compute all a[n] with Divide and Conquer algorithm in O(nlog^2(n)). What is that Divide and Conquer algorithm?

I have the feeling that it is strongly related to FFT but that's just my feeling. Can someone give me the exact algorithm?

Thank you

•
• +2
•

By duckladydinh, history, 17 months ago, ,

Hallo everyone,

Do you know any simple formulas that are often unknown to many? For me, some can be mentioned are

• Graph: Euler characteristic, Handshaking theorem, Caley Formula, Kirchhoff's theorem, Kőnig's theorem

• Polygon: 2-Ear Theorem, incenter formula of a triangle, pick theorem, Shoelace Formula

• Logic: Pigeonhole

• Prime: Fermat, Wilson's theorem

• Number: McNugget theorem

• Fibonacci: Zeckendorf's theorem

• Counting: Burnside Lemma, stars and bars

• Combinatorics Identity: Vandermonde's Identity, Hockey-stick identity

• Math: Linearity of Expectation

• Other: harmonic series sum

... And what about you? Can you share some?

Thank you.

•
• +92
•

By duckladydinh, history, 17 months ago, ,

Dear friends,

"Driving in Optimistan"

I have read this problem from last year to this year, but I am still unable to understand the example. The English is perfect. The way they express the problem is super nice, but it seems a little overwhelming for me. Therefore, can someone please help me clarify the sample input/output???

Thank you.

•
• +5
•

By duckladydinh, history, 17 months ago, ,

Hello,

I have been looking for an implementation of 2D Fenwick Tree for n, m<= 100000 without using std::map but with no luck. I want to ask if it is possible to implement 2D Fenwick Tree using O(nlogn) memory and O(logn^2) per update?

Tutorials, ideas or papers, all are very welcome.

Thank you.

•
• -5
•

By duckladydinh, history, 18 months ago, ,

Hello, everyone!!!

I would like to post some old problems from old ICPC Regionals/WF... on Kattis and create some contests for me and my friends, but I cannot find anyway to do that. Does any one have an idea how we can do something like that?

I already tried ICPC Archieve and feel very unacceptable. My output presentation was correct on udebug and get WA while while my output not matching with udebug, my solution get ACcepted.

Thank you.

•
• -5
•

By duckladydinh, history, 18 months ago, ,

Hallo everyone,

I want to ask if there is anyway to enable g++ compiler option '-std=gnu++14' within the source code. I am upsolving problems from the recent Barcelona bootcamp but for some reasons, they did not enable C++14 and my code library just gives all kinds of errors due to that. I really do not want to recode my already tested library.

Thank you.

•
• -6
•

By duckladydinh, history, 18 months ago, ,

Hallo,

I have been using e-maxx.ru for quite some time. It has also been my great dictionary when it comes to learning algorithms, but it seems clear to me that e-maxx has been outdated. I recently hear a lot more algorithms that are not covered by e-maxx. A few to mention are palindrome tree, Lichao Segment tree, Dominator Tree (not sure if this is a correct name)... and a dozen more.

I wonder if there exists a new page that has the same functionality as the great e-maxx page where we can see new algorithm updates? If there is implementation, it is nice, otherwise, the name and definition should do. English page is wonderful, but even if it is in Russian, it would be still marvelous with Google Translate. I also tried wcipeg.com but it is not even comparable to e-maxx.

Thank you for your time and consideration.

•
• +10
•

By duckladydinh, history, 19 months ago, ,

Hello everyone,

Do you know any simple tutorial + implementation + applications for Delaunay triangulation? I searched around, but still unable to find any good stuff in this topic.

Thank you.

•
• +30
•

By duckladydinh, history, 19 months ago, ,

Hi friends,

During the implementation of matrix fast exponentiation, I have encountered a segmentation fault in the recursive approach. Even if I have managed to fix it by changing it to a loop, but I really want to know what is wrong with my code. I wonder if you can help me.

This is my recursive implementation. I cannot understand what is wrong with it. With n = 1, it is fine, but if n is greater than 1, then segmentation fault.

const int N = 100;

struct Matrix {
llnum c[N+N][N+N];
int n = 0, m = 0;
Matrix(int _n, int _m) {
n = _n, m = _m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
c[i][j] = 0;
}
}
}
void out() {
REP(i, n) {
REP(j, m) {
cout << c[i][j] << " \n"[j+1 == m];
}
}
cout << "\n";
}
};

Matrix fast_pow(Matrix A, int n) {
if (n == 0) return ident(A.m);
if (n == 1) return A;
Matrix E = fast_pow(A, (n/2));
if (n % 2 == 1) {
return mul(E, A);
}
return E;
}



Thank you.

•
• -5
•

By duckladydinh, history, 20 months ago, ,

Dear all,

I am having trouble understanding the solution to this problem on Kattis. I hope someone can help me explain the solution.

Summary of the problem: Given a 2D binary table, each ceil is either high or low. The cost go from a low ceil to a high one is A, the cost to "low down a high ceil" is B. We must find the minimum total cost of traveling through all columns and then all rows by lowing down some ceils?

Summary of the solution: Create a graph with n * m (ceils in the table) + 2 (source and sink) vertexes, connect the source to all low ceils and connect all high ceils to the sink with edges having capacity of B, connect ceils to their neighbors (regardless of the heights) with edges having capacity of A. The answer is the min cut max flow from source to sink.

I try my best but still unable to understand the meaning of this solution. I think this is a great application problem of max flow min cut, so I hope someone can help me.

Thank you so much for your time and consideration.

By duckladydinh, history, 20 months ago, ,

Hallo everyone,

the next Barcelona Bootcamp is coming. This year, my university also has the intention of participating. That is really great!!! :)). Looking at the previous World Final results, I think this is a huge opportunity for me since maybe I can transform myself to a higher stage with this. However, I wonder if I should go...

Honestly, looking at the the result does not give me a very good feeling because I think it is normal for a university like ITMO to win (that is not the first time anyway) or the University of Tokyo to get a bronze medal (in fact, they did even better when rng_58 was alive). It is not really clear when seeing the results from the always-on-the-top participants. How about other participating universities? Was there any big jump-ups in their ranking? Especially for those in the second division, what were their results in the regional contests? If possible, I really want to know.

Of course, there is always an option that I just 'go for fun' and ignore everything, but I will not forgive myself if I cannot gain anything back for my university because my fund is from my university and the fee is not cheap anyway, let alone visa and travel costs. I am from a normal university that is normal in all respects, but my university is still funding for coding passion, though a bit useless passion, so I must make a responsible decision even though no one will kill me if I waste the money.

I really want to know what kind of training the Bootcamp can offer in just a few short days and how relevant they are. What are the results of all participating universities at both World Finals and Regionals in the previous Bootcamp, other than the top 12 in World Final? Is this camp suitable for lower class universities or only relevant for those that are already on the top of the world?

Thank you for your time and consideration. PS: I have absolute trust in the organizer, especially Mike who has created the great Codeforces, but I just want to know if someone like will really benefit from the Bootcamp. Thank you.

Updated: I am so sorry for being mistaken. The ACM World Final results on their page are referenced from the MIPT workshop, the not Barcelona Bootcamp itself. It seems that this Bootcamp is still too new.