### pikmike's blog

By pikmike, history, 2 years ago, translation, ,

985A - Chess Placing

Tutorial
Solution (Vovuh)

985B - Switches and Lamps

Tutorial
Solution (Vovuh)

985C - Liebig's Barrels

Tutorial

985D - Sand Fortress

Tutorial
Solution (PikMike)

985E - Pencils and Boxes

Tutorial
Solution (PikMike)

985F - Isomorphic Strings

Tutorial

985G - Team Players

Tutorial

• +80

 » 2 years ago, # | ← Rev. 2 →   +21 Okay, formulas got better.
 » 2 years ago, # |   0 In problem D, for n=5,H=2, why is [2,3] wrong? I seem to be missing something here
•  » » 2 years ago, # ^ |   +29 The pillars are infinite. So your example is [2, 3, 0, 0, ...]. The difference between 3 and 0 is beyond 1.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Ahh damn I knew I was missing something simple. Thanks!
 » 2 years ago, # |   +5 Problem D binary search on h the height becomes h,h-1,h-2...2,1,0 and if h>H make it becomes H and change the height on the right too. if H=5 There are two case: 1. [9,8,7,6,5,4,3,2,1,0][ 5,6,7,6,5,4,3,2,1,0] Sum=(9+1)*9/2-(4+2+0...) 2. [8,7,6,5,4,3,2,1,0][5,6,6,5,4,3,2,1,0] Sum=(8+1)*8/2-(3+1+0..) find the smallest h that sum>=n Note: 1+3+..n=[(n+1)/2]^2=tmp 2+4+..n=tmp+n east to calculate
 » 2 years ago, # | ← Rev. 2 →   +5 for D exists O(1) solution. http://codeforces.com/contest/985/submission/38514950
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Does sqrt work in O(1)?
•  » » » 2 years ago, # ^ |   +9 Nope, but STL sqrt works faster than O(loglogn).
•  » » » 2 years ago, # ^ |   0 SQRT works very fast.see http://acm.timus.ru/rating.aspx?space=1&num=1001 solution rating !!
 » 2 years ago, # |   +1 Can you please explain this- "Otherwise, for each i from 1 to n let's take no more than k smallest staves from this segment in the i-th barrel, but in such way, that there are at least n - i staves left for next barrels."
•  » » 2 years ago, # ^ |   0 Every barrel will have atleast one stave from the range [1,rg) otherwise there will be two barrels whose volume difference will be greater than l.So for each barrel i from 1 to n, start picking up the staves (smallest first) from [1,rg) until you reach the required number of staves (k) or if there there are fewer than n-i staves left in the range [1,rg) because you still need to build n-i barrels and each of these needs atleast one stave from this range
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 i didn't get the logic for selecting n staves in the range[1,rg) to get the maximum sum of volume can we use this logic n, k, l = map(int, input().split()) a = sorted(list(map(int, input().split())))p = 0 while p < len(a) and a[p] — a[0] <= l: p += 1 if p < n: print(0) exit()ans = 0 u = 0 for i in range(n): ans+=a[u] if u+k<=p-1: u=u+k else: u=p-1 #print(u) print(ans)
 » 2 years ago, # | ← Rev. 4 →   0 Correct me if I am wrong.In the first example for problem C:4 2 12 2 1 2 3 2 2 3Isn't [1, 2], [2, 2], [2, 2], [3, 3] a valid solution with answer 8?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 l = 1, and the volume of your first barrel is equal to 1, and the volume of your fifth is 3,so abs(3-1) is definitely bigger than 1.
•  » » » 2 years ago, # ^ |   +2 Ah, I get it. Thanks.
 » 2 years ago, # |   0 How the solution for 985A works? what principal/logic is this? I'm struggling to understand.
•  » » 2 years ago, # ^ |   +3 You have to first sort the positions of the pieces because in one move you can either move left or right. We need to sort the positions to get optimal answer. Now the there are N positions and N/2 pieces. These N/2 pieces can be on black position or on white position since we need to place them in same color. Black positions are odd numbers till N and white pieces are even numbers till N (BWBWBW....BW) . Now the number of steps required by each piece is the absolute difference of required position where it should be and initial position of the piece given in the array. Thats what they have done for N/2 pieces. They are taking the minimum steps when placing in white position and black position.
•  » » » 17 months ago, # ^ |   +1 Thanks saumyadip
•  » » » 2 months ago, # ^ |   0 WHY ARE YOU USING REQUIRED POSITION AS 2*i and 2*i-1
 » 2 years ago, # | ← Rev. 2 →   0 For Problem C if there exists a configuration- Why only n-i barrels should be left for the barrels which appear next
•  » » 2 years ago, # ^ |   0 Not only n-i barrels solution says at least n-i barrels so that for remaining barrels at least one stave is available for making each barrel 'equally enough' with every other barrel.
 » 2 years ago, # |   +8 In author solution of problem F, is the mt19337 random generator unpredictable enough?
