Unnecessary Details: 1B — Spreadsheet

Правка en15, от jsgoller1, 2022-07-04 01:15:59

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. Using unsigned ints means we can't compute negative powers, 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

However, the solution does none of these:

Solution

Let's take this apart, starting with for(x=0,p=s;*p>64;++p). After sscanf() returns 0, x and y are uninitialized, so x is zeroed and will store the value of the column string as it's converted to base-10. We also set p to the first character in the string. On each iteration, we increment p (which will add 1 byte to the address) and then evaluate it.

Our termination condition is that the character p points to is less than 64; 65 is the ASCII code for A, so during each iteration of our loop p must point to a char that represents some letter from A-Z. The problem ensures each test case is a valid Excel or RC string, so while a test like *p>64 && *p < 91 would be more correct, it isn't necessary. When the loop ends, it will thus point to the first number in the string, i.e. the row portion of the string. We will then be able to print it directly, since it's already in base-10.

The next line is the most confusing: x=x*26+*p-64;. First, what does it actually do? Let's add parens to make order of operations explicit: 1. Dereference: x*26+(*p)-64 1. Multiplication: (x*26)+(*p)-64 1. Add / sub, with L-to-R associativity: ((x*26)+(*p))-64

The entire result is stored in x repeatedly, so we can use substitution and write an entire loop as a single line. Using the previous example of converting RZA to 12845:

(((((((((0*26)+(82))-64)*26)+(90))-64)*26)+(65))-64)

then drop some redundant parens to get

((((0*26)+(82-64))*26+(90-64))*26+(65-64))
((((0)+(18))*26+(26))*26+(1))
((18*26+(26))*26+(1))
((468+26)*26)+1
12845

История

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