Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

royappa's blog

By royappa, history, 5 months ago, In English,

The "Recent actions" list on home page only contains the last 25 blog entries. There is a "Detailed->" link at the bottom but that takes us to a list of individual comments, and that too, it is limited.

I wanted a place where I can catch up on older CF blog entries, so I created this page:

https://codeforces-blogs.web.app

It watches the blog entries periodically and adds them to an archive.

Some notes:

  • Mike may say this is not allowed
  • It will lag 5-10 minutes behind reality
  • It has some small differences with the actual list and I'm not 100% sure of all reasons. For example, CF may delete some posts or auto-hide them, etc., which I don't.
  • Sadly, it does not show handle rating colors :-(
  • Archiving started around Sep. 3, 2019. Data from those early days data may be buggy.

The source code is https://github.com/royappa/cfblogs. Feel free to clone, add issues, pull requests, etc. Note, I am a beginner in this coding platform, this was a fun project to put together some things I have learned.

Read more »

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

By royappa, history, 14 months ago, In English,

Any general ideas on how to debug RUNTIME_ERROR on huge inputs in the systests? Here's my submission: https://codeforces.com/contest/1092/submission/47535638

  • I cannot copy the full input (it is truncated with "...") for local testing with gdb
  • I tried compiling with execinfo.h to use a stack backtrace handler, but that doesn't compile (no surprise)

My code gives RUNTIME_ERROR on test #7 and both times it says memory used is exactly 10000KB, but the memory limit is 256MB. It does seems odd that the crash would come at that exact point of memory (and both times).

Thanks for any tips on what I'm doing wrong. Not asking for algorithm help, as I have read the editorial. Just trying to implement.

Read more »

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

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

I am grateful the contest announcements have a link to the "timeanddate.com" converter.

But it would be truly convenient to see my local time in the email itself instead of UTC. It would be based on a timezone setting in the user's codeforces profile. I would love to see Attention! The round starts on MyOwnTime

Please consider this request. The email is inserting my username, so it is pulling one variable from the profile already. So hopefully, inserting a second one is not too hard.

Thanks!

Read more »

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

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

Dr. Kip Thorne from CalTech won the Nobel Prize in Physics today. Just writing on this forum to recommend his book "Black Holes and Time Warps". I think the audience here would really enjoy it, even though it is not related to computation.

I read it years ago and hardly understand any of the physics or math but it was a wonderful description of how Hard Science is done, the people doing the work, their personalities and arguments, etc. Highly entertaining!! He described working with many other Nobel Prize winners — before they were such, even.

Dr. Thorne is a great writer and he is also the executive producer of the movie "Interstellar". Rare example of crossover between hard sciences and artistic fields.

Read more »

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

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

I solved Topcoder SRM 607 Div. 1 250 using Linearity of Expectation in the practice room.
https://community.topcoder.com/stat?c=problem_statement&pm=12964&rd=15840

I brushed up the rules about Linearity of Expectation (LoE). The proof is easy algebra and using it is also easy.

But I still don't understand WHY it works here.

In this problem, suppose the concatenated input is "??". It has 3 substrings: the first "?", second "?" and the whole string "??".

The solution just separately generates every substring, finds the probability that it is a palindrome, and adds it all up, so we get 1+1+(1/26) = 2.038. Fine.

But for "??" to be a palindrome requires the first and second substring "?" to be the same letter chosen for the "??". I mean, if "??" = "bb" then the first substring also has to be "b" and the last substring also has to be "b".

So why can we just add up the palindrome probability of each substring independently without considering its matching with the other substrings?

Read more »

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

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

Hi, I believe on the USACO training site there was a problem that was to solve 8 queens but in a very, very tight time limit. So you had to keep optimizing first with simple stuff but then with symmetries and so on.

I never was able to get that under the time limit, it was many years ago, and I left the USACO site.

Now I thought of that problem again and was interested in trying it. I re-logged in to train.usaco.org after many years and my "DONE" and viewed problems are showing but I cannot find this one. I'm 90% sure it was at USACO and nowhere else.

Does anybody know the problem statement I'm talking about? Do you know if it's been removed from USACO? Thanks!

Read more »

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

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

In a topcoder problem recently, there was this definition:

Correct parentheses sequences can be defined recursively as follows:
* The empty string "" is a correct sequence.
* If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
* If "X" is a correct sequence, then "(X)" is a correct sequence.
* Each correct parentheses sequence can be derived using the above rules.

What is the purpose of the last line?

I've seen this type of extra condition many times and have to spend time thinking about whether it means something for the solution. Usually I can't think of something, and so (for me) it wastes time during a contest.

Read more »

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

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

Hello, I'm teaching myself the "Ionic" framework for fun and wrote an app to calculate the coding time for a problem in a Topcoder contest, based on points scored. There used to be some great websites for Topcoder utilities like this, but anyway, here is my small offering:

https://tctime.medalica.com/

Ionic is intended for mobile apps, so it will look best on a phone.

There is one bug which may amuse this audience to find: for a certain input, it shows a correct but wrongly formatted coding time. I'm sure there's more, so all suggestions and bug reports are appreciated.

Note, the app is of course free, but I plan to monetize it using the Reverse Knuth Model, meaning the first person to submit a bug report owes me $1, then the second owes me $2, the third owes me $4, and so on doubling each time.

I expect to retire soon!

Read more »

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

By royappa, history, 4 years ago, In English,

Small suggestion, would it be possible to indicate every contest's "rated" status in the title somehow, e.g.:

  • VK Cup 2016 — Round 2 (RATED)
  • VK Cup 2016 — Round 2 (UNRATED)
  • VK Cup 2016 — Round 2 (++)
  • VK Cup 2016 — Round 2 (NR)

Anything at all, it doesn't matter. As programmers I'm sure we'll get used to any notation.

Secondly or alternately, could we add a column to the Contests table, like this? I imagine "rated" is stored in the database already.

(The smileys are just a joke, folks, calm down!).

Read more »

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

By royappa, history, 4 years ago, In English,

This is a question about psychology, not about the best way to program something.

I have often felt that the top contestants seem to prefer writing DP solutions using for-loops and arrays, instead of memoized recursive functions.

Certainly there are times when one or the other method is "right" based on the density of the search space, depth of recursion etc. But often it doesn't matter, and in those cases, the top programmers overwhelmingly use loop+array. This seems counterintuitive to me because the loop+array approach often has corner cases to think about regarding array initialization and loop boundaries. Programming with a recursive function, on the other hand, seems to correspond more "naturally" with a mathematical expression of a recursive formula. The base cases are much simpler and correspond more directly with the math of the problem.

For a silly example, take f(n) = { if (n == 0) return 1; else return n*f(n-1); }, this is almost like the mathematical way of writing it (like this notation from Wikipedia ).

But in no math book would you see f[0] = 1; for (int i = 1; i <= n; i++) { f[i] = i*f[i-1]; }. That loop is not "the math way". Yet the top programmers seem to favor loops.

To test this theory I performed a rigorous scientific experiment. Here is the problem for topcoder TCHS 44 medium: https://community.topcoder.com/stat?c=problem_statement&pm=8250&rd=10795

It has a simple recursive solution. I then looked at ALL the red user submissions in the practice room, 32 total. This screenshot shows that the top 12 all used array+loop. The 13th used memoization (and his solution was faster — because even for those guys I think saving a few seconds thought on boundary cases makes a difference).

Of the 32 "red" solutions, only 6 used recursive functions.

We know the top guys are highly mathematically minded, so why don't they favor that style in their programming? Do they start out that way and then turn to array/loops after practicing lots of problems? Or do they start out writing like that the moment they encounter recursive solutions because that is the way their mind things? (bottom-up instead of top-down)? Do they hate writing a separate function when you can do everything in the main() ?

Would be curious to get anybody's thoughts, if they more naturally write loop+array, why they do so. And I don't know if it's just "top" programmers who do this or some set of people across all ranks. I mainly study top programmers solutions to learn, so my sample is obviously biased.

Read more »

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

By royappa, history, 4 years ago, In English,

Browsing codeforces on my phone while out and about on some useless errand or other is my habit.

To view solutions submitted by others during contests, one has to double click or control+click.

Neither of those work on my android phone. Double clicking just highlights the text and I can't figure out how to do a control click.

Has anybody figured out how to get that popup to come up, on an android smartphone? Or any workaround on android?

(More generally I am curious why doubleclick/control+click was chosen as opposed to just ordinary click to bring up the popup... maybe to prevent it happening accidentally during the rush of contests?)

Thanks!

Read more »

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

By royappa, history, 4 years ago, In English,

I can't get the compiler to find llabs() anymore. I've tried<cstdlib> and <cinttypes>

Or is this another thing they have irritatingly removed from C++11 along with my favorite operators like >?= . . .

Read more »

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

By royappa, history, 4 years ago, In English,

Hi, I'm working on http://codeforces.com/contest/580/problem/B and getting WA on test 7.
This is my code: http://ideone.com/IlboLx
I read the tutorial and it made sense, I'm just using upper_bound() instead of my own binary search.
Any hint on the bug would be great. Thanks!

Read more »

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

By royappa, 5 years ago, In English,

I've played in 3 contests now but am still not sure how to hack. First, I "lock" my solutions when they pass pretests. Then I look in the Standings area for other people with submissions that are in bold font. I doubleclick and/or control-click that cell.

I get a popup, but for other people the only thing I ever see is a single line like "00:06:47 Pretests passed [pretests] → 8184534". Clicking the submission number there, which is a link, does nothing, it just goes to the standings page.

If I do this on my OWN submissions, I see my source code in the popup.

I know this is a dumb question because I see other people are successfully hacking. :-) But any help would be appreciated. I've tried in Chrome and IE11 browsers. Thanks!

