Hello codeforces,

We all have done the classic question where there are two arrays, lets say, one denoting user-id and other denoting tenure. Now we need to sort both arrays so users with shortest tenure come first. Ex:

user-ids: [34, 51, 21, 22, 37] tenure : [ 1, 4, 1, 10, 3 ]

answer:

user-ids: [21, 34, 37, 51, 22] tenure: [ 1, 1, 3, 4, 10]

This is pretty straight forward with creating array of pairs and using library sort. However this ends up using O(n) extra memory. Surely if I wrote my own selection-sort or merge-sort, I could manage to do it in in-place by book-keeping the indexes and updating both arrays myself.

My question is, how can we do this in C++ using library sort, inplace, without creating a new array ?

For a personal project I'm working on, I need to sort a list by asking user preferences. Naturally the list can't be too long, at most 20 values. Now since complexity is not an issue, I'm focussing on reducing the number of questions asked. My initial idea was to use library sort and overload the custom comparator which then takes user input. But it seems to me that it's asking too many questions. I've also used a memoizing table, which returns answer for (x,y) if (x,y) or (y,x) has been answered by user before, but it's still unsatisfactory.

Help me design a sort which asks for minimum comparisons. Complexity of computation is not much of an issue, go wild.

In a certain problem, the complexity of my algorithm is O(n*sum_of_factors(n)), I want to get a simple bound for the complexity. Obviously one bound is O(n^3), since there can be n factors each with maximum value n, a better bound is O(n^2*sqrt(n)) since a number can have 2*sqrt(n) factors.

Please help me to give a better bound in terms of simpler functions of n, (simple is defined here as stuff you can find on a standard scientific calculator).

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 ?

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 ?

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 !!

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 !

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!

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!