muxecoid's blog

By muxecoid, history, 17 months ago, In English

For quite some time I am using codeforces for candidate screening in job interviews.

One common suggestion to improve problem statement clarity is to add examples of invalid inputs to problems with constrains.

For example in 1469A - Regular Bracket Sequence multiple candidates misunderstood the requirement of exactly one '(' and one ')', perhaps because the brace symbol itself was not quoted. Without quotes () looked like a part of sentence to some.

The following examples could be used for such problem to improve clarity

Too many braces

  1
  (())

Not enough braces

  1
  (????????????????

Input overly long

  1337
  .....
  .....
  .....

Full text and comments »

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

By muxecoid, history, 23 months ago, In English

First 3 problems were kinda easy. Grime Zoo also felt easy at first. Quickly wrote a quick DP solution and only 40 minutes after the match I finished debugging the last bug. When problem is all about 01 you have many places for off by one mistakes. I must practice more.

My general idea for Grime Zoo was simple, at any specific point in string you have given number of question marks. Any fraction of them could be used as 1s. So you store the lowest number of comments obtainable for each number of 1s and advance from there.

And even version after additional debugging passed only the pretests.

Full text and comments »

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

By muxecoid, 7 years ago, In English

Just something curious that I just noticed during practice.

std::map::upper_bound returns iterator to the first element with key strictly greater, than argument.

By intuition of symmetry one could expect std::map::lower_bound to return iterator to the last element with key strictly less, than argument. In fact it returns iterator exactly one after it.

What is the reason for this asymmetry? This is because map::end() points at one position after the last element, if we search for element greater than largest key in map upper_bound has a reasonable iterator to return map::end. map::begin() points at first element. To provide API symmetry lower_bound would need to return map::prebegin() which does not exist in standard. This way asymmetry between begin() and end() leads to asymmetry between lower_bound() and upper_bound().

What other cases of asymmetry are there in STL?

Full text and comments »

Tags c++, stl
 
 
 
 
  • Vote: I like it
  • -16
  • Vote: I do not like it

By muxecoid, 7 years ago, In English

After not participating in topcoder competitions for 4 years I'm rather rusty. Topcoder algorithm competitions seem to be in a bit of decline now (correct me if I'm wrong) so I decided to switch to codeforces. Here are my notes on differences from topcoder format and other observations.

  • Arrays are 1-based

Looks like whoever wrote the guidelines for codeforces is a huge fan of Pascal language. If you are used to C++ convention favored by topcoder you will lose time trying to understand why the answer in subject cases is like it is and also fixing your code when you realize you implemented 0-based output.

  • Standard input, standard output

In topcoder your IO is through STL/C#/Java containers. Here you must parse IO. This reminded me how rarely I used scanf and cin in my life before.

  • Problems with multiple solutions

In case there are many solutions print any of them. If your solution for sample case does not match sample solution you are not necessary wrong.

  • Score for all problems is from start of contest, not from opening specific problems

It may be a good idea to read all problems before attempting to solve the first and decide which to solve first.

  • I need a proper IDE

Running stuff in ideone.com is too slow. Must compile locally. I'll give CodeLite a try.

  • I need more snippets

A bigint library is a must for a C++ contestant like me. I was too lazy to find one while on topcoder, now is the time. Some IO utilities would be nice. Refactor everything I used during contest and feel I may need to use again as a snippet.

Edit — messed up the markup syntax

Full text and comments »

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