foxtrot9's blog

By foxtrot9, history, 4 weeks ago, In English,

Problem statement link: https://codeforces.com/contest/1198/problem/A

According problem statement and example in the problem statement, output of test case

10 1

589934963 440265648 161048053 196789927 951616256 63404428 660569162 779938975 237139603 31052281

should be 10 — 4 = 6.

Explanation for answer:

(Sorted array for ref: 31052281 63404428 161048053 196789927 237139603 440265648 589934963 660569162 779938975 951616256)

Suppose l = 31052281 and r = 196789927, then I can store the file as following:

31052281 63404428 161048053 196789927 196789927 196789927 196789927 196789927 196789927 196789927

In this case, K = 4 (& k = 2) and I have changed 6 numbers which are > r. So, answer should be 6.

However, judge says answer is 9. Submission link: https://codeforces.com/contest/1198/submission/59000769

Can someone help me in understanding what I am doing wrong?

1198A - MP3

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by foxtrot9 (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think your misunderstanding is that you think $$$n$$$ should change as the number of distinct elements in the array changes, but $$$n$$$ is constant no matter what you do to the array. In the test case above, $$$n$$$ will always be $$$10$$$, meaning that the only valid $$$k$$$ is $$$0$$$ (where $$$K = 1$$$ and therefore all elements in the array are equal, so you need to change $$$n - 1 = 9$$$ elements). This seems to correspond with your proposed answer, as there are $$$4$$$ distinct elements in the array and $$$k = 2$$$, so it fits in the $$$8$$$ bit disk.