### removed1's blog

By removed1, 11 years ago, translation,

Problem A.

The constraint that edges of each flagstone much be parralel to edges of the square allows to analyze X and Y axes separately, that is, how many segments of length 'a' are needed to cover segment of length 'm' and 'n' -- and take product of these two quantities. Answer = ceil(m/a) * ceil(n/a), where ceil(x) is the least integer which is above or equal to x. Using integers only, it is usually written as ((m+a-1)/a)*((n+a-1)/a). Note that answer may be as large as 10^18, which does not fit in 32-bit integer.

Most difficulties, if any, contestants had with data types and operator priority, which are highly dependant on language used, so they are not covered here.

Problem B.

Let each letter representation of column number be associated with integer in radix-26, where 'A' = 0, 'B' = 1 ... 'Z'=25. Then, when converting letter representation to decimal representation, we take associated integer and add one plus quantity of valid all letter representations which are shorter than letter representation being converted. When converting from decimal representation to letter representation, we have to decide how many letters do we need. Easiest way to do this is to subtract one from number, then quantity of letter representation having length 1, then 2, then 3, and so on, until next subtraction would have produced negative result. At that point, the reduced number is the one which must be written using defined association with fixed number  of digits, with leading zeroes (i.e. 'A's) as needed.

Note that there is other ways to do the same which produce more compact code, but they are more error-prone as well.

Problem C.

The points can be vertices of regular N-polygon, if, and only if, for each pair, difference of their polar angles (as viewed from center of polygon) is a multiple of 2*pi/N. All points should lie on the circle with same center as the polygon. We can locate the center of polygon/circle [but we may avoid this, as a chord (like, say, (x1,y1)-(x2,y2)) is seen at twice greater angle from center, than it is seen from other point of a cricle (x3,y3)]. There are many ways to locate center of circle, the way I used is to build midpoint perpendiculares to segments (x1,y1)-(x2,y2) and (x2,y2)-(x3,y3) in form y = a*x + b and find their intersection. Formula y = a*x + b has drawback that it cannot be used if line is parallel to y, possible workaround is to rotate all points by random angle (using formulae x' = x*cos(a) - y*sin(a), y' = y*cos(a) + x*sin(a) ) until no segments are horizontal (and hence no perperdiculares are vertical).

After the coordinates of the center are known, we use fancy function atan2, which returns angle in right quadrant: a[i] = atan2(y[i]-ycenter, x[i]-xcenter)

Area of  regular polygon increases with increasing N, so it is possible just to iterate through all possible values on N in ascending order, and exit from cycle as first satisfying N is found.

Using sin(x) is makes it easy: sin(x) = 0 when x is mutiple of pi. So, for points to belong to regular, N-polygon,

sin( N * (a[i]-a[j]) /2 )=0

because of finite precision arithmetic,

fabs( sin( N * (a[i]-a[j]) /2 ) ) < eps

• +12

 11 years ago, # |   0 You can use TeX for the mathematical formulas.
•  11 years ago, # ^ |   0 How?
•  11 years ago, # ^ |   0 frac{x}{y} = 3 frac{x}{y} = 3 for example.
•  11 years ago, # ^ |   0 oops..
•  11 years ago, # ^ |   0 How do you expect me to guess which source code did you write?
•  11 years ago, # ^ |   0 (shift+4)\frac{x}{y}(shift+4)
•  6 years ago, # ^ | ← Rev. 2 →   0
•  2 years ago, # ^ |   0
 11 years ago, # |   0 Problem B.I can't pass Test case 6.I don't konw why? Isn't there a test case like:Input: R001C001Ouput: 00A001?
•  11 years ago, # ^ |   0 My AC program give A001
•  7 years ago, # ^ |   0 No leading zeros needed. "A1" is correct.
•  10 years ago, # ^ |   0 R288C494 check this input. (Tricky one :D)
•  7 years ago, # ^ |   0 It is "RZ288".
•  5 years ago, # ^ |   0 Thanx for the test case. Found the problem in my code! :-)
•  7 years ago, # ^ |   0 You cannot have zeros in letter numbering. "00A" is incorrect, it should be only "A". "001" is not incorrect, but the leading zeros are unnecessary, it can be simply "1". I doubt though that there are numbers with leading zeros in the official test cases, it is simply "R1C1" or "A1".
 11 years ago, # |   0
 11 years ago, # |   0 Who can give me the data on test 6？Why I always get WA、