•  » » 2 years ago, # ^ |   0 If a seed of generator is fixed, any random generator will generate same sequence every time. So it is necessary to set a seed with diffenent values.On the other hand, as author, I would like to have a deterministic solution which will not depend on time it was started.
•  » » » 2 years ago, # ^ |   0 I guess it is OK to use hash without unpredictable random in author solution (if the hash is strong enough, like the 8-modulo hash in author solution for F). No one beside author can see the solution and generate the anti-hash testcase until the end of the hacking phase.
 » 2 years ago, # |   0 i dont understanf why i am getting TLE in problem C my code
•  » » 2 years ago, # ^ | ← Rev. 3 →   +1 Java's inbuilt Arrays.sort() uses a double pivot quick-sort whose worst case is O(n^2), So, it can be hacked by a testcase specially designed to break it. Some O(nlogn) sort like Merge sort or heap sort could be used or radix sort. You can also add a random shuffle before Arrays.sort or use Integer instead of int so that java's inbuilt Arrays.sort() over Objects(timsort) will be used.TLE with Arrays.sort()-38492535AC with Arrays.sort() over Integer- 38524250My Java solution also TLEd due to same reason :(
•  » » » 2 years ago, # ^ |   0 thanxx man, got it!!! and does it only happen in educational rounds or in normal rounds we should take care of Arrays.sort()
•  » » » » 2 years ago, # ^ |   +1 Usually normal rounds are of small length, so this kind of hacks rarely happen. But creating a custom sort function which first randomly shuffles the array and then sorts or some other sort should be on the safer side.
 » 2 years ago, # |   +4 Can Somebody explain DP part of Solution E
•  » » 2 years ago, # ^ |   0 Same question xD
•  » » 2 years ago, # ^ |   +9 Also, NecrozmaMaybe the code of O(n 2) solution will help a bit more? Codefor (int i = 0; i <= n; ++i) dp[i] = 0; dp[0] = 1 for (int i = 0; i < n; ++i){ for (int j = 0; j <= i; ++j) if (dp[j] == 1 && i - j + 1 >= k && a[i] - a[j] <= d) dp[i + 1] = 1; puts(dp[n] == 1 ? "YES" : "NO")
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Hey, by checking i+1-j>=k, you basically check if i and j can be taken in a segment, what if the jth is already taken in some previous segment and taking i,j together "disturbs" it?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +7 You update from dpj and that is the state for the first j elements being distributed. j-th element is the first one not taken.
•  » » » » » 2 years ago, # ^ |   0 That was awesome !! Thanks a lot :) @PikMike
•  » » » » » 2 years ago, # ^ |   0 Please can you explain the use of array f[N] . I am not able to understand.
•  » » » » » » 2 years ago, # ^ |   0 That is BIT
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 Problem E. I dont understand why Time Limit is Exceeding in my code[submission:38589137]. I think time complexity of the problem is decent O(nlogn).
•  » » » 2 years ago, # ^ |   0 Thank you very much. It helped me a lot.
 » 2 years ago, # |   0 can anybody help in understanding div 2 C,i havent got the idea n-i stacks to be left for each i??
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 First, sort array in non-decreasing order.We must have a barrel which contains a 1 stave. So each maximal total sum of volumes of barrel cannot be larger than a1 + llet C = (number of stave which has length  ≤ a1 + l) - N.If C < 0, then answer is 0.Otherwise, While picking staves, if C > 0, pick the smallest stave you have, and decrease C by 1. else, pick the largest stave you have.
•  » » » 2 years ago, # ^ |   +3 thanks i got it!!
 » 2 years ago, # |   0 How to solve F with LCP?
 » 2 years ago, # |   0 Someone please help me with this last line of code given in Ediorial for problem D.printf("%lld\n", check(r) ? get(r) : get(l));
•  » » 2 years ago, # ^ |   0 When check ==1 run get(r) function and that function returns a ll type , else call get (l) function and get another ll, this is basically a shorthand in c++
 » 2 years ago, # |   0 cannot wrap my head around picking staves in problem C. How do I know to pick which indices while iterating? For ex in first test case how do I know to pick 1 2 2 2?
 » 2 years ago, # |   +3 PikMike, Can u give me any practice problem link similar to DP involved in Problem E? P.S : I am new to DP.
•  » » 2 years ago, # ^ |   0 Huh, you know, this is such a basic dp usage. No particular problem comes to my head. I can recommend to search some dp trains on e-olymp, they have lots of great contests on certain topics.
»
2 years ago, # |
Rev. 2   -29

I submitted using my solution but its giving TLE for test case 7. Can anyone suggest any optimization over my solution.

Soln...

# define ll long long

using namespace std;

int bin[500001];

int binsearch(int* a,int low,int high,int allow){

if(low==high){
return low;
}

int mid=(low+high+1)/2;

if(a[mid]<=allow)
return binsearch(a,mid,high,allow);

return binsearch(a,low,mid-1,high);

}

