Page 3 of 5

problem 128 + general question about speed

Posted: Wed Oct 01, 2003 11:17 am
by Maarten
I'm just wondering, how do people get those *really* low execution times ? For example in problem 128, the program runs in 0.6 seconds, but the fastest solution in 0.06 seconds, which is about 10 times faster! There might be some optimization possible on my code, but I'm quite convinced there's not THAT much to gain! After all, I have to read all the input at least once...

btw, my code is:

[cpp]
#include <stdio.h>

#define LONG unsigned long

int main(int argc, char *argv[])
{
LONG g = 34943;
char line[1025];
while( gets(line) != NULL ) {
if( line[0] == '#' ) break;
LONG message = 0, pos = 0;
while( line[pos] != 0 )
message = ((message<<8) + line[pos++])%g;
message = (message<<16)%g;
LONG crc = (g - message)%g;
printf( "%02X %02X\n", (crc & 0xFF00)>>8, crc & 0xFF );
}
return 0;
}
[/cpp]

Posted: Thu Oct 30, 2003 4:55 am
by zaghaghi
you can set the ios::uppercase flag for cout.
you can use setf member function of cout to set this flag :

[cpp]
cout.fill('0');
cout.setf(ios::uppercase);
cout<<hex<<setw(2)<<nHigherByteCRC<<" ";
cout<<hex<<setw(2)<<nLowerByteCRC <<" "<<endl;
[/cpp]

and for unsetting this flag use unsetf member function of cout.

from Presentation Error to Accepted...

Posted: Wed Nov 26, 2003 7:18 am
by chicapi
They always have a trick.

You should have noticed that hexa numbers in the output are in UPPER case and C printfs them is lower case...

then you get AC!! :D

Posted: Thu Apr 29, 2004 12:34 pm
by Corpse Fiend
Can someone explain the "generating CRC - for dummies" algorithm? I can't understand it. :|

Posted: Thu Apr 29, 2004 1:09 pm
by Dominik Michniewski
to chicapi:
read carefully manual for printf() function - exist flag to output hexadecimal numbers in uppercase :-)

Bes regards
DM

128 (CRC) - example data

Posted: Fri Aug 27, 2004 2:57 am
by bowman
Hi,

given all I know about CRC calculation and the Polynomial p = 0x887F (34943 in decimal), I cannot verify the example data. No matter if I use a program or pen and paper, I get 0x3643 as the CRC for "A".

Am I doing something wrong or is the example data incorrect?

I will NOT calculate the CRC of "this is a test" on paper! ;)

Posted: Sat Aug 28, 2004 5:58 pm
by Stas
Hi,

you can verify the example data like this:

m = "A" = 65 decimal = 0100 0001

"2" = 0x0C86 = "0000 1100 1000 0110"


g = 34943 decimal = 1000 1000 0111 1111
The CRC value is chosen so that ``m2'' when divided by a certain 16-bit value ``g'' leaves a remainder of 0.
so,

0100 0001(m) 0000 1100 1000 0110(2) % 1000 1000 0111 1111(g) = 0
(division result is 1111010 = 122,0 decimal)

Problem 128!!!! Software CRC!!!

Posted: Tue Mar 22, 2005 7:41 pm
by Andrey
I don't understand the explanation for this problem!!

Please help me!!

Sorry for my english!!
:oops: :oops: :oops:

CRC problem

Posted: Mon Oct 24, 2005 10:43 pm
by BlackDevil
Please can any body explain the CRC problem.................. and if there cases to test ot????????????

128-Software CRC WA

Posted: Fri Jan 20, 2006 5:36 pm
by ar2rd
I have no idea what's wrong with my code. Does anybody have some special cases or other inputs. Here is my code:

Code: Select all

// Software CRC - acm.uva.es/p/v1/128.cpp
// by Artur Dmowski
#include <cstdio>
#include <cstring>
#define G 34943
using namespace std;

char line[1500];
int crc,m,k,i;

int main() {
   #ifndef ONLINE_JUDGE 
     freopen("in.txt","r",stdin);
     freopen("out.txt","w",stdout);
   #endif
   
   while( gets(line) ) { 
    
    if( line[0] == '#' ) return 0;
    
    m = 0;
    k = strlen(line);
    
    for(i = 0; i < k; i++) 
         m = ((m<<8)+line[i])%G; 
    
    m = (m<<16)%G;
    crc = (m==0 ? 0 : G-m);
    
    printf("%02X %02X\n", crc>>8, crc -((crc>>8)<<8));
   }
}

Posted: Sat Mar 18, 2006 7:41 am
by MeteorRain
YEA, Also WA'ed. could anyone give some test case or give some advices? thanks in advance.

Code: Select all

// uva128 Software CRC
// MR

#include <stdio.h>
#include <string.h>

int main()
{
	char str[1040];
	int pos, curr, sl, out;
	while(1)
	{
		gets(str);
		if(str[0] == '#')
			break;
		pos = 1;
		curr = str[0];
		sl = strlen(str);
		while(pos < sl)
			curr = (curr << 8 + str[pos++]) % 34943;
		out = (34943 - (curr << 16) % 34943) % 34943;
		printf("%02X %02X\n", out >> 8, out % 256);
	}
	return 0;
}

Posted: Sat Mar 18, 2006 9:21 am
by Darko
Hm, for me that C code doesn't produce correct answer for the sample input.

Seems that strlen() counts the newline character. But even if I ignore the last character, it still doesn't output right answer for an empty string. After fixing that, it's still broken. (although it passes sample input at that point)

I don't know C, so I don't know why compiler complains about gets() and shift operations not being inside parenthesis (I put them inside, but that didn't work).

Darko

Posted: Sat Mar 18, 2006 10:51 am
by chunyi81
Darko: gets discards the newline character.

MeteorRain:
This code:

Code: Select all

      while(pos < sl) 
         curr = (curr << 8 + str[pos++]) % 34943; 
works differently from this code:

Code: Select all

      while(pos < sl) 
         curr = ((curr << 8) + str[pos++]) % 34943; 
in my gcc 3.3.2 compiler.

Changing to the second code will make your code work with the sample input.

Posted: Sat Mar 18, 2006 1:55 pm
by Darko
Darko: gets discards the newline character.
My bad - I copied the file from Windows - it had carriage returns at the end.

But it stil gave me a wrong answer for the empty string, even with shift in parenthesis. (gcc 3.4.3)

I couldn't see why it wouldn't work afterwards.. but it didn't.

Darko

Posted: Sun Mar 19, 2006 7:09 am
by chunyi81
The empty string still gives me correct output on my university's Unix server for MeteorRain's code, after putting the shift in parantheses.

This test case from a past thread will reveal the error in both WA programs in this thread:

Input:

Code: Select all

RFC: 793
#
ar2rd's program output:

Code: Select all

10A 21
MeteorRain's program output:

Code: Select all

81 A2
But correct output should be:

Code: Select all

0A 21