•  11 years ago, # ^ |   0 test 6 is very big (1000 lines)try to check this test instead:13R1C17R1C18R1C19R1C20R1C21R1C22R1C23R1C24R1C25R1C26R1C27R1C28R1C29after passing this I got AC.
•  10 years ago, # ^ |   0 This is what I got,Q1R1S1T1U1V1W1X1Y1Z1AA1AB1AC1Which i believe is the correct solution. But it still wouldnt pass test 6 :(
•  10 years ago, # ^ |   0 Me too.
•  7 years ago, # ^ |   0 My program that got AC says "R288C494".
•  7 years ago, # ^ |   0 This is correct.
 » 9 years ago, # |   0 B: what about "R1C204152" answer:"KOYZ169801"
•  » » 7 years ago, # ^ |   0 That is incorrect. The correct answer is "KOYZ1". The cell is obviously in row 1.
•  » » » 7 years ago, # ^ |   0 -#,long long ago !
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 So what?
 » 8 years ago, # |   +1 When I use ceil((float)N/A) for problem 1A, it gives wrong answer while it gives a correct answer when I use ((N+A-1)/A). What is the catch behind it?
•  » » 8 years ago, # ^ |   0 Use double, Luke
•  » » » 7 years ago, # ^ |   0 Can ceil() give wrong result if it is fed with float value? It "should not",though; because doesn't it convert that float to double implicitly? and also, there should not be any problem of precision as it is lower to higher precision conversion. I am kind of novice in programming.
•  » » 7 years ago, # ^ |   0 float has very low precision. Best stay away from it, use double.
•  » » » 4 years ago, # ^ |   0 I use double,but the answer is wrong(case 10).I don't know why.
 » 8 years ago, # |   -8 Hello :) How do I represent 10^9 integers and input integers separated by space in a single line in C language?
•  » » 7 years ago, # ^ |   0 For integers up to 10^9, you can use the 32-bit integral type long int. But if you multiply them, you have to use a 64-bit type, like long long int, otherwise the multiplication will overflow.As for input, the proper way to input a 32-bit integer on Codeforces isscanf ("%ld", & integer);and for a 64-bit integerscanf ("%I64d", & integer);
 » 7 years ago, # |   0 I can't pass case 47 of problem C. But the output is correct when I run locally. The error message is 'Verdict: RUNTIME_ERROR'
 » 7 years ago, # |   0 Can someone help me in problem 1B ? 1B - Spreadsheetexcept this one "R1C204152" answer:"KOYZ169801", all the test cases which users gave in comments run on my machine. Help me please
•  » » 7 years ago, # ^ |   0 The correct answer to the test case "R1C204152" is "KOYZ1". The cell is obviously in row 1. I got AC on this problem today.
•  » » » 7 years ago, # ^ |   0 Okay I mended my one as well to get KOYZ1 but still it fails test 6. Wanna see my code ?
•  » » » » 7 years ago, # ^ |   0 Yes, please.
 » 7 years ago, # |   0 I am a novice C language，I run my program with VC 6.0 the answer of test 1:"BC23" is "R23C55", but when I submit my program it show "Wrong answer on test 1",and I see it show my answer of "BC23" is "R23C53",I don't know how to solve my problem,because I select “GUN C 4”?Please help me!Thanks!(by the way my English is so poor,Do not care about my grammar errors on English.)[submission:6296049][problem:1B]
 » 7 years ago, # |   0 I have been trying 1B. But getting Runtime error. Here other people also have said same but no reason mentioned. Please suggest me what's wrong.