int fn(int *a,int low,int high,int d,int k,int n){ if(low>high) return 0;

//cout<<"Start FN"<<endl;

if(high-low+1 <k){
//cout<<"Error 1"<<endl;
bin[low]=0;
return 0;
}

if(bin[low]!=-1)
return bin[low];

int index = binsearch(a,low,high,a[low]+d);
//cout<<"Index ="<<index<<endl;

if(index==n-1){
bin[low]=1;
return 1;
}

int elesize = index-low+1;

if(index-low+1<k){
//cout<<"Error 2"<<endl;
bin[low]=0;
return 0;
}

if(fn(a,index+1,high,d,k,n)){
bin[index+1]=1;
return 1;
}

int l=low,r=index;
while(l<=r){
if(l==r){

if(fn(a,l,high,d,k,n)){
bin[l]=1;
return 1;
}

}

int m=(l+r)/2;
if(m-low+1>=k && fn(a,m+1,high,d,k,n)){
bin[m+1]=1;
return 1;
}

else if(m-low+1 < k){
l=m;
continue;
}
r=m-1;
}

//cout<<"Error 3"<<endl;
bin[low]=0;
return 0;

}

int main() { memset(bin,-1,sizeof(bin));

int n,k,d;cin>>n>>k>>d;

int a[n];

for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);

if(fn(a,0,n-1,d,k,n))
cout<<"YES"<<endl;

else
cout<<"NO"<<endl;
return 0;

}

 » 2 years ago, # |   0 Well it is annoying that the third problem WA on test 13
 » 2 years ago, # | ← Rev. 2 →   +3 in problem F. More over, if we sort all positions posis for all distict characters in s and sort all positions posjt for t, then posis must be equal posit for any i. can someone expalain this?
•  » » 2 years ago, # ^ |   +5 If both strings are isomorphic, then the first occurrence of character X in S MUST be the first occurrence of some character Y in T. So if you sort the positions of first occurrences of distinct letters for S and T, they will be exactly same (only if they are isomorphic, also the reverse might not be true).
•  » » » 2 years ago, # ^ |   0 Thanks. got it.
 » 2 years ago, # |   0 About problem 985E — Pencils and Boxes. I was thinking about proof. For "YES" condition its fairly simple. But what about "NO". Can'nt we get other segments. other than what is describe by DP solution.
•  » » 2 years ago, # ^ |   0 Usually, there is next idea behind this type of task: (solution exists)  →  (author solution finds answer) !(author solution finds answer)  →  !(solution exists).
 » 2 years ago, # |   0 for Problem C, Why is this going wrong ~~~~~ Arrays.sort(arr); int limit = l+arr[0]; int li=-1; for(int i=0;ilimit) { //pw.println(arr[i]); li=i; break; } } //li is the index such that all integers before are within range of l from arr[0] if(li==-1)li=n; int noofsmallest = li; if(noofsmallest
 » 17 months ago, # | ← Rev. 3 →   0 adedalicFor test case 6:Input: 10 30 accbaaccac 6 8 3s=acct=cacI think this is isomorphic and I printed YES but the verdict after submitting my solution says as NO
 » 13 months ago, # |   0 Another approach in problem E is to first sort the whole array. My approach- https://codeforces.com/contest/985/submission/54277798 Now start from back, I am using 0 based indexing, now mem[j] stores if from index j, I can have a soln. or not. Base case is mem[n]=1 and mem[j] can be known as we need to know nearest location after k indexes from where mem[i]==1. or just look at my soln.- In my soln. mem[j] stores if from index j ican construct a soln. or not. nr[j] stores nearest index >=j where mem[i]==1.
 » 13 months ago, # |   0 can anyone please help me in A problem...how you come up with the idea of this formula
 » 11 months ago, # |   0 In second question if you enter 2x3 matrix 1 1 0 0 1 1 so answer will be yes or no ???Tutorial's code give yes but answer will be no!!
•  » » 11 months ago, # ^ |   0 answer is "no" obviusly, and the tutorial code also gives "no"
•  » » » 11 months ago, # ^ |   0 Tutorial c9de gives yes
•  » » » 11 months ago, # ^ |   0 You can check it
•  » » » » 11 months ago, # ^ |   0 i've checked. it gives no
•  » » » » » 11 months ago, # ^ |   0 ohhh really it gives yes i checked it again
•  » » » » » » 11 months ago, # ^ |   0 i checked it 4 times and it gives no
•  » » » » » » » 11 months ago, # ^ |   0 input is 2 3 1 1 0 0 1 1 ????
•  » » » » » » » » 11 months ago, # ^ |   +3 input is 2 3 110 011
•  » » » » » » » » » 11 months ago, # ^ |   0 there is 2 switch if you you on only one switch how it posible all lamps on.
 » 7 weeks ago, # |   0 Can someone explain to me how the O(n^2) solution is working in case of ProbE Pencils and Boxes? I am facing a lot of difficulty in understanding how the given solution is taking care of the constraint that every box contains at least k elements.
 » 4 weeks ago, # |   0 In problem E, does anyone know a top-down DP approach? Thanks a lot.