duckladydinh's blog

By duckladydinh, history, 5 weeks ago, In English,

After experimenting with Kotlin for a long time, my love for Java grows. Here are a few points I strongly believe that Java is better...

  1. Worse parameter type casting. It is even worse compared to Java. At least, Java could detect an int object in a long parameter. Now if I create a method for long, I need to create int wrapper for it.

  2. Hardship to create multidimensional array. Even if I agree that linear array is almost 99% of the case in real world scenario, if we somehow need it, like for CP, it is a terrible experience.

  3. Immutable function parameters. It should be fine if the outside fields are immutable, but now, even within the scope of the function, we have to declare new variables and if we use the same name, we got the warning "shadowed name". It is even worse than Java.

  4. No real interop for functional features in Java and lambda is a bit worse. This is not related to CP, but for software engineering. Another reason to not adopt it.

Well, there are more, but after trying Kotlin for sometime, I am increasing doubtful of its existence. There are hardly strong evidence for it in my opinion. Do you have any idea?

Thanks!

Read more »

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

By duckladydinh, history, 5 weeks ago, In English,

Hallo,

I am stuck on the following graph problem: How many k-colorings (exactly k, k is a constant) of a sparse graph of n vertexes (n <= 50000) with no connected component of size s having more than s + 2 edges (almost tree).

I am completely stuck!!!

Could someone give me a hint? It's a problem from Hong Kong Regional Online Preliminary 2016 (all of their problems are super hard).

Thanks.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By duckladydinh, history, 8 months ago, In English,

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.

Read more »

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

By duckladydinh, history, 11 months ago, In English,

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

Read more »

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

By duckladydinh, history, 11 months ago, In English,

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

Read more »

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

By duckladydinh, history, 13 months ago, In English,

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).

Submission: https://beta.atcoder.jp/contests/abc110/submissions/3261324

Thank you very much.

Read more »

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

By duckladydinh, history, 13 months ago, In English,

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.

Read more »

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

By duckladydinh, history, 17 months ago, In English,