•  » » 7 years ago, # ^ |   0 Try this cell: R1
•  » » » 7 years ago, # ^ |   0 It got AC thanks. I didn't think of this cell.
 » 7 years ago, # |   0 Problem B. My submission: here WA on test 6, but I can't trace this big test case. Can anyone help me with a one that can be traced and hacks my code? Thanks in advance.
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 Have you scrolled to the bottom of the submission report? 1 R228C494 
 » 6 years ago, # |   +2 I can't solve problem A, please help me. I was using a 2D-Segment Tree to simulate the squares, but I got WA. I need help. If you help me, I'll give you a big hug.
•  » » 5 years ago, # ^ |   0 Tip: Solve the problem first in one dimension. Look for an analytical solution of the problem, no advanced data structures are needed.
 » 5 years ago, # |   +5 Please help: Why I'm getting a different output on different systems for Problem B sample test cases?On my system: On CF system: My submission: 16392041
•  » » 5 years ago, # ^ |   0 pow pow pow... How many bugs with it. Write your own function.
•  » » 5 years ago, # ^ |   0 ull getColNumber(string s) { ull n = 0; for (int i = s.size() - 1, j = 0; i >= 0; i--, j++ ) { n += (pow(26, j) * (int)(s[i] - 'A' + 1)); } return n; } here is some data loss because pow() returns double so i used double to calculate colNum and it worked !!
•  » » 3 years ago, # ^ |   -6 Did you get correct result .me also facing same problem.
 » 5 years ago, # |   0 Why is this C++ solution fails on 9th test #include using namespace std; int main() { int n, m, a; cin >> n >> m >> a; int answer = ((n+a-1)/a)*((m+a-1)/a); cout << answer; return 0; } But this Python solution is correct? n, m, a = map(int, input().split()) answer = ((n+a-1)//a)*((m+a-1)//a) print(answer) 
•  » » 5 years ago, # ^ |   0 Note that answer may be as large as 10^18, which does not fit in 32-bit integer.
•  » » 15 months ago, # ^ |   0 in cpp all the variables should be long long
 » 5 years ago, # |   0 I've tested all the cases from the comments section but it still does not pass test no 6. Rather it keeps on showing Runtime error. Submission no 18746719 please help!
 » 5 years ago, # |   0 Problem B I've tested all the cases explicitely suggested in the comments below but still cannot pass test 6. Shows Runtime error. Submission: 18746719 Please help!
•  » » 4 years ago, # ^ |   0 are you OK?
 » 4 years ago, # |   0 what datatype can i use to this big number in java? numbre: 1000000000000000000
•  » » 4 years ago, # ^ |   0
•  » » » 4 years ago, # ^ |   0 i try to multiplicate 1000000000X1000000000 and i want that the result was 10000000000000000000, but when i try do this operation in java, the answer of the multiplication give me how result this number -1486618624 whit datatype long and int and BigInteger.
•  » » » » 4 years ago, # ^ |   0 You have to store 1000000000 in a long also, if you want to make operations on it which makes it become a long. You can cast it meanwhile operation too, so you can do ((long) 10000000000)*10000000000, and it will give correct result.Long can handle numbers up to 9*10^18, for numbers bigger than that you need to use BigInteger.
 » 3 years ago, # |   0 I found another solution for B here is my code: 33646284
 » 3 years ago, # |   0 can someone help me with the concept of epsilon in finding the gcd. Why do most of the accepted answers have it as 10^-4 . when i reduce it to 10^-5 , i get incorrect answer. Can someone tell me how did we decide this value because i think that lesser the value of eps meant a more precise answer??
 » 3 years ago, # |   0 Would love some explanation on problem a answer. I know with (m+a-1)//a*(n+a-1)//a would give the right result but it would help a ton if someone can collaborate on how to reach to this conclusion. Thank you in advance.
•  » » 2 years ago, # ^ |   0 Just draw the diagram and it will be clear to you :-)
 » 2 years ago, # |   0 i keep getting Wrong answer on test 9 on the A problem anyone knows the solution ??
 » 21 month(s) ago, # |   0 can anyone explain me why my code is not passing testcase 6. https://codeforces.com/contest/1/submission/58648097
