royappa's blog

By royappa, history, 22 months ago, In English

Does anyone have a link or copy of the 1989 ACM national championship problem set? Just a PDF would be fine but if the problems are in some online solver that would be even better.

I participated in it (for Purdue, we finished 9th I think), and would love to try solving that set now, many years later. I can't find it online.

Thanks!

Full text and comments »

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

By royappa, history, 22 months ago, In English

Is there anywhere online where I can find some variation of this problem to solve, other than SPOJ?

https://www.spoj.com/problems/DECFRAC/

It's marked as "Hidden" in SPOJ due to some issues. I wrote a program for repeated decimal fractions and would like to test it somewhere reliable, and I'm not sure if solving a "hidden" problem in SPOJ is allowed. I did search Codeforces briefly and there's a lot of fraction problems but didn't easily find one that is just nothing more than "output A/B with the repeating decimals marked somehow". Thanks!

Full text and comments »

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

By royappa, history, 4 years ago, In English

I finally upgraded to Windows 10 (after 10 years of Windows 7 .. sob). The Topcoder applet is blurry which I can live with, but the dropdown of practice rooms is so long that it extends above and below my entire screen. I can't reach SRM 800. Is there a "/" command (like "/search ") for directly going to a given room? Thanks.

Full text and comments »

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

By royappa, history, 4 years ago, In English

I seem to remember, but cannot find, a tutorial posted here on how to use new features in C++ to print things more easily from cout.

It showed how to set it up so you can do "cout << x" on several common data structures (vectors, pairs, maps, etc.) and it would print them, e.g., a vector may print out as "32 12 45\n". Of course you would have to implement some code for each datatype you want.

If someone remembers this tutorial or can show how, I would appreciate greatly. Thanks!

Full text and comments »

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

By royappa, history, 4 years ago, In English

OK so I came across an old Google Doodle recently:

https://www.google.com/doodles/celebrating-50-years-of-kids-coding

It is to write six programs in that applet using a block language (like MIT Scratch). Very cute.

Now, Google gives you a ribbon if you write the shortest code (in terms of blocks). The steps in their shortest code program is shown in the screenshot below, it's the number inside the ribbon. To be very clear, this is like shortest lines-of-code, not fewest runtime steps. A short program may not be efficient.

Now for the challenge: I was able to solve that last program with 5 blocks instead of Google's shortest solution of 6. So, see if you also can do better than Google's shortest solution, on any of the programs. I could only improve the last one.

And don't forget to share this with your young friends who might be interested in coding!

image

Full text and comments »

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

By royappa, history, 5 years ago, In English

Bored stuck at home? Waiting for next contest? Here is an archive of CF forum posts:

https://codeforces-blogs.web.app/home

It goes back to roughly Sep. 2019. Enjoy :-)

p.s. The site is slow and probably has some bugs.

Full text and comments »

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

By royappa, history, 5 years ago, In English

Hello, I'm enjoying GCJ 2020 and hope everyone is too. ***

While competing I ran into some minor issues and made a list to send to Google for feedback. Then I thought about posting here so that others can add their suggestions also, and maybe Google could make some changes next year (thanks in advance!).

  • Show the language version in the dropdown, or at least somewhere more clearly.
    Explanation: I assumed C++ would be the most recent version but my first submission was a compiler error, so I wasted time before thinking it might be a version issue. (I had tried "for (auto [r,c] : p)" where p was a pair<int,int>. This works in C++17 but not C++14). This is documented in the FAQ, but I didn't read that until later. Also, the "Syntax pre-check" control didn't flag this... or any syntax errors for that matter. Anyone know what it does?

  • Add the test number to the result messages, e.g., "Test Set 2: passed" or "Test Set 2: Wrong answer".
    Explanation: Again, my bad for not reading the rules, but even after reading them, the difference between messages like "Sample Failed: WA" and just "Wrong Answer" is not very clear. I originally thought it was like previous years where you submit a "small" and get some points, then submit a "large" and get some points. Since we have new rules of "samples" and "tests", just numbering those hover messages with the Test Number (matching the problem statement) would be nice.

  • Instead of hiding the bottom row, just grey out the "Submit attempt" button.
    Explanation: If you click the "eye" icon to view your code from a previous attempt, the bottom row with the Submit button goes away. I did that to look at an old submission, and then could not resubmit. The issue was, I had also scrolled the left pane with the problem text, so that the "eye" icon was no longer visible; and I had forgotten that I clicked it. So I was really puzzled how to resubmit until I realize you have to re-click the eye icon.

  • A "Copy to Clipboard" next to the sample input would be cool :-)

  • Allow the usual Google account selector like any other Google app.
    Explanation: I have a corporate gmail account from my company and also my personal gmail account. When registering and competing, it always chose the former and did not let me switch to the latter. So I have to use Chrome Incognito mode and login to my personal gmail account to compete. It seems like this Google app should have the round "account chooser" icon. (There is a round icon but it does not bring up the accounts).

*** Well, except for that interactive problem. I don't like interactive problems.

Full text and comments »

Tags gcj
  • Vote: I like it
  • +51
  • Vote: I do not like it

By royappa, history, 5 years 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.

Full text and comments »

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

By royappa, history, 6 years ago, In English

Any general ideas on how to debug RUNTIME_ERROR on huge inputs in the systests? Here's my submission: https://codeforces.net/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.

Full text and comments »

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

By royappa, history, 6 years 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!

Full text and comments »

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

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

Full text and comments »

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

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

Full text and comments »

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

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

Full text and comments »

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

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

Full text and comments »

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

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

Full text and comments »

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

By royappa, history, 9 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!).

Full text and comments »

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

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

Full text and comments »

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

By royappa, history, 9 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!

Full text and comments »

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

By royappa, history, 9 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 >?= . . .

Full text and comments »

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

By royappa, history, 9 years ago, In English

Hi, I'm working on http://codeforces.net/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!

Full text and comments »

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

By royappa, 10 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!

Full text and comments »

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

By royappa, 10 years ago, In English

Hi this is about problem http://codeforces.net/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!

Full text and comments »

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

By royappa, 10 years ago, In English

Hi,

I'm looking at this problem http://codeforces.net/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!

Full text and comments »

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

By royappa, 13 years ago, In English

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

Full text and comments »

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