duckladydinh's blog

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

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

Read more »

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

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

Read more »

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

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

Read more »

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

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

Read more »

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

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

Read more »

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

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

Read more »

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

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

Read more »

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

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

Read more »

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

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

Read more »

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