•  » » 20 months ago, # ^ |   0 I also wa on the test6, especially why the R228C494 transform to the answer RZ228? I think the answer should be SZ228
 » 19 months ago, # |   0 Here is my code for problem 'B'. It works correctly on my system but gives wrong answer here. I can't seem to find the mistake.Please help me out. Thanks in advance :)https://pastebin.com/YUV7wKzv
 » 18 months ago, # |   0 Can anyone post some materials regarding problem C Im not able to understand the math behind it. Thanks!
 » 13 months ago, # |   0 My BFS code which produces MLE for B: 75570425. MLE rarely happens but this time memory Limit is small, and the Time limit is 10 sec.
 » 13 months ago, # |   0 Can someone please share their code for A. I am not able to get the correct precision. The output shows 1e18 when I use cout. But when I assign the value to a long long variable then I get a wrong answer. cout << (ceil(n/a) * ceil(m/a)) ; //gives output as 1e18 ll ans = (ll)(ceil(n/a) * (ll)ceil(m/a)) ; cout << ans ; Upon this, I get the wrong result as shown: 1000000000 1000000000 1 999999984306749440
 » 13 months ago, # | ← Rev. 2 →   0 https://codeforces.com/contest/1/submission/77144010 I'm getting RTE at TC 7. Please help!
 » 9 months ago, # |   -9 I think an easy to understand solution of Problem 1B
 » 9 months ago, # |   0 if i try to use long long in c++ to not get an overflow it works fine on my pc, but when i try to submit it on codeforces i get the error: "Field cannot contain binary data". I can't seem to find any solutions online. can anyone help me?
•  » » 9 months ago, # ^ |   0 Oh i have the same problem. It caused error with my code on test 9. However, when i run it on repl.it or other online compilers, test 9 works well and passed.
•  » » » 9 months ago, # ^ |   0 i think its a server problem, because i tried uploading the same unedited file a few hours later and it worked fine.
 » 8 months ago, # |   0 could someone explain why we add a to m them subtract 1 ((m+a-1)/a) in problem A
•  » » 8 months ago, # ^ |   0 When there is a remainder, the result will not be smaller by one
•  » » 8 months ago, # ^ |   0 Subtracting 1 is to prevent the result from being larger when there is no remainder
•  » » » 8 months ago, # ^ |   0 sorry didn't get it could you provide an example with numbers if you don't mind
 » 3 months ago, # |   0 what about the last test case for problem A? Note that answer may be as large as 10^18, which does not fit in 32-bit integer. what to do to make it fit?
 » 7 weeks ago, # |   0 I can not pass problem B. It tells me I got "wrong time error on Test 6". mine is OK on 'R288C494'. Is it because Python is slower? def func_1(s): c=0 x=0 for i in range(len(s)): if s[i].isdigit(): x=i break for i in range(x): c+=(ord(s[x-i-1])-64)*(26**i) r=eval(''.join(s[x:len(s)])) print('R{}C{}'.format(r,c)) def func_2(s): x=0 for i in range(1,len(s)): if s[i]=='C': x=i break r=eval(''.join(s[1:x])) c=eval(''.join(s[x+1:len(s)])) d='' while True: c,num=divmod(c,26) if num==0: d='Z'+d c-=1 else: d='%s'%(chr(num+64))+d if c==0: break print('{}{}'.format(d,r)) a=eval(input()) for _ in range(a): s=input() if s[0]=='R' and s[1].isdigit(): func_2(s) else: func_1(s) 
•  » » 6 weeks ago, # ^ |   0 I get the same problem with you.
 » 6 weeks ago, # |   0 Problem B： I can't pass the test.6 though i have tried the input"R288C494" the output i get is"RZ288" can anybody help me? Please~
•  » » 8 days ago, # ^ |   0 Hi! I have this problem too, but I think that true, because i solved myself and i got SZ288 and i checked on the web-site "Base Conversion Tool" and answer was "SZ".
 » 9 days ago, # |   0 [HELP] I am obtaining different answers on my machine and Codeforce Judge and I can't understand why. The test case is "1000000000 1000000000 1". Judge shows that my output is a negative number (which indicates some overflow), but it works when I test on my machine.Here's the link to my submission : https://codeforces.com/contest/1/submission/115088752