Example of Ad Hoc problem in DSA questions : Many approaches, some better than others ;
The Prologue
I was trying to get back into learning more about Data Structures and Algorithms, a topic that I thoroughly enjoyed in the past - both the ups and the downs. So I started working on a question that I left at almost completed status 2 months ago. The code that I wrote then was ugly and somewhat lengthy ( unnecessarily ), so I started having a dig at it again with a fresher mind. So I started reading the question and doing it all over from scratch again.
Objective of this blog post:-
Understanding a class of problems called Ad Hoc problems
Through the example of a suitable question
Intuition behind the solution
2 approaches to the same problem,one better than the other
Ad Hoc problems
Ad hoc problems in Algorithms refer to those problems that lack a standardized or well-defined solution methodology. These problems often require creative and improvised approaches, leveraging many algorithmic techniques and heuristics tailored to that specific problem instance rather than relying on established algorithms or theories.
The Question
Codeforces has a lot of these ad hoc problem for beginners rated around 800 - 1100. We'll be looking at this particular one :-
Codeforces problem 1890A Doremy's Paint Part - 3
Constrains
Expected Output
Sample Test cases and Output
( You can copy paste the values and check if you're getting the correct answers )
5
2
8 9
3
1 1 2
4
1 1 4 5
5
2 3 3 3 3
4
100000 100000 100000 100000
Yes
Yes
No
No
Yes
Understanding the Question
As straightforward as that.
Naive Idea :- Brute Force
Algorithm :-
Construct all possible arrangements of array
See if the adjacent elements sums to the same value
Theoretically to construct all possible arrangements, it'll be O( n! ) !!!!;
But you could argue that we'd be able to detect if there is a sum mismatch within few iterations and the ammortised cost might degenerate to some reasonable polynomial time, and I'd say " It's still really bad, i think." or "Can you prove it ?"
Logic - I
( I came up with it when I was burnt out ; So the logic isn't the best is pretty bad, but we'll make it better; TRUST ME ON THAT or abandon ship and come up with new approach later )
I'll explain why this always works and the key intuition for arriving at it, in the next section. The purpose of the below algorithm is only to show that many working and valid solution to ad hoc problems are sub optimal, and how we can come up with something better.
Algorithm :-
Check if n = length( array_given) is even or odd
If n is even
count the number of times you see first element
count the number of times you see another distinct element
if at all you see an element different from the previously seen distinct elements, then the array is not good
if counters follows the following pattern it is good
either of the counts == n ( all n elements are same ) => Array can be permuted to be good
Both of the counts are equally n/2 => array can be permuted to be good
If the counters does not follow them, then they can't be made good.
if n is odd
count the number of times you see first element
count the number of times you see another distinct element
if at all you see an element different from the previously seen distinct elements, then the array is not good
if counters follows the following pattern it is good
either of the counts == n ( all n elements are same ) => Array can be permuted to be good
One count is (n+1)/2 - 1 and other count is (n+1)/2 => array can be permuted to be good
If the counters does not follow them, then they can't be made good.
Now that I gave a cringe attack to all reading, allow me to go even further and show the ugly code I worked on for a good one hour. I'll explain later why this code is so bad.
Example Implementation for Logic - I
int a[100];
void old_solution(){
int t,n,x,y; cin >> t;
// x is the first element
// y is the first element that is different from x
while(t--){
cin >> n;
int cnt1 = 0, cnt2 = 0;
// if n == even
if(n%2==0){
for(int i=0;i<n;i++) cin >> a[i] ;
int flag = 0, fn = 0;
// cnt1 count of first elem
x=a[0]; cnt1++;
for( int i=1; i<n; i++){
if(a[i]==x)cnt1++;
else{
if(!flag){ y=a[i];cnt2++;flag=1;} // first time seeing this
else{
if(a[i] == y)cnt2++;
// see an element different from x and y
else { fn = 1;break; }
}}
}
cout << cnt1 << cnt2 << "\n" ;
if(fn){cout << "NO\n" ;}
else{
if(cnt1 == n || (cnt1 == n/2 && cnt2 == n/2) )cout << "YES\n" ;
else cout << "NO\n";
}
}else{
for(int i=0;i<n;i++) cin >> a[i] ;
int flag = 0, fn = 0;
// cnt1 count of first elem
x = a[0]; cnt1++;
for( int i=1; i<n; i++){
if(a[i]==x)cnt1++;
else{
if(!flag){y=a[i];cnt2++;flag=1;} // first time seeing this
else{
if(a[i] == y)cnt2++;
// see an element different from x and y
else { fn = 1;break; }
}}
}
if(fn)cout << "NO\n" ;
else{
if(cnt1 == n || (cnt1 == (n+1)/2 && cnt2 == (n+1)/2 + 1) || (cnt1 == (n+1)/2 + 1 && cnt2 == (n+1)/2) )cout << "YES\n" ;
else cout << "NO\n";
}
}
}
}
Logic - II
Now that I was out of DSA for a month and started approaching this with a fresh mind, I hopefully did better. It took 30 minutes to implement, with the annoying errors and edge cases that I forgot to take care about.
Key Intuition
If we look at any good array :-
$$b_0+b_1=b_1+b_2\Rightarrow b_0=b_2$$
$$\\b_1+b_2=b_2+b_3\Rightarrow b_1=b_3$$
But we also know,
$$\\b_2+b_3=b_3+b_4\Rightarrow b_2=b_4$$
$$\\b_3+b_4=b_4+b_5\Rightarrow b_3=b_5$$
So combining the 2, we get :-
$$b_0 = b_2 = b_4 \cdot\cdot\cdot = b_{2k}$$
$$b_1 = b_3 = b_5 = \cdot\cdot\cdot = b_{2k + 1}$$
By Principle of Induction it can be induced from the first system it's self that there can only be at most 2 distinct elements in the array. The mathematical proof isn't much but I leave that to the CS grads 🙂;
So to visualize :-
So the Principle of Induction visualized would something like :-
same elements are in same colour.
So this gives us the most important intuition for this question :-
There can only be 2 DISTINCT elements AT MOST in the array. Only then can we make an arrangement where all the adjacent elements sums to the same value.
Algorithm
Check if the number of distinct characters are less than or equal to 2.
( If the number of distinct characters are greater than 2 => NOT POSSIBLE ; )
( If the entire array was of same elements => IT'S POSSIBLE ; )
Check if the difference between count[ 1st element ] - count[ different element ] is at most 1. ( if it is => POSSIBLE ; If it's not => NOT POSSIBLE ; )
THAT'S IT !!
Example Implementation for Logic - II
int arr[100];
void simple_solution(){
// 1. check if distinct elements are 1 or 2
// 2. check if c1-c2 is 0 or 1
// ONLY THEN can the array be made good
int t,n;
cin >> t;
while(t--){
int seen1,seen2,started=0; int c1=0,c2=0; int no_flag=0;
cin >> n;
for(int i=0;i<n;i++){
cin >> arr[i];
if( started ){
if( started==1 && arr[i] != seen1 ) { seen2=arr[i]; started++; }
else{
// no flag triggered only when we see an element
// different from seen1 and seen2
if( arr[i] != seen1 && arr[i] != seen2 ) { no_flag = 1; /* break; */ }
if(arr[i]==seen1)c1++; else c2++ ;
}
}
else{ seen1 = arr[i] ;started++ ; }
}
if( no_flag ){ cout << "NO\n"; continue; }
if( started == 1 ){ cout<<"YES\n"; continue; }
if(abs(c1-c2)<=1){ cout<<"YES\n"; }
else { cout << "NO\n";}
}
}
Why was Logic - I worse ?
Biggest reason
There was no need to have 2 different cases, since the central idea anyway independent of weather the size of array is even or odd .
I got the key intuitions of at most only 2 distinct elements for logic - I, but the framing the logic was unnecessarily tedious.
Code was still needlessly long
ODD CASE
If counters follows the following pattern, it is good
case where all elements are same
One count is (n+1)/2 - 1 and other count is (n+1)/2 => array can be permuted to be good
=> difference in counts = 1
EVEN CASE
if counters follows the following pattern, it is good
case where all elements are same
Both of the counts are equally n/2 => array can be permuted to be good
=> difference in counts = 0
These two rules could have been tested for their DIFFERENCES which would avoid lines like :-
if(cnt1 == n || (cnt1 == (n+1)/2 && cnt2 == (n+1)/2 + 1) || (cnt1 == (n+1)/2 + 1 && cnt2 == (n+1)/2) )cout << "YES\n" ;
Better code :-
if(cnt1 == n || abs(cnt1-cnt2) <= 1 ) cout << "YES\n" ;
In my defence though, normally I don't make THIS dumb mistakes, I make DUMBER , but during that time I was trying to develop the skill of splitting a problem into smaller sub problems and then learning to use dynamic programming to recursively tackle all the sub problems. And I didn't really think enough to see a better way. Once I got the intuition of there being only at most 2 elements in the array, I was in auto pilot mode, which explains those absurdly long lines.
Important Learnings from both Mistakes and Successes
We didn't have to ARRANGE the array to know IF it was possible.
Don't forget to reset the value of counters and flags for each test case.
Even if you know the answer before codeforces finished giving you the inputs, IT WILL STILL SHOVE IT DOWN YOUR THROAT.
If you look carefully :-
else{ // no flag triggered only when we see an element // different from seen1 and seen2 if( arr[i] != seen1 && arr[i] != seen2 ) { no_flag = 1; /* break; */ } if(arr[i]==seen1)c1++; else c2++ ; }The
breakis commented out. We know as soon as we see a third distinct element in the array we can say the answer is NO. But at least in codeforces, it will still feed you inputs and therefore you need to take those inputs anyway. That is why I am using flag variable to detect if ever a third distinct element was seen =>no_flagand still accepting the elements after I toggle theno_flag
Don't be shy to use vectors for counting 2 elements. The code gets simpler.
If you're burnt out, touch grass for a while. BREATHE. Live. Otherwise you'll solve problems but you won't get better.
Even if you get the LOGIC quickly after reading the question, don't get in your head, you can still RUIN the implementation.
Closing statements
Many of the lower rated problems in Codeforces often are ad hoc problems. Many of them are exercises for developing an ability to develop LOGIC into IMPLEMENTATION in CODE .
- https://www.tle-eliminators.com/cp-sheet <--- Very good list of codeforces problems to start out in developing coding skills to implement LOGIC
Finally :-
Inspirations from a Japanese coder I admire - Kotatsugame ; He is really good with these " converting logic into BETTER code " apart from being a god tier coder with humble beginnings; On inspecting his way of writing code carefully, I get a a lot of inspirations and ideas.
( I heard subscribing to his channel and watching him code helps you to clear the DSA round in placements. )
Thank you for reading,