prac64's blog

By prac64, history, 2 months ago, In English,

Hi Codeforces,

I use sublime-text3 editor to write codes, and CMD to run them. But sublime text does not have a feature to replace all endl's with '\n' , I tried recording a macro, but that only records characters printed on the screen, so that failed.

I don't use #define because that looks bad in the code and has resulted in frustrations before(forgetting that endl is not flushing the buffer and hence getting no output on incorrectly terminating programs).

Can someone write a script or snippet or anything that can do the above operation in 2-3 keystrokes ? Alternatively, point me to resources that can help me learn how to do that ?

Read more »

 
 
 
 
  • Vote: I like it  
  • -17
  • Vote: I do not like it  

By prac64, history, 2 months ago, In English,

The general boat river problem is that, you have a river and a boat, the boat can carry atmost 2 people at once. The objective is for all people to cross over to the other side of the river.

Each person limits the time it takes to cross the river when that person is in it. Example: if a A has a limit of 1 and B has a limit of 2 and they cross the river while in the same boat then it takes 2 minutes for them to cross i.e. max(A,B)

Now in the general problem some small number of fixed limits are given, lets say 1,2,5,6, and the minimum time for every person to cross the river is asked. In this case the answer is 13, first 1&2 go, then 1 comes back, then 5&6 go, then 2 comes back, then 1&2 go to the other side, now every one has crossed.

But what if an array of limits is given ? lets say of size 10? or 20? or 50?, how do you solve this then ? What is the complexity to solve it programatically ?

Read more »

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

By prac64, history, 4 months ago, In English,

I saw a question somewhere, which asked to find the number of distinct numbers which can be represented as sum of two distinct primes. T=10000,N=10000000, the question felt impossible, so after attempting for a while, I saw the editorial, the solution was incorrect and poorly written.

If we did not have distinctness constraint, we could use goldbach conjecture and also mark p+2 as true(where p is prime) in a sieve and find the ans, but here we want only distinct sum of distinct primes, above approach would include 4(2+2) in the answers, which is not okay.

Even though the question is probably not solvable for the given values(i.e. n=1e7), what would be your best algorithm for this problem. And upto what n could it solve the problem for ? (1e3? 1e4? 1e5 ? 1e6 ? 1e7?)

Is it possible to answer more queries ? (lets say the limit comes from space complexity, so we can answer more queries)

sample cases n=4 ans=0

n=5 ans=1 (5=2+3)

n=9 ans=4 (5=2+3,7=5+2,8=5+3,9=7+2) (6=3+3 is not valid because the primes are not distinct)

Thank you codeforces !!

Read more »

 
 
 
 
  • Vote: I like it  
  • +8
  • Vote: I do not like it  

By prac64, history, 4 months ago, In English,

I am horrible at string problems, especially the ones that involve indexing maths and corner cases. I rarely get a string problem correct even after getting the algorithm right.

Codeforces does not seem to have such "dirty" indexing/cases problems but, other platforms such as hackerearth and codechef have many. Regardless, I need tutorials, tips and tricks to solve such problems !

Thank you Codeforces !

Read more »

 
 
 
 
  • Vote: I like it  
  • -11
  • Vote: I do not like it  

By prac64, history, 5 months ago, In English,

Hello Codeforces,

Recently I came across a problem where we have to output the minimum number of fibonacci terms needed to make up a number. Repeating the terms to make up the representation is allowed. The fibonacci sequence 1,2,3,5,8,13,21.. will be used for all cases.

I can explain better with an example, lets say N=6, then the answer is 2, you can use the numbers 1 and 5 to make 6, another combination is 3 3, which also gives the optimal answer 2. However in this question we only need the minimum number of terms, not what those terms are.

Other examples: input = 5 output = 1 input = 7 output = 2 input = 19 output = 3

I tried out some examples and even submitted the greedy algorithm on this problem, which is to keep subtracting the largest fibonacci number possible which still keeps the result non-negative, and adding 1 for each of those terms subtracted. A few blogs on the same topic give this algorithm for solving the problem, however no proof on correctness.

A quick wikipedia search yielded Zuckendorf theorem, which just proves uniqueness with non-adjacent terms, I was unable to extend it to greedy or minimum.

Does anyone have a proof on correctness(or a counter-case is welcome too :D ) ?

Thank You Codeforces!

Read more »

 
 
 
 
  • Vote: I like it  
  • +31
  • Vote: I do not like it  

By prac64, history, 8 months ago, In English,

Hey CodeForces, recently I came accross a problem, finding an element in an array which occurs more than n/3 times, while using constant space and linear time. Now I admit, this is a well known interview problem and plenty of articles exist which cover this, however I have struggled to find one that offers proof of correctness or any explanation.

Please help me understand the correctness.

Article: https://www.geeksforgeeks.org/given-an-array-of-of-size-n-finds-all-the-elements-that-appear-more-than-nk-times/

Basic Idea: Like we do in Boyer-Moore algorithm, however instead of keeping one element and counter, keep 2 , then update them similar to the original algorithm.

Thank you CodeForces!

Read more »

 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it