Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

duckladydinh's blog

By duckladydinh, history, 7 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.

Full text and comments »

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

By duckladydinh, history, 7 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.

Full text and comments »

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

By duckladydinh, history, 8 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.

Full text and comments »

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

By duckladydinh, history, 8 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

Full text and comments »

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

By duckladydinh, history, 8 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.

Full text and comments »

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

By duckladydinh, history, 8 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

Full text and comments »

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

By duckladydinh, history, 8 years ago, In English

Hello coders,

Currently, I am stuck with the following problem: Given 2 powers, a[0] ^ (a[1] ^ (a[2] ^ (... ^ a[n]))) and b[0] ^ (b[1] ^ (b[2] ^ (... ^ b[m]))), how to compare these two powers? (a[i], b[i], n, m <= 100)

I believe that there must be some mathematical trick to solve this problem but I could not find out myself. I hope that someone can help me with this. Thank you very much.

Another matter is, I wonder if there is a simple and fast way to compute (a[0] ^ (a[1] ^ (a[2] ^ (... ^ a[n]))) % MOD) for some MOD. All I can think of is to use Euler theorem a ^ totient(MOD) = 1 (% MOD), but it seems pretty low. Can someone help me with this too?

Thank you for your time and consideration. Happy Coding

Full text and comments »

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

By duckladydinh, history, 8 years ago, In English

Hi guys,

Coding for several years, all I can say is that Competitive Programming is so great that I love it so much, despite my innumerable failures and the enormous amount of time it takes. I have always happily enjoyed it until I read this.

I hate to say this but I have to admit that what other people say about us (or at least me), competitive programmers, is true: We are not so great as we are supposed to be. As a Computer Science student, I feel it myself too. When it comes to learning a new programming language, it has always been so easy for me, but then I recognise that I can only learn as much as the previous one, to compete here on Codeforces, but not anywhere else. I could not build anything useful like an OS or an IDE when I was using Pascal and neither can I now when I have already know C/C++, Python, Matlab, Java... I feel so disappointed about myself.

I also want to build something useful just like when Linus Torvald built his first Linux Kernel. That kernel was written in C, and I know C but I am still unable to do anything similar. I hate this. I hate the feeling of being inferior to those people who called themselves professional programmers. I hate that but how and what can I do?

I hope that some of you have similar feelings like me, and I would like to know your thinking and experience, about how we can go further, go beyond what we currently are.

Thank you for your time and consideration. HAPPY CODING

Full text and comments »

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

By duckladydinh, history, 8 years ago, In English

Dear coders, how do you read books?

There is just no way I can imagine that can help us gain more knowledge but to read a book. Reading is surely more important than practising problems. An effective way to read a book is, however, still mysterious to me. I have tried my best to read some books like Introduction to Algorithm, the 4 volumes of The Art of Computer Programming and some more. The result is always "IT RETURNS NOTHING".

My reading process can be summarised as follow: Firstly, I open the book, read the Table of Contents and the Introduction. Then I come to the first chapter, read word by word to understand the motivation and situation in every sentence. After the first page, I am extremely energetic. After the second page, I feel that the situation in each sentence is no longer interesting and the motivation inside it is decreasing (So is my motivation). After no more than 10 pages, I feel extremely sleepy. I then drop the book, go to sleep and come back to it later. However, I recognise that I have forgotten everything I have read, which means I can never finish a book.

How about you guys? Have you ever been in a similar situation? If yes, what have you done to overcome it? Maybe you think I am just inborn lazy, and maybe it is really true :)). I, however, really want to read more and more. If you know a way, please tell me. I am really curious about the way great people read books.

Thank you very much.

Full text and comments »

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

By duckladydinh, history, 8 years ago, In English

Hi guys,

I am reading the book Competitive Programming 3 from Steven Halim. However, I am having a bit of trouble as there are no solutions to starred (difficult) questions (For easy one, there are very clear answers, I wonder why?). I wonder if there are any official or unofficial sources where I can find some hints to these difficult questions?

Another question is that, has anyone tried this website? (By Mr. Halim too)

https://www.comp.nus.edu.sg/~stevenha/methodstosolve.html

It is said to contain hints to many problems. However, I have found no ways to see these hints. Clicking on the hint button (?) does not return anything. Is there anyone knowing how to use it or it really does contain nothing.

Could you please help me? Thank you.

Full text and comments »

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

By duckladydinh, history, 8 years ago, In English

Hi, everyone!

Do you remember the Max-Sum Subsequence? I don't know the exact name, but the problem is: Given an array of N elements, find the subsequence [i, j] such that the sum (a[i] + a[i+1] + a[...] + a[j]) maximizes.

And the problem I am working on (in vain), is given K queries, each is either to update (change value of) an element a[i] for some i (given in the query) or to find the Max-Sum subsequence [i, j] within the range [L, R] for some L, R (given in each query).

Constrains: N <= 100,000, K <= 100,000, |a[i]| <= 10^9.

I have tried but still unsuccessfully. Could someone please help me? Thank you very much!

Full text and comments »

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

By duckladydinh, history, 9 years ago, In English

Hi everyone,

I know that this is not a good question to post on Codeforces, but since we all know that a good mathematical background does greatly improve our programming skills, I wonder whether or not there are any good books in Maths to learn, and of course it would be even better if they could be similar to Introduction to Algorithms or Competitive Programming.

I know that many great coders on Codeforces are also great mathematicians, such as the legendary Xellos. Could you share your secret and books to learn Maths with us?

Thank you.

Full text and comments »

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

By duckladydinh, history, 9 years ago, In English

Hi everybody!

I have been working on the following number problem for half a year, but still unable to figure it out. Could someone help me?

PROBLEM: Given n elements a[1], a[2] ... a[n], let A be a set such that:

  1. All element a[1], a[2] ... a[n] belong to A.

  2. If x, y belong to A, GCD(x, y) and LCM(x, y) belong to A.

Task: Given a number x, determine if x belongs to A.

Thank you.

Full text and comments »

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

By duckladydinh, history, 9 years ago, In English

Hi everyone.

I am working on 484A — Bits which should be an easy one. Unfortunately, I am facing a very strange thing that I have never seen before. Hope that someone can help me with it.

Below is my code, and the problem is this code gives WA on test 2, line 12th, when the statement a = 0 is after cin >> l >> r, but when I just put the statement a = 0 before cin >> l >> r, it gives WA on test 2, line 11th. However, in both cases, I test on my computer, both code are correct.

#include <bits/stdc++.h>
using namespace std;
#define len(u) (64 - __builtin_clzll(u))

int n;
int64_t l, r, a, u;

int main(){
    cin >> n;
    while(n--){
        cin >> l >> r;
        a = 0;
        while(len(l) == len(r) && r > 0){
            u = 1 << (len(r) - 1);
            l-= u, r-= u, a+= u;
        }
        u = 1 << (len(r) - 1);
        u <<= (u + u - 1 == r && r > 1);
        cout << a+u-1 << "\n";
    }
    return 0;
}

Thank you.

Full text and comments »

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

By duckladydinh, history, 9 years ago, In English

Hi everyone!

For one-parameter function such as f(n) = f(n-1) + f(n-2), we all know that it can be solved with matrix multiplication, but what if there are two parameters such as f(n, m) = f(n, m-1) + f(n-1, m)? Is there similar way to solve it?

Can someone help me?

Full text and comments »

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