[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.

Read more »

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

By duckladydinh, history, 17 months ago, In English,

[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.

Read more »

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

By duckladydinh, history, 17 months ago, In English,

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.

Read more »

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

By duckladydinh, history, 18 months ago, In English,

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.

Read more »

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

By duckladydinh, history, 20 months ago, In English,

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.

Read more »

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

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

Hallo, everyone.

Can you please help me with the following problem?

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

Read more »

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

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

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.

Read more »

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

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

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.

Read more »

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

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

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.

Read more »

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

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

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.

Read more »

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

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

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.

Read more »

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

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

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.

Read more »

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

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

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.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

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.

Read more »

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

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

Hello friends,

after weeks of mind-battling, I have finally made up my mind to take a break from Competitive Programming. My plan is to pay a visit to other fields of Computer Science, to see if there are any other things interesting in life, and I have found the first stop in my journey... Genetic Algorithms.

The thing is, I have recently come across a problem, "input a number and output any equation that equals to it". Sound simple :v??? Indeed, but just after I read the code, I felt like "what the heck I am reading". The program is a few hundreds of lines in length, and the algorithm is exactly what I learnt in my high school biology lessons: create a 'population' of equations, encode them into binary 'genes', choose 'dad' and 'mom' genes in a way resembling 'natural selection', let them marry and produce children by crossover and mutation of their genes. Just like the way organisms evolved, isn't it? Why this "crazy" approach works is still mysterious to me.

Link to the problem and solution (code): http://www.ai-junkie.com/ga/intro/gat3.html

Now I feel really interested in such algorithms, and I want to learn more about them, but you know, it is really difficult because I cannot find any similar problems and even if I can, there is just no one around to evaluate my work. Therefore, I wonder if there is any online judge like Codeforces or Topcoder that has such problems. It would be very nice if someone can recommend some learning materials and some communities that focus on this field. At the moment I am following the book An Introduction to Genetic Algorithms by Mitchell, but when I am not clear about something, I cannot ask anyone :'( at all.

Thank you for your time and consideration. HAPPY CODING.

Read more »

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

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

Dear competitive coders, (this is as lengthy as 'Codeforces problem statements' and irrelevant to improving your skills, so never mind it if you are short of time, but if you could read it and find an 'AC solution' to my problem, I would like to deeply appreciate it)

The past 2 years made the most tedious period of my life. Time has revealed to me a miserable truth that I am too old to be a coder or even anything. If one takes a look at my rating graph, it would be crystal clear that my 2 years of lifetime has been wasted. The line was just fluctuating around some certain points depending on my emotional states (approximately 1600 at first, then 1850 thanks to the recent "Rating Inflation", I was actually happy with it for a while though). No improvement, yeah, 2 years without any improvement at all. I start to wonder if I am really aging that fast.

Never can I forget the first time I started coding, 8 years ago. When my friends were learning Excel, I was coding my the first infamous Pascal program, "Hello World", for... almost 1 and a half hour (Well I am aware that I was originally not an intelligent being, trying to replace the command name and the ";" for something more beautiful :p and receive red warnings all over the windows, but hard work beats smart mind, I made it run finally). I coded through days and nights since then; stay in the local bookstores to read all the programming books I found till they closed. Now, whenever I attempt to code, my body seems to be functioning on its own, like I want to break something, hit someone, jump back and forth, and even after... trying all, I could never force myself to focus on a problem for long enough, not to mention sometimes I did even give up reading a problem statement because I forgot the sentence as soon as I moved on to the next one. What is exactly going wrong with me? No idea but it is just terrible... but not all. At first glance, it seemed that I just could not improve, but the more terrifying truth to me is that my learning ability has a serious problem. I cannot learn new things. Everything got worse in my class. I still survived through my exams, but all I did were 'sleep till the final day' and write all stuff that I 'already knew long long ago' (thanks God that I study Computer Science). My lectures are hopeless. Over the past 2 years, I simply could not learn a single new thing. My brain seems full even though I know more than anyone, it has always been empty. Is this a symptom of aging? I wonder if it is really too late for me to learn. Am I really that old? I am already 20.

It is not like I don't devote enough time to learning. 'Even more', I can say. I did attend 'all' my lectures, trying to listen to my teacher without sleeping (in the past I often skipped my class and got away from school whenever I could do it officially). I spend nights trying to force myself to read book, all sorts of book, mostly till midnight, many till morning, but all were in vain. I simply could not read at all. Deep inside my mind, I am still able to sense some sort of desire to break through my limit, to fly higher and succeed, but just as soon as I get started, foolish thoughts suck as "Let's eat first", "A movie is nice", "Sleep please". I end up doing nothing, fighting against these thoughts like fighting a loosing battle until no time left any more or even if I somehow I manage to get rid of them temporarily, I end up so tired and loose consciousness soon enough... before they came back.

I understand Codeforces is not a place for self-complaining. I just believe that, among us, there exist many great people, who are old (even older than me) enough to suffer from something similar and are well experienced enough to find a solution for it. I want to know if I have any light hope of gaining back my youth or should I better just accept my age and leave the playground now.

Thank you for reading so far. Your patience and determination are far superior to that of mine. Happy Coding

Read more »

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

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

Hello everyone,

Do you have any ideas about the system for NWERC 2016 in UK, like what IDEs, compilers will be used? I have visited their website nwerc.eu, but it has no information at all.

Thank you.

Read more »

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

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

Hello,

I am working on this problem on Kattis. I have been constantly thinking about it for the last 3 hours, but it seems that I am totally hopeless on this problem. Can someone give me some hints?

(I know 3 hours is too short :(. Normally I would only give up if it lasted for a few days, but I am in my urgent self-training period before an NWERC, so I change my plan to solve problems that I am totally hopeless instead of those that are hard but still somehow solvable and I use all this time just to make sure that it is really impossible for me)

Thank you. Happy Coding

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it