Forces in the crystalProblem code: HX |
All submissions for this problem are available.
The time limit for the large test cases for this problem has been upped to 15 seconds.
Suppose that we have a crystalline triangular grid of atoms. Atoms are arranged on a regular grid, and each atom has six neighbors (unless it lies on the boundary of crystal). Each atom has an electric charge of q, and can be polarized in only one of two directions: up or down (the laws of physics in Byteland are somewhat surprising!). If two atoms are neighbors and share the same polarization, then a destructive force against the crystal occurs, whose value is equal to q1*q2. We can choose the polarization for each atom, and we would like to minimize total force working against the crystal, i.e., the sum of values of all the individual forces.
Input
First, 1000 <= n <= 2000, the size of input. Then n lines with n numbers in each follow. In the x-th line, 1 <= x <= n, the y-th number, 1 <= y <= n, is the charge of the atom with coordinates in the crystal equal to (x,y) if x is odd, (x,y+1/2) otherwise. For any atom at coordinates (x,y), the coordinates of the neighbors are assumed to be the following (as long as they appear in the crystal): (x-1,y-1/2),(x-1,y+1/2),(x,y-1),(x,y+1),(x+1,y-1/2),(x+1,y+1/2). Each charge q is in the range 0.1 <= q <= 1.
Output
For each atom given at input, output 0 or 1 depending on whether the polarization of the atom should be directed up or down.
Score
The score of your program is equal to the value of the force acting on the crystal. The program is tested multiple times for different data sets, and the results are averaged.
Example
Input:
3
1 2 3
4 5 6
7 8 9
Output:
0 0 0
0 0 0
0 0 1
Score:
269 = (1*2+1*4+2*3+2*5+2*4+3*6+3*5+4*5+4*7+4*8+5*6+5*8+7*8)
| Date: | 2009-09-22 |
| Time limit: | 10s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK CAML CLPS PRLG WSPC BF ICK JS |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
"Each charge q is in the
"Each charge q is in the range 0.1 q 1"
does this mean the elements of the input matrix will lie between 0.1 and 1
but in the example they are >=1
plz explain
I think Soumya is correct --
The example is incorrect. The
The example is incorrect. The problem statement is fine.
A couple quick questions
A couple quick questions (sorry if these are answered elsewhere -- I spent some time browsing around the website but couldn't find the info):
1. Will submissions be rejudged with a different test set after the contest period ends or will the results on Oct 11 hold?
2. Which submission(s) count for the final score?
3. How many digits of precision are used in the input?
heyi did not underctand this
heyi did not underctand this question itself
@Ploh There won't be any
@Ploh There won't be any rejudge. Your best submission counts. You can't assume anything about the digits of precision used in the input :)
@kmn could you be more specific as to what you don't understand ?
@Po-Ru Loh ad. 3: few
@Po-Ru Loh
ad. 3: few digits
Thanks for the quick
Thanks for the quick response!
admins can u take a look at
admins can u take a look at my latest time limit exceeded submission for this problem?
Just a doubt, Is my program really running for ten seconds or is there a small mistake in the judge regarding that?
If it is running, Can you make it lot bigger? like 100 seconds or something so that it provides scope for better algorithms to be used?
There is no mistake in the
There is no mistake in the judge :) We can't increase the time limit in the middle of the contest.
Hello, I am new to
Hello, I am new to codechef.
What is score used is for?
Is this possible to find a polyniomial time solution to this problem
or
we are expected to find some solution such that lesser the score, better will be my solution?
Yes, the lesser the score,
Yes, the lesser the score, the higher the points you get.
My submission times out even
My submission times out even though I'm, only using scanf() and printf() for input and output (and 10^6 additions).
The time limit for the large
The time limit for the large test cases has been upped to 15 seconds.
hen n lines with n numbers in
hen n lines with n numbers in each follow. In the x-th line, 1 <= x <= n, the y-th number, 1 <= y <= n, is the charge of the atom with coordinates in the crystal equal to (x,y) if x is odd, (x,y+1/2) otherwise. This sounds unclear....could you just elaborate it!!
It was unclear to me also
It was unclear to me also until I actually graphed it, then it makes sense, but then, I'm almost entirely a visual person.
In the example, 1 is at coordinates 1,1, 2 is at 1,2 and 3 is at 1,3. Since x in this case is odd, you can plot them just as they appear. For line 2 (x = 2) since x is even you would plot points 2, 1.5 for 4, 2, 2.5 for 5, and 3, 3.5 for 6, basically adding .5 to each y coordinate just as the problem states.
Do this for the next line following the same rule depending on whether x is even or odd. Graph it and you should have no problems moving on.
Are all of the testcases
Are all of the testcases randomly generated with all q randomly and uniformly distributed between 0.1 and 1.0, or were some generated with a non-uniform distribution?
Hi Anirudha, I am printing
Hi Anirudha,
I am printing some garbage in my soln 105186, but judge is still saying right answer. Not getting the reason.
Why was the time limit
Why was the time limit changed so late in the contest? I really think that was a bad idea, as everyone would have submitted based on a 10 second time limit, as most programs on these sorts of problems have the time limit coded into the program. I now have to go back and resubmit all of my earlier submissions, which I can't even do because I can't view my submission via the 'My Submissions' page.
Can the time limit please be changed back?
Also, what constitutes a
Also, what constitutes a "large" test case? Is the time limit still 10 seconds below some cutoff value of N and 15 seconds above it?
I agree with Stephen
I agree with Stephen absolutely. I also consider it to be a very poor practice to change the rules in the middle of the contest.
Hello all, We received a lot
Hello all,
We received a lot of complaints regarding the fact that the time limit was too strict and solutions which accepted input using scanf() and printed values using printf() were getting TLEd. The time limit was changed to address this fact.
@Josh We can't give out specific information regarding either the distribution or the values of N.
@Saeeudding We will check this out. My first reaction is that the judge solution considers any non zero value to be 1.
@Stephen Sorry about that. The link will be put up soon on the MySubmissions page. However, the solutions are infact available to you via the all submissions page. In the mean while, you can download your solutions by changing the submission id. Rest assured, this will be the first issue on our to-do list.
@Jan Stola Sorry about not changing the time limit sooner. We try to keep the contest as error free as possible. Such issues however do crop up time and again. Having promised last time that we will try to keep the time limits as lenient as possible, it seemed wrong on our part to not do something about what was being reported to us.
We will try our best to see that such things do not happen in the future.
@Stephen This is now fixed.
@Stephen This is now fixed. You can see the link on the My Submissions page.
Well, I'm afraid this is
Well, I'm afraid this is still rather ridiculous, and very unfair on anyone who submitted before the time limit was changed - it has ruined this contest for me. I'm very disappointed that you aren't going to change it. The last three contests all had the same problem with time limits and this was made clear to you after the contest ended, so this really should have been fixed a long time before the contest started.
At the very least it is necesssary to answer what Josh asked about what a 'large' test case, otherwise you will just get a massive number of submissions by everyone trying to figure out which cases have a time limit of 15 seconds.
We made sure that the time
We made sure that the time limits for the other problems are as lenient as possible. The challenge problem managed to slip by as we did not think that Input / Output would be an issue for it. However, as there was still time, we thought it would be better to make amends when we could rather than continue with the low time limits. We are sorry if you feel that this contest is ruined, but would strongly encourage you to continue participating in the current contest as there is a lot of time left for it to end :) Sorry for the goof-up.
@admin: at what value of n
@admin: at what value of n test case will be considered to be large?
The current contest
The current contest scoreboard is rounding the scores for this problem so that even if one score is slightly more than another, they are being given equal places on the leaderboard. (For example, I'm currently tied with bcloud on 5.999 even though we have different scores for the challenge problem). Will the true results be based on the exact scores, and if so, can the leaderboard be fixed?
@admin: what is the exact
@admin:
what is the exact format of INPUT numbers.
if charge q is .5,
what will be the format - .5 or 0.5 ?
and what about for value 1 ?
@Surendra I do not think that
@Surendra
I do not think that that makes much of a difference. It is not hard to deal with it.
However, I do believe that every q has exactly one digit before decimal.
I do not have any sort of a
I do not have any sort of a confirmation, but that is how I expect it to be (with a probability of 99.999%.
@Keshav: Thanx for reply. But
@Keshav:
Thanx for reply.
But I don't think so. I am getting RunTimeError for a specific format.
@Admin:
Please, specify the input format
@Surendra You are ridicoulus,
@Surendra
You are ridicoulus, input is specified - it's floating point number!