CHEFOFR - Editorial

binary-search
bitmasking
bitwise
editorial
medium
april19

#1

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Utkarsh Sinha
Tester: Zhong Ziqian
Editorialist: Oleksandr Kulkov

DIFFICULTY:
MEDIUM
PREREQUISITES:
DP, bitmasks
PROBLEM:
You’re given array A_1,\dots,A_N, you have to split it into K segments to maximize sweetness of this partition, which is defined as follows: Firstly each A_i will be multiplied by some number t_i. Then sweetness S_i of each segment is defined as sum of sweetnesses of all elements in it. Sweetness of the whole partition is defined as S_1 * S_2 * \dots * S_k where * is defined as follows:

x * y = \sum\limits_{n=0}^{\lfloor \log_2 x\rfloor} 2^n \left(\left \lfloor \frac{x}{2^n}\right\rfloor \bmod 2\right)\left(\left \lfloor\frac{y}{2^n}\right\rfloor \bmod 2\right)

You will have Q queries with given t_i for each query, constraints:

  • 1 \leq Q \leq 10
  • 1 \leq K, N \leq 10^5
  • 1 \leq A_i \leq 10^{15}
  • 0 \leq t_i \leq 10
  • At most 50 of t_i will not be equal to zero.

QUICK EXPLANATION:
Just a bit of bit magic and observations.
EXPLANATION:
You may immediately recognize that x*y is simply bitwise and of x and y. Then you should note that there is no reason to have any segment with sweetness 0, thus we may simply ignore all indexes i having t_i = 0 and assume that N \leq 50. Let’s deal with the following subproblem: Given number mask you have to check if there’s a partition such that mask is a submask of its sweetness. It may be done via simple DP in O(m^2 k):

bool check(vector<int> a, int mask, int k) {
	int m = a.size();
	int dp[m + 1][k + 1];
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	for(int i = 1; i <= m; i++) {
		int sum = 0;
		for(int j = i; j > 0; j--) {
			sum += a[j - 1];
			if((sum & mask) == mask) {
				for(int t = 1; t <= k; t++) {
					dp[i][t] |= dp[j - 1][t - 1];
				}
			}
		}
	}
	return dp[m][k];
}

With this function we may greedily check bits in answer and set them to 1 whenever possible. Assume that ta is the array of non-zero t_i A_i, then solution looks like this:

if(k > ta.size()) {
	cout << 0 << "\n";
} else {
	int l = 0, r = 1LL << 55;
	while(r - l > 1) {
		int m = (l + r) / 2;
		if(check(ta, m, k)) {
			l = m;
		} else {
			r = m;
		}
	}
	cout << l << endl;
}

Note that though we used binary search here, function is not monotonic in common sense but it’s monotonic in terms of logic functions, that is if u is submask of v then f(u) \leq f(v). Turns out it’s also enough to utilize simple binary search in particular case of l=0 and r=2^k and it will find lexicographically largest mask on which check is equal to 1.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.


#2

You call this an editorial! What is this? Even Stack Overflow has provided wonderful answers. This question was really amazing but this editorial spoils it all.
Many people wouldn’t know why this question is reduced to finding bitwise \& of x_1, x_2,... This editorial could be explained really well and would have benefited the people who couldn’t solve it (including me) a lot.

I’m sure you could edit this and make it more detailed and self-explanatory and prevent spam posts on 'Why is it the bitwise \&? Why is the solution correct? etc.

Hoping for a positive response from your side! :slightly_smiling_face:

Also, @admin why is it that my response is 8 days after the editorial was posted? Was the editorial uploaded and hidden 8 days ago? Is it truly hidden? If yes, why does the editorial take time to get posted after the end of a contest?
Scroll below for a bigger view of this situation!


#3

What would u say to this : Problem


#4

S**t!
The question already existed! @admin This is unfair! Many people would have known about this question. I feel I have been rated on an unfair scale. I thought Codechef Long problems were original! The constraints were also the same.
I wondered why the number of submissions for KLPM and this question were nearly the same!
@vijju123 Please comment about this!
Great work finding it @aman_robotics.
@utkarsh97 Did you or did you not know about this?

  • I feel this is unfair
  • I don’t feel that way. Whats wrong if they used this question from an already existing question?

0 voters


#5

Was that supposed to be an editorial?


#6

this question wasnt there in div2 , how come it is linked to div2 and that link is also working ?


#7

Non-Scorable Section


#8

“Also, @admin why is it that my response is 8 days after the editorial was posted? Was the editorial uploaded and hidden 8 days ago”

I tend not to answer any part of it publicly.

“Is it truly hidden?”

Yes.

“If yes, why does the editorial get posted after a few hours after the end of a contest?”

Same as 1.


#9

I used a different approach . I found out all the ways in which the array can be partitioned (K segments) , i simply used some properties of AND ( such that AND of two numbers is always equal or less than the number ) . I was surprised to see my code getting AC .
Is my approach efficient or i got lucky due to weak test cases.
(The test cases passed well within the limit)
link : https://www.codechef.com/viewsolution/23795566


#10

Test cases are not weak. This approach is efficient enough. See here NICARRAY - EDITORIAL


#11

It’s also unfair to make it unrated now.
If you want an unrated contest mail codechef. They will make it unrated just for you.

