×

SEAND2 - Editorial

Author: Sergey Nagin
Editorialist: Lalit Kundu

CHALLENGE

PROBLEM:

Sereja has an integer number A that doesn't contain zeroes in its decimal form.
Also he has N integers B[1], B[2], ..., B[N].
Let us first define function f for a number A as follows.

Now he has to reorder the digits of A such that f(A) is minimum.
A has upto 1000 digits. N=100 and B[i] is upto 10^6.

EXPLANATION:

I haven't found solution that is better than random, because of modulo function, so the best solution would be one, that can try as many A as possible.
So we need to optimize finding F(A). We can swap two digits of |A| and calculate F(newA) in O(N) time (because we can represent A mod B as (a0*100 + a1*101 + a2*102 ...) mod B = (a0*100 mod B + a1*101 mod B + a2*102 mod B ...) mod B).

So we can just find some random A and then try to swap some random not equal digits and check if it is better. Then we work with new A.

Also we can try next algorithm: fix some random A and swap some digits while we can make F(A) < F(newA). Then fix some new A and do it as many times as possible.

Other greedy techniques can also be used. Also techiniques like simulated annealing and evolutionary algorithms can be used.

Here's an interesting and useful blog post on this: http://gauravsen.blog.com/2015/01/14/hello-world/

SOLUTIONS:

This question is marked "community wiki".

3.0k93162187
accept rate: 12%

 2 I write this answer in reply to @argos's question about @rns4's approach. I looked at many of @rns4's submissions and my best guess is that he was able to generate the full data offline and optimize his solution parameters this way (e.g. try a lot of rand seeds for his solution, which would easily explain the big score difference). For the digits part it's more or less easy. He extracted the length of the 1st number in a file and the first few digits (I think about 9). Then you can brute-force offline the seed of the random number generator which generates this data (I think he rightfully assumed the author used the popular MersenneTwister). You can see this submission of his, where he checks if the first 10 digits strings in one of the test files are equal to 10 digits strings he has stored in the file (my guess is that this was to verify that he got the test data generating part right): http://www.codechef.com/viewsolution/5843470 I'm not sure how he got right the generation of the B parameters, since there was a manual parameter R used in test data generation (unless R was also randomly chosen). Anyway, I think there was a lot of work in guessing the exact test data generation algorithm (given that these R parameters were involved), but it seems that it paid off. answered 20 Jan '15, 13:25 10.0k●26●69●90 accept rate: 18%
 1 Do anybody know what was idea of rns4 solution that gave him(them) so high quality, comparing to other contestants? answered 20 Jan '15, 11:34 7★argos 71●3 accept rate: 0%
 1 @gkcs: How did you determine you could only make 45 swaps using your initial algorithm? And how did storing the sum of the rows increase it to 50,000 swaps? answered 20 Jan '15, 16:26 4★ashes45 36●2 accept rate: 50% I used the initial algorithm in some of the submissions. In fact 46 was the limit, 47 was TLE. Then i realized that only the rowsums were changing. And that saved around 1000 computations, per remainder. Simply put, the complexity went from O(N*X) to O(X). I also saw that the number of computations went even higher than a factor of 1000...but i think that is because i optimised my code. (20 Jan '15, 17:42) gkcs4★ Really cool! :D Thanks! (20 Jan '15, 18:33) ashes454★
 0 Main idea of my solution is to reject swap of two digits faster than O(N) if its partial score on top biggest mods is worse than their sum/2. And one more idea is try only permutations with different last 6 digits. All permutations of last 6 digits could be checked in 6! log 6! time by precalculating arithmetic progressions of r[i]+k*m[i] (small m[i] should be normalized). I did't know about multithreading. In my opinion it will be better to forbid it due to more random in running time. And at least it will be better to announce about it =) answered 19 Jan '15, 22:22 7★argos 71●3 accept rate: 0% 7★xellos0 5.9k●5●41●91 Really good ideas there. I had also thought of extremely localized(last k digit) search, but discarding a swap halfway though is smart. I think banning threads is also the only practical way forward. Unfortunately, how do you do so? :-P (20 Jan '15, 00:04) gkcs4★
 0 And what about you, @mugurelionut, how did you generate so many good seeds(about 500), using only 500 submits? answered 20 Jan '15, 22:01 7★argos 71●3 accept rate: 0% @argos: Good question. First of all, my rand seeds were not as good as those of @rns4 (my guess is because I couldn't test as many - I used actual submits compared to trying the seeds offline). But the answer is easy: With each submit I checked rand seeds for up to 15 different test cases. I used about 300 of the 500 submits for tuning rand seeds => I was able to test 8-9 rand seeds for each of the 500 test cases (300*15/500 = 9). (20 Jan '15, 22:20) Still didn't get =) How did you test 15 different test cases by one submit? And one more question - seems that it could take plenty of time (at least 30sec*300=2.5 hour) for mechanical work, how did you handle it? (20 Jan '15, 22:30) argos7★ Oh, I have idea how you did it, may be you marked results by running time =) But the second question still remains =) (21 Jan '15, 02:25) argos7★
 0 What is wrong with the codes? Cannot see the setter's or tester's solution. Please fix it. answered 15 Feb '15, 15:25 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,010
×717
×204
×18

question asked: 19 Jan '15, 01:48

question was seen: 3,331 times

last updated: 15 Feb '15, 15:25