Unnecessary Details: 1B — Spreadsheet

Revision en10, by jsgoller1, 2022-07-04 00:42:21

1B - Spreadsheet was extremely challenging for me; it took me over 2 hours to get AC. I didn't find the editorial helpful, and then when I went to see practice solutions from red/orange people, it made even less sense (they were basically copy/paste with minor variation):

Solution

I'll talk about each part of the problem itself and approaches/alternatives, and then explain how the above solution (henceforth "the solution") handles it. I'll go into unnecessary detail since I'm very new to CP/CF and would've wanted this level of detail myself.

Problem statement

Input: First line is an int representing the number of test cases. Each following line is a string of characters specifying a spreadsheet cell, in one of two formats:

  • "Excel": ^[A-Z]+[0-9]+\$ (e.g. BB352).
  • "RC": ^R[0-9]+C[0-9]+\$ (e.g. R253C55).

Output: For test case, we must output the same cell specified in the opposite format. Example:

2
R23C55
BC23

should output

BC23
R23C55

Constraints:

  • Between 1 and 10000 test cases (all valid in either format)
  • In each case, the row and column numbers are no larger than 1000000 (so each line is 16 chars at longest since we never exceed R1000000C1000000 / BDWGN1000000).

Approach

Our implementation needs to do 3 things:

  • Convert from Excel to RC
  • Convert from RC to Excel
  • Determine which format the input is in, and do the right conversion on it

The heart of this problem is a change of base; RC-format uses two base-10 numbers, whereas Excel uses one for rows and a quasi-base-26 character string for columns.

Determine format

Note that for RC format, we will always find a C after some numbers in the string, whereas with Excel we will never find any letters after numbers. We could use this as a test of format with something like:

Solution

The solution does this in a better way:

Solution

The string %*c%d%*c%d will match on the RC format, but not Excel; %*c matches on and throws away any non-numeric characters, whereas %d matches on numeric characters and stores them in the respective variable. For an RC string, R and C are thrown away but the numbers following them are stored in x and y (so (sscanf() will return 2). On an Excel string, this won't match so nothing is stored in x or y (and sscanf() will return 0).

Excel to RC conversion

This is the easier conversion, conceptually. We can copy the row portion and print it as-is. For the column portion, we have to convert from base-26 to base-10. A base-10 number represents addition of successive powers of 10, each times a constant: 12345 in base-10 means 5*(10^0) + 4*(10^1) + 3*(10^2) + 2*(10^3) + 1*(10^4). So for the column string, we can map each letter to a number (i.e. A=1, B=2, ... , Z=26) and then associate each with a power of 26. Consider RZA: A=1, Z=26, and R=18, so we can write it as 1*(26^0) + 26*(26^1) + 18*(26^2) = 12845.

We have a problem: C++ has no built-in for integer exponentiation. There are a couple workarounds. We could try writing one ourselves:

Solution

or

Solution

The iterative version is slightly faster (by a few ten-thousandths of a second on my machine, probably due to the time involved with stack frame creation/cleanup) but we have bigger problems to worry about. Neither of them handle negative exponents, but those are ruled out by the problem statement so again we don't care.

Another approach would be to use a hashtable for powers of 26 since the problem constraints mean we'll never compute 26^n for n > 4 (though this requires more code):

Solution

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en28 English jsgoller1 2022-07-04 03:21:00 5 Tiny change: 'ut**: For test case' -> 'ut**: For each test case'
en27 English jsgoller1 2022-07-04 03:15:03 2
en26 English jsgoller1 2022-07-04 03:13:58 17 Tiny change: ' variation):\n\n<spo' -> ' variation of the following):\n\n<spo'
en25 English jsgoller1 2022-07-04 03:12:12 31 Tiny change: 'in any way. ' -> 'in any way (I'll publish edits over time). ' (published)
en24 English jsgoller1 2022-07-04 03:11:19 421
en23 English jsgoller1 2022-07-04 03:04:47 625
en22 English jsgoller1 2022-07-04 02:45:35 928
en21 English jsgoller1 2022-07-04 02:06:15 573
en20 English jsgoller1 2022-07-04 02:00:38 735
en19 English jsgoller1 2022-07-04 01:45:29 1172
en18 English jsgoller1 2022-07-04 01:42:24 1138
en17 English jsgoller1 2022-07-04 01:22:39 337
en16 English jsgoller1 2022-07-04 01:19:48 535 Tiny change: 'xplicit:\n1. Deref' -> 'xplicit:\n\n1. Deref'
en15 English jsgoller1 2022-07-04 01:15:59 6
en14 English jsgoller1 2022-07-04 01:15:33 700
en13 English jsgoller1 2022-07-04 01:09:00 729 Tiny change: 't. \n\n### `for(x' -> 't. \n\n#### `for(x'
en12 English jsgoller1 2022-07-04 00:54:11 319
en11 English jsgoller1 2022-07-04 00:48:02 426
en10 English jsgoller1 2022-07-04 00:42:21 997
en9 English jsgoller1 2022-07-04 00:38:16 1026
en8 English jsgoller1 2022-07-04 00:20:29 31 Tiny change: 'ter way:\n~~~~~\ni' -> 'ter way:\n<spoiler summary="Solution">\n~~~~~\ni'
en7 English jsgoller1 2022-07-04 00:20:07 13 Tiny change: '.\n~~~~~\n\nThe so' -> '.\n~~~~~\n</spoiler>\n\nThe so'
en6 English jsgoller1 2022-07-04 00:19:35 1292
en5 English jsgoller1 2022-07-04 00:04:48 418
en4 English jsgoller1 2022-07-03 23:58:46 988 Tiny change: 'aints**:\n- Betwee' -> 'aints**:\n\n- Betwee'
en3 English jsgoller1 2022-07-03 23:48:17 48
en2 English jsgoller1 2022-07-03 23:47:33 4 Tiny change: 'iation):\n~~~~~\n ' -> 'iation):\n\n~~~~~\n '
en1 English jsgoller1 2022-07-03 23:47:16 745 Initial revision (saved to drafts)