Read more »

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

By royappa, 5 years ago, In English,

Hi this is about problem http://codeforces.com/contest/471/problem/C

In the tutorial it shows that (N+F)%3==0 is needed for a house with F floors to be valid.

But I don't understand how this condition is enough for the requirement that "each floor has fewer rooms than the floor below it".

I mean, suppose we have make F=3 floors from 6 rooms. Then those floors can be arranged as having 3,2,1 rooms, which meet the requirement. But we could wrongly arrange the house as having 2,2,2 rooms as well. In both cases (N+F)%3==0.

In this example it doesn't matter. But how do we know in some case we would not be counting a wrong configuration of floors? Of course I cannot come up with a counterexample, I'm sure the tutorial is correct, but I just don't understand how "divisible by 3" also implies "decreasing rooms on each floor".

Thanks!

Read more »

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

By royappa, 5 years ago, In English,

Hi,

I'm looking at this problem http://codeforces.com/contest/467/problem/C and it is tagged as "DP" and "Implementation". My question is what the "implementation" tag means here.

I can understand there is a DP solution for it, but is there also a non-DP, purely "implementation" solution also? Or it just means, this is a DP problem, and you must implement it. What is the purpose of tagging this problem as "implementation"?

I hope writing a "blog entry" is the right way to ask questions, I can't find a "forum".

Thanks!

Read more »

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

By royappa, 9 years ago, In English,

It would be nice to have a CODEFORCES environment variable, to allow our programs to print debug output selectively.

Read more »

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