Question about problem F in ACM ICPC 2017.

Revision en7, by Hossam, 2017-09-15 19:01:38

My question is, can we solve this problem using algorithms like k-means or something? After all, all we're trying to do is minimize the error for each pixel with respect to the nearest cluster/value out of the K values, right? this idea hit me first before the straightforward dynamic programming solution which passes nicely here link, but when I tried this solution link I got WA on test #9 and I have no idea if the error is from my implementation or that the algorithm doesn't even fit here, in which case I'd very much like to know explicitly why?

Thanks in advance.

Tags acm icpc 2017, problem f, posterize, k-means algorithm, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English Hossam 2017-12-02 23:03:01 0 (published)
en8 English Hossam 2017-12-02 23:02:17 23 Tiny change: 'ut of the **K** values`, ' -> 'ut of the K values`, ' (saved to drafts)
en7 English Hossam 2017-09-15 19:01:38 70
en6 English Hossam 2017-06-24 14:11:03 41 Tiny change: '### Question about Problem F: Posterize\nMy questio' -> 'My questio'
en5 English Hossam 2017-06-04 15:55:45 6 Tiny change: 'ssions/1883959) I got WA' -> 'ssions/1882552) I got WA'
en4 English Hossam 2017-06-04 13:36:56 0 (published)
en3 English Hossam 2017-06-04 13:35:31 0 (saved to drafts)
en2 English Hossam 2017-06-04 13:31:28 0 (published)
en1 English Hossam 2017-06-04 13:29:01 801 Initial revision (saved to drafts)