@aman_robotics If you knew about this question you should have contacted CC regarding it. They would have removed it.


#12

Add one more option for me - “Its unfair. But making it unrated now is also unfair.”


#13

@aryanc403 , I just started this long challenge 2 days back, and it was too late to be reported … I don’t think so its a good idea to make the make the contest unrated.


#14

Unfair - Meaning

I stated that the inclusion of that question was unfair, not the rating process. I never asked for the contest to be declared unrated. I know there are many people who might have solved this question(through the solutions on the net) though they didn’t solve KLPM. So they had a very unfair advantage over others.

I had an advantage too when I noticed the question on StackOverflow. However, keeping to Codechef Moral Code of Conduct, I restrained myself from looking at the solution.
Even though some might reason out stating that the question was posted with an intention of learning, I know for sure that all that person wanted was Rank and Ratings.

\begin{align} \fbox{ I didn't have this reported as the dividing line seemed so thin.} \end{align}

The problem of questions posted on StackOverflow was already mentioned in some post during this Long Challenge.

To make everything short, I want to know if it is possible to calculate ratings again, determining results after excluding the score of CHEFOFR.
This case can be considered, since multiple people are complaining about rating calculation of ALKH2019.

@vijju123 Have a look into this please! Also, could you find the person who posted the question on SO by using the Brute Force sol he posted(comparing codes or MOSS or something)?
@aryanc403 Give me further explanation if you still feel I am missing something.


#15

I haven’t seen the results of the poll.

You create a poll and if “I don’t feel that way. …” wins won’t make it fair.
What CC does when they find that setter has deliberately copied a question from another source -
Ask setter for an explanation. Sometimes ban setter also.
Apologise in community.
If they find it during the contest. They remove it from the contest.

H.W. for you -

  1. Search for the meaning of “It seems a notorious coincidence to me.” meme.
  2. Look at @vijju123 and @narendramodi profile on StackOverflow.

“I thought Codechef Long problems were original!” - No comments.

This is unfair. Declaring it fair if it wins in poll won’t make it fair.
Only contests where reusing older problems are allowed are educational rounds.

Lets for a minute assume that @admin admits it is unfair. Now, what do you want admin should do?? That’s the questions. Whose answer I assumed that you will ask for an unrated contest.

I want to know if it is possible to calculate ratings again, determining results after excluding the score of CHEFOFR. - That’s what I’m saying is also unfair.

This case can be considered, since multiple people are complaining about rating calculation of ALKH2019
Let me copy paste again for you -


#16

How could you assume such a thing? My statements never gave a glint of me wanting it to become unrated. Just because I haven’t spoken about the decision CC should take, doesn’t mean you could assume anything on my part. At the least, you could have started out stating “assuming you want it to become unrated…”.
This comment of your’s brings my reasoning and judgement at a wrong level of understanding and if you agree that’s the case, please edit your post accordingly.


I’m very bad at understanding meme’s and have failed even now. Plus, I don’t want any statement explaining the meme to me. :stuck_out_tongue:


  • No one’s determining National (or Codechef) leaders by voting in this poll.
  • Huge approval of online petitions don’t mean a law favouring it will get passed.

Instead, it’s only a way of showing our concern and voicing our views on the concerned matter. CC admins might not feel the way the polls go, and we have no say in that.
But, CC values(hopefully) community opinions and may take their decisions based on these poll results.


Notice the term ‘I want to know’, which gives a completely different meaning from the term ‘I want’. You are confusing my query with a demand + you don’t tell WHY it is unfair. What makes it unfair? That some people genuinely coded and solved it?

I recall a COOK OFF(if I’m not wrong) where the problems where not visible to everyone. Why was it then declared unrated? Some people who saw the questions must have coded it with enthusiasm and dedication only to see that the contest became unrated. They have the right to call it unfair. CC declared it unrated to even the scale of some participants who would lose their ratings due to this. Similar case can be applied here. I might have got a higher rating if this problem didn’t persist.

Backing Note: Never once have I seen number of Successful Submissions so close to each other for different questions.


If I’m right, your statement refers to my statement about determining who posted that question. You are right in a sense that it would not be possible to determine exactly who posted the question. But if that person posted the question on the net giving a code which fails the Time-Constraints, I’m sure he must have tried submitting the code (or something similar). Else he wouldn’t have uploaded the question for a better approach.


I realise different people have different opinions on this matter, but instead of resorting to a verbal Dog-Fight, lets ensure that we handle it peacefully.

(I’m not wanting to start an argument with you, so please don’t take my explanations in the wrong sense):smile:


#17

I also don’t want to keep on arguing. So I will leave it with https://codeforces.com/blog/entry/52348?#comment-364302


#19

It was the easiest problem if you prune the tree.

If you get some value of “&” till some point in recursion, you can prune it if it is less than or equal to global answer (It can in no way result more than that). Also, if remaining partitions are less than available numbers, you can again prune it.

You can find my solution using basic recursion.


#20

Should I complain about weak test cases here??
My soln of this question passes in 0.07 sec.
But It gives tle on the original problem.


#21

Hi,

I am yet to catch up on discussion of @aryanc403 and @infinitepro but in general I am against any kind of rejudge and rating recalculation now. Some people put genuine effort in the question and by no means are I feel we should discredit that. If that means some people get extra credit its fine as it will even out as they participate in future contests.