ZCO 2016 discussion

So I’m not going to make it. My solutions worked perfectly for every test case I could think of but didn’t work for the subtasks. I could only get the first subtask of bamboo accepted.

How did you guys do and what were your algorithms for the questions?

I did terrible.

I almost thought I solved Problem 2, although I didn’t

I got 130
The second one goes something like this
Maintain an array dp where dp[i][j] stores the maximum length upto i with a successive difference j
Now, for all j from 0 to i-1, dp[i][a[i]-a[j]] = dp[j][a[i]-a[j]] + 1

I felt the problems were much tougher than previous years though

2 Likes

I coded the same thing but I thought it would time out and didn’t submit it, damn :frowning:

For some reason, I thought the worst case complexity would be 10^5*2500, but now I realize it will be not be so much, because the nos are distinct.

Yeah exactly. I was fixated on that line of the problem statement for a long time before I figured out its purpose. Did you solve the first one?

No I didn’t. What was your algo?

bad…

i worked on bookshelves for 2 hrs and wrote the solution but i couldn’t imagine for which data it would get wrong output. Scoring a big 0…

  1. sort both arrays
  2. lots of cases (compare a1[n-1] with a2[n-1], a1[n-1] with a2[0], a1[n-2] with a2[0] and accordingly determine swap (not going to sit writing result for each case, hope you understand.
  3. calculate minimum value of skew at each step.
  4. break if any one array has all bigger values of skew, i.e. new skew after this swap will not result less than equal to current skew.

something like this…

as for the second problem,
Didn’t attempt bamboo one.

also the system was terrible. dev-cpp used to disappear on minimizing and had to switch the computer twice. :-/

Sort the two arrays and traverse the one with the smaller max value from the end. For each element from the last, eliminate that and its lower_bound in the second array and repeat this till either each element is covered or till k is reached

this explanation is a very crude one as I had coded a lot more conditions. it was perhaps one of those unnecessary conditions that gave me a runtime error in the second subtask

How about this test case?

6 1

1 13 13 13 13 13

1 1 1 1 1 14

Answer should be 15

That’s back to the drawing board I guess. Never really thought hard about my solution. How did I manage a 30 though xD were the test cases weak. Or I would’ve probably coded that possibility into one of my constraints. Man I’m dying to see my code again. Anyway, even if it fails the additional test cases, I’m happy with a 100

Haha yeah, you’ve done the 2nd problem anyway, so you’re good to go :slight_smile:

Hopefully. I missed last year’s INOI by a test case which was used for the final evaluation, so I hope my code doesn’t have any loopholes :stuck_out_tongue:

Is there a separate cut-off for class 10 and below in ZCO too? If yes, what was last year’s cut-off?

Giving Zco 2016 in Delhi was a very bad experience. Some of the computers even had windows 98 ( not all). Many candidates only got 90-100 minutes. There were a few guys who almost called the ico coordinator. The technical staff didn’t even knew the difference between compile and run atleast this never happened in IITD. Though I am Zio candidate but I feel bad for the potential candidates of ioitc who suffered because of this.
And I think Zio should be removed as it does not test a person’s coding ability, instead seats through zco should increase.

4 Likes

:’( Bad for me…It was really unexpected…only successfully submitted Subtask 1 of each problem. Means, total of 70 which confirms that I will not be selected. Actually not sure about it. If my codes fail in system test case, it will give me a ‘0’ marks. :3 …Well, may be the cut-off will be 100. I really don’t know why my codes gave wrong answer in subtask 2.

I scored 0.
My algorithms were
For Bookshelves
sort two arrays
swap(A1[n-1],A2[0])
store skew
in other copy of arrays
swap(A2[n-1],A1[0])
This didn’t worked so i tested for all swaps even that didn’t work and gave WA:-(
For Bamboo Sticks
I used dp a 2d array
B[i][j]=A[j]-A[i]
then store it in 1d array
then look for repeated digits whatever times repetition occurs thats answer
but my code didn’t work.

Experience:
Page developed by tcs was extremly bad, User foe page. I was not even told how to switch between c and c++.
No Demo Page provided!!
Continues crashing of dev c++
changed my pc 4 times!!
Above all resources for preparation are not provided.

1 Like

@aalok_sathe and @alphastar: Say a= {1, 2, 3, 7, 8}, b= {1, 5, 6, 7, 8} and k=2. Swapping a[n-1] and b[0] gives the same skewness as swapping b[n-1] and a[0]. Which one do you choose? If you swap a[n-1] with b[0] you can get an arrangement with skewness 12 after the next swap. If you swap b[n-1] with a[0] the minimum skewness you can get after another swap is 14. How do you break the ties efficiently?

Here’s what I did for Bookshelves (got AC in contest; expecting 200 overall): Note that the largest book must contribute to the skewness. Our objective is to minimize the other book which contributes. To do this, we must bring the larger books to one of the arrays so that the maximum book of the other array is as small as possible. Let’s try the first case: we try to bring the large books to array a. Suppose there are p instances of the largest book in the second array. We need to bring these p instances to the first array. If we have enough amount of swaps and space available, we do this and do the same thing with the second largest book and so on. (Note that you must also take care that the total number of elements in the first array cannot exceed n.) Then do the same thing for the second array and print whichever solution is optimal. This can be implemented nicely with maps in O(n log n).

1 Like

i was able to get the bamboo stick one’s first subtask with brute force. it ran in o(n^3).

//