Πρόβλημα με παλινδρομικούς αριθμούς

TSMGeorge · 14 Οκτωβρίου 2014

Περιγραφή:

Κώδικας:

    class Program
    {
        static void Main(string[] args)
        {
            // Read Input
            string input = Console.ReadLine();

            // Parse Input
            string[] split = input.Split(',');

            int PalindromesCount = 0;
            int a, b;
            // TryParse because we want only Integers-32bit
            if (int.TryParse(split[0], out a) &&
                int.TryParse(split[1], out )
            {
                if (b >= a) // Limit: b >= a
                {
                    if (a >= 0 && b >= 0)   // Limit: Positive numbers
                    {
                        for (int i = a; i <= b; i++)
                        {
                            if (i > 0) // Ignore 0, is not Palidromic
                            {
                                // XOR Reverse is the fastest way to reserv an string
                                string x = Convert.ToString(i, 2);
                                char[] charArray = x.ToCharArray();
                                int len = x.Length - 1;

                                // Do XOR
                                for (int k = 0; k < len; k++, len--)
                                {
                                    charArray[k] ^= charArray[len];
                                    charArray[len] ^= charArray[k];
                                    charArray[k] ^= charArray[len];
                                }

                                if (x.Equals(new string(charArray)))
                                    PalindromesCount++;
                            }
                        }
                    }//If

                }//If b>=a

            }//IfTryParse


            // Print Output
            Console.WriteLine(PalindromesCount);

        }//Main
    }

Ενώ καλύπτω όλα αυτά που ζητάει ( a <= b, a&b >= 0, must be Integer-32, Positive, time limit: 3s) , δεν μπορώ να περάσω με τίποτα το τελευταίο Τεστ, έχω κολλήσει στο 80% (4/5).

Ίσως η εκφώνηση δεν είναι τόσο ξεκάθαρη...

Μπορεί κάποιος να μου πει τι παίζει; που είναι το λάθος; δεν μπορώ να φανταστώ το Input για το Test #4 (5o) ώστε να το φτιάξω...

Αν κάποιος έχει εμπειρία από IEEEXtreme, μπορεί να μου πει πως να διαβάσω τα προβλήματα; δηλαδή λέξεις κλειδιά που δηλώνουν κάτι στον κώδικα.

Πχ: "Α & Β must be positive integers-32", αυτόματα βγάζεις τον κώδικα


if (int.TryParse(x, out a) && int.TryParse(y, out ) // Check if is Integer-32
{
   if (a >= 0 && b >= 0) // If is Positive
   {

   }
}

albNik · 14 Οκτωβρίου 2014

Παντως να ελεγχεις καθε αριθμο a<=x<=b δεν ειναι αποδοτικό

Ξεκινα κατασκεβαζοντας τα

1,

11,

101, 111,

1001, 1111,

10001, 10101, 11111 ...

παπι · 14 Οκτωβρίου 2014

Πρωτα φτιαξε συναρτηση η οποια ελεγχει εαν ενας int ειναι παλινδρομικος... viva la abstraction.

Δευτερον, δεν υπαρχει λογος να κανεις μετατροπη του binary σε string για να κανεις τους ελεγχους. Υπαρχουν οι bitwise operators

TSMGeorge · 14 Οκτωβρίου 2014

Πρωτα φτιαξε συναρτηση η οποια ελεγχει εαν ενας int ειναι παλινδρομικος... viva la abstraction.

Δευτερον, δεν υπαρχει λογος να κανεις μετατροπη του binary σε string για να κανεις τους ελεγχους. Υπαρχουν οι bitwise operators

... που δεν έχω ασχοληθεί ποτέ...

albNik · 14 Οκτωβρίου 2014

Επισης o int ειναι μεχρι 31 bits (2^31-1 )

Θες uint

TSMGeorge · 14 Οκτωβρίου 2014

Παντως να ελεγχεις καθε αριθμο a<=x<=b δεν ειναι αποδοτικό

Ξεκινα κατασκεβαζοντας τα

1,

11,

101, 111,

1001, 1111,

10001, 10101, 11111 ...

Υα οκ... το θέμα είναι, τι input έχει για το ***νο 5ο (#4) Τεστ και δεν περνάει...

Τεσταρα τα πάντα...

- Negative numbers, return 0

- More than 32bits return 0

- a > b return 0

- count 0 as palindromic

- ignore 0 as palindromic

- coun 0 and 1 as palindromic

- ignore 0 and 1 as palindromic (start from 2(10))

H C# μου βγάζει Runtime Error και η Java "NumberFormatException"... αν πάρω το Output της Java μάλλον περνάνε κάποιον αριθμό >32bit... αυτό όμως το πιάνω σαν ενδεχόμενο και επιστρέφω 0. Έχω σπάσει το κεφάλι μου! Σύμφωνα με την εκφώνηση έπρεπε να δουλεύει... δεν ξέρω!

Επισης o int ειναι μεχρι 31 bits (2^31-1 )

Θες uint

Το μόνο που μου έμεινε να δοκιμάσω είναι uint, παίζει να είναι και αυτό.

2^32-1 = (2^32) - 1 = 4.2κκκ

παπι · 14 Οκτωβρίου 2014

btw το να κανεις '0' xor '1' δεν θα εχει το αποτελεσμα που θα ηθελες. Πρεπει να τα μετατρεψεις και παλι σε int

albNik · 14 Οκτωβρίου 2014

Καπου 130000 αριθμοι ειναι για 0<x<2³²

Τους παραγω σε 0 seconds.

Συγκρινε αν ο καθενας ειναι μεταξύ a-b

	               List<string> strs = new List<string>();
			for(int i = 1; i <= 32; i++)
				strs.AddRange(Pal(i));
		
			List<uint> ints = new List<uint>();
			foreach(var item in strs)
				ints.Add(Convert.ToUInt32(item, 2));

			ints.Sort();




   static List<string> Pal(int n)
		{
			if(n < 1)
				return new List<string> { };
			if(n == 1)
				return new List<string> { "0", "1" };
			else if(n == 2)
				return new List<string> { "00", "11" };
			List<string> pals = new List<string>();
			string addL = "1";
			string addR = "1";
			int k = n - 2;
			while(k >= 1)
			{
				foreach(var item in Pal(k))
					pals.Add(addL + item + addR);
				addL += "0";
				addR = "0" + addR;
				k -= 2;
			}
			return pals;
		}

TSMGeorge · 14 Οκτωβρίου 2014

ΥΓ: Να ξεκαθαρίσω κάτι...

0 και 1 (δυαδικό) είναι παλινδρομικοί;;;

παπι · 14 Οκτωβρίου 2014

Καπου 130000 αριθμοι ειναι για 0<x<2³²

Τους παραγω σε 0 seconds.

Συγκρινε αν ο καθενας ειναι μεταξύ a-b

	               List<string> strs = new List<string>();
			for(int i = 1; i <= 32; i++)
				strs.AddRange(Pal(i));
		
			List<uint> ints = new List<uint>();
			foreach(var item in strs)
				ints.Add(Convert.ToUInt32(item, 2));

			ints.Sort();




   static List<string> Pal(int n)
		{
			if(n < 1)
				return new List<string> { };
			if(n == 1)
				return new List<string> { "0", "1" };
			else if(n == 2)
				return new List<string> { "00", "11" };
			List<string> pals = new List<string>();
			string addL = "1";
			string addR = "1";
			int k = n - 2;
			while(k >= 1)
			{
				foreach(var item in Pal(k))
					pals.Add(addL + item + addR);
				addL += "0";
				addR = "0" + addR;
				k -= 2;
			}
			return pals;
		}

Και θα κανεις lookup σε 130000 αριθμους;;;;

TSMGeorge · 14 Οκτωβρίου 2014

Παιδιά... λίγο OnTopic... το θέμα δεν είναι να βρούμε τον ταχύτερο κώδικα... (ήδη αυτός που έχω το Max που πιάνει είναι 1.92s / 3) οπότε δεν έχω θέμα με τον χρόνο. Δεν μπορώ να ασχολιέμαι με αυτό τώρα.

Απαντήστε μου λίγο pls (binary values),

0 is palindromic?

1 is palindromic?

albNik · 14 Οκτωβρίου 2014

Και θα κανεις lookup σε 130000 αριθμους;;;;

Αν ειναι ταξινομιμενοι βρισκεις σε O(log(130000)) ποσοι ειναι μεταξυ a b.

TSMGeorge · 14 Οκτωβρίου 2014

Άλλαξα σε uint (90% το τελευταίο τεστ έχει κάποιον πολύ μεγάλο αριθμό) και τώρα τρωω timeout.

Οπότε, Acording the below code, τι μπορώ να κάνω ώστε να το βελτιώσω σε ταχύτητα;

// Read Input
            string input = Console.ReadLine();

            // Parse Input
            string[] split = input.Split(',');

            uint PalindromesCount = 0;
            uint a, b;
            if (uint.TryParse(split[0], out a) &&
                uint.TryParse(split[1], out )
            {
                // Some optimization
                if (a % 2 == 0) a++;
                if (b % 2 == 0) b--;

                if (b >= a)
                {
                    if (a >= 0 && b >= 0)   // Positive numbers
                    {
                        for (uint i = a; i <= b; i+=2)
                        {
                            if (i > 1) // Ignore 0, is not Palidromic
                            {
                                // XOR Reverse is the fastest way to reserv an string
                                string x = Convert.ToString(i, 2);
                                char[] charArray = x.ToCharArray();
                                int len = x.Length - 1;

                                // Do XOR
                                for (int k = 0; k < len; k++, len--)
                                {
                                    charArray[k] ^= charArray[len];
                                    charArray[len] ^= charArray[k];
                                    charArray[k] ^= charArray[len];
                                }

                                if (x.Equals(new string(charArray)))
                                    PalindromesCount++;
                            }
                        }
                    }//If a & b > 0

                }//If b>=a

            }//IfTryParse


            // Print Output
            Console.WriteLine(PalindromesCount);

Υπενθυμίζω ότι το πρόβλημα δεν ζητάει να παράξουμε παλινδρομικούς αριθμούς από α εως β, ζητάει να βρούμε πόσοι είναι οι παλινδρομικοί αριθμοί από α εως β, οπότε :

for(uint i = a; i <= b; i++)
{
    // Get the ammount of palindromic numbers
}

PS: Τι έχω κάνει για να βελτιώσω την ταχύτητα:

- ΧΟR Reverse, which seems it is the fastest way (according forums)

- Check the half numbers in range [a;b], we know that only odd numbers can be palindromic.

παπι · 15 Οκτωβρίου 2014

Αν ειναι ταξινομιμενοι βρισκεις σε O(log(130000)) ποσοι ειναι μεταξυ a b.

Τι να σου πω.. εγω εφτιαξα μια παραδοσιακη συναρτηση με μια for μεσα, το εβαλα στον compiler και μου εβγαλε...

test:
00D91280  mov         edx,ecx  
00D91282  mov         ecx,1Fh  
00D91287  mov         eax,edx  
00D91289  sar         eax,cl  
00D9128B  test        eax,eax  
00D9128D  je          test+15h (0D91295h)  
00D9128F  xor         eax,edx  
00D91291  test        al,1  
00D91293  jne         test+1Bh (0D9129Bh)  
00D91295  dec         ecx  
00D91296  jne         test+7h (0D91287h)  
00D91298  mov         al,1  
00D9129A  ret  
00D9129B  xor         al,al  
00D9129D  ret

Btw ειναι μαρκαρισμενη με noinline...

defacer · 15 Οκτωβρίου 2014

Αυτό που έχεις τώρα (δεν το διάβασα προσεκτικά, μόνο τη γενική ιδέα) έχει δύο μεγάλα προβλήματα:

Είναι Ο(N) στην είσοδο, που είναι το λεγόμενο "αφελές" και για το συγκεκριμένο πρόβλημα το χειρότερο που μπορεί να γίνει. Οποιαδήποτε λύση με τέτοιο for δεν πρόκειται να περάσει το test.
Ακόμα και για τα δεδομένα αυτής της λύσης είναι πάναργο επειδή δουλεύει με strings, strings, strings...

Τώρα.

Καταρχήν είπες ότι δεν ξέρεις για δυαδικούς τελεστές. Οπότε; Τι περιμένεις να γίνει για να μάθεις; Δε φτάνει ότι προσπαθείς να λύσεις ένα πρόβλημα στο οποίο θα σε βοηθούσαν και σου λέμε πως θα σε βοηθούσαν σε περίπτωση που δεν το ξέρεις;

Εν συνεχεία, είδες τελικά που είχαμε πρόβλημα με το χρόνο; Με περισσότερη εμπειρία θα ήξερες ότι τα 3 sec που σου δίνουν είναι μια αιωνιότητα (μια καλή λύση του προβλήματος θα έτρεχε σε msec, όχι σε sec) και επομένως το 1.92 που λες αντί για ΟΚ είναι προάγγελος της συμφοράς που ακολουθεί. Όταν σου λένε κάτι τέτοιο θα μάθεις πολύ περισσότερα αν απαντάς "γιατί το λες αυτό" αντί για "στο θέμα παρακαλώ".

Σε γενικές γραμμές αυτό που θέλεις είναι να κάνεις τους υπολογισμούς όχι δοκιμάζοντας αριθμούς αλλά με τη λογική. Παράδειγμα: έστω ότι θέλεις να μάθεις πόσοι είναι οι αριθμοί που έχουν ακριβώς 7 ψηφία, δηλαδή α = 1000001 και β = 1111111.

Είναι φανερό ότι το πρώτο και το τελευταίο ψηφίο θα είναι πάντα 1, αλλιώς ο αριθμός ή δεν έχει 7 ψηφία (άτοπο) ή αρχίζει από 1 και τελειώνει σε 0 (άκυρο). Επομένως έχεις 5 ψηφία στη διάθεσή σου που μπορεί να αλλάξουν. Από αυτά, τα μισά (round down) δεν τα λαμβάνουμε υπόψη γιατί προφανώς είναι καθρέφτης των άλλων μισών. Άρα μένουν 5 - 2 = 3 ψηφία. Οι συνδυασμοί των 2 δυνατοτήτων (0 και 1) ανα 3 είναι 2 στην τρίτη δύναμη = 8.

Επομένως χωρίς κανένα for και χωρίς καμία δοκιμή μόλις βρήκαμε πως τα δυαδικά παλίνδρομα με 7 ψηφία είναι ακριβώς 8, ήτοι:

1000001

1001001

1010101

1011101

1100011

1101011

1110111

1111111

Δε χρειάστηκε ούτε να σκεφτώ για να τους γράψω, επειδή για τα ψηφία 2-3-4 (με bold) απλά μετράω στο δυαδικό από 000 ως 111 και τα υπόλοιπα προκύπτουν από τα δεδομένα της εκφώνησης. Αυτό το αναφέρω επειδή είναι πιθανόν βγάζοντας αυτή την ιδέα μόνος σου να δούλευες ανάποδα: πρώτα γράφεις τους αριθμούς και μετά αντιλαμβάνεσαι ότι απλά μέτρησες δυαδικά οπότε είναι φανερά 2 στην τάδε δύναμη που προκύπτει από τον αριθμό των ψηφίων.

Αυτό τώρα γενίκευσέ το με ένα for από x μέχρι y για να υπολογίζεις αθροιστικά το σύνολο των παλινδρόμων που έχουν ακριβώς από x μέχρι y ψηφία. Δεδομένου ότι το y πάει το πολύ μέχρι 31 το for θα τερματίσει σε microseconds οπότε ο,τι κι αν σου δώσουν σαν είσοδο είσαι παραπάνω από ΟΚ.

Και μετά γενίκευσέ το ξανά για να μη περιορίζεσαι να μετράς όλα ανεξαιρέτως τα παλίνδρομα με Χ ψηφία αλλά να μπορείς να ξεκινήσεις και "από τη μέση".

Για το τελικό χτύπημα, συνειδητοποίησε πως ούτε καν ένα τόσο μικρό for δεν είναι 100% απαραίτητο.

Σύνδεση

Πρόβλημα με παλινδρομικούς αριθμούς

Προτεινόμενες αναρτήσεις

TSMGeorge

albNik

παπι

TSMGeorge

albNik

TSMGeorge

παπι

albNik

TSMGeorge

παπι

TSMGeorge

albNik

TSMGeorge

παπι

defacer

Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε

Δημιουργία λογαριασμού

Σύνδεση

Σύνδεση