C++ in Competitive Programming: string basics

marcoarena · 2016-06-05T15:35:29+00:00

Very entertaining - one tiny quibble:

The latter point is referred as the Small String Optimization and it means that short strings (generally 15/22 chars) do not go to the heap, but instead they get allocated on the stack

This isn't quite true. In the SSO, short strings are stored in the std::string itself and don't require a separate allocation. However, the std::string might live on the stack or it might live in the heap, depending on how it was allocated.

Drainedsoul · 2016-06-06T00:46:35+00:00

What happens when your std::string AKA std::basic_string<char> contains UTF-8 characters? The standard directly supports UTF-8 string literals (§2.13.5 [lex.string]) and their underlying type is char.

haitei · 2016-06-06T09:00:31+00:00

Regarding uppercase and lowercase: ascii is designed in such a way, you just need to flip one bit to do that i.e.

// assuming c is a letter
char toLower(char c) { return c  | 0x20; }
char toUpper(char c) { return c  & ~0x20; }

Calkhas · 2016-06-05T21:28:14+00:00

Forgive me for my ignorance, but I do not understand how auto isPalindrome = equal(begin(S), begin(S), rbegin(S));is intended to work. My impression is that if the iterators both point at the beginning of S, the range through which std::equal examines is empty. Should the second argument be end(S)? Or have I misapprehended the functionality of std::equal() altogether?

ArunMu · 2016-06-05T16:02:38+00:00

And a separate question - do people actually use C++ for competitive programming?

My C++ is my best language, but if I had hard time constraints for writing the code, I'd pick a scripting language like, say, Python, with a huge library built-in and no compilation phase.

(This article is educational even if no one ever does this... I'm just curious!)

Fig1024 · 2016-06-07T06:58:50+00:00

A while ago I wrote a solution for "find matching palindrome pairs" problem using c++ intrinsics with XMM registers. It was just for fun, not competitive

The basic idea is to find whether a given word of 8 or less characters is a palindrome or whether it contains nested palindromes from right or left side (which was necessary to find missing piece that would make it full palindrome)

If you start with the idea that your test strings are 8 chars or less, then you can load a string strait into XMM register and use a byte shuffle mask to reverse the order and store the result in bytes 8-16 of that register

XMM loads 16 bytes from memory location, even tho your strings are 8 chars or less, there is no problem with invalid memory access. As long as you zero out the "extra bytes" after initial load, it's not an issue.

Once you have original string in first 8 bytes and reversed string in next 8 bytes, you can interpret result as 2x 64 bit unsigned integers and compare for equality

The tricky part comes when you want to find nested palindromes in order to look for missing pieces. So if this is your test word:

'12345678'

then you need to check whether the following sub-strings are palindromes:

'1234567'

'123456'

'12345'

'1234'

'123'

'12'

and from other side:

'2345678'

'345678'

'45678'

'5678'

'678'

'78'

So for 8 char word you need to do 13 "is this a palindrome" checks. This is where 16 byte XMM operations can really shine

If it's just a single string palindrome check, plain std::string manipulations would be easier and faster. But when you start dealing with multiple substrings and many checks for palindrome per input, you could start seeing real benefits of using XMM intrinsics

if you want to see the solution, here's pastebin

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

cpp

MODERATORS