### Noam527's blog

By Noam527, history, 5 weeks ago, ,

In the problem archive right now, we are able to sort the problems by the amount of people who solved it (and also filter by the subjects the problem requires), but that's it.

I was wondering whether we should have more options to sort by. For example, the feature to make a contest or a problem one of your "favourites" already exists, so what about being able to sort the problems in the archive by the number of people that made it one of their favourites? (Could also be applied to favourite contests.)

I'd be happy if more options were suggested in the comments, as I don't have many, but I am interested to hear some more.

MikeMirzayanov (Hopefully this is worth the mike-tag :P.)

•
• +25
•

By Noam527, history, 2 months ago, ,

Hey!

I am not related to the organization of this competition, however there doesn't seem to be any blog post regarding it (and there's not much time left), which is unfortunate so that's why I'm writing this :).

Today (in approximately 4.5 hours, 14:00 UTC) starts this year's COI — Croatian Olympiad in Informatics. The contest is open and the registration page is here (while this page contains a redirect to the registration, along with their past problemsets).

The competition should be close to IOI style; It seems to contain ~4 problems and from what I understood, has a duration of 5 hours. A big difference is that there is no full feedback during the contest: every submission is only tested on the samples provided during the contest (I would expect them to change this format for COI but it doesn't seem to be the case).

Good luck! Let's discuss the problems and the solutions here after the contest ends :).

•
• +43
•

By Noam527, history, 4 months ago, ,

This is a quick question; I'd like to know if there is any place (some online judge possibly) in which I could put 2 programs of mine to interact with each other, just like interactive problems work here (the judge's program interacts with the submitted program).

And if there seems to be none, I'm wondering what's the best way I could implement something to do this for me.

Thanks :).

•
• +26
•

By Noam527, history, 4 months ago, ,

I have 2 questions in mind, just out of curiousity :). They both consider tries (not compressed). Also note — by a trie's size I'm not considering its root (even though, it does not matter for the purpose of this problem).

1) For some 2 natural numbers N and K (suppose K ≤ N), what is the maximal size of a trie that can be achieved if you take some string S of length N, with the size of its language (number of distinct characters it can contain) being K, and insert into the trie all its suffixes (so, a suffix trie)?

For instance, if N = 2, K = 2, we can form the string "ab", which makes the trie of size 3. On the other hand, if N = 10, K = 1, the only string we can form is "aaaaaaaaaa" which makes the trie size 10.

2) How do you form such a string with maximal trie size? An algorithm or an idea, both are acceptable.

Thanks.

•
• +11
•

By Noam527, history, 5 months ago, ,

Usually the wavelet tree is made not to support updates. I wonder what types of updates it can recieve that will still keep all its operations in , where A is the range of values it gets. For instance the only one I found is that you can support appending or removing the element from the back of the array (on which the wavelet is built).

A short tutorial for this data structure can be found here, for those who are interested.

•
• +10
•

By Noam527, history, 6 months ago, ,

I really want to know what's the shortest problem statement in CF but I'm unable to find a blog post talking about it. So, what's the shortest problem statement you know of in CF?

•
• -3
•

By Noam527, history, 6 months ago, ,

Here is a problem I thought of. This is just for others' interest, maybe to help them pass the time. I thought of this problem initially because I wanted to put it in a contest, however it turned to be too hard for me and a few others so it shouldn't be in a contest:

you need to construct a permutation of length N. you're given M pairs of integers (each pair contains 2 distinct elements, both are between 1 and N). the permutation you construct needs to have the following value minimized: for each pair {X1, X2}, add up to the total sum the distance (indicies distance) between the values {X1, X2}. you can print any correct answer is multiple ones exist.

input:
N M
M pairs, described in the statement
output:
the minimized value described in the statement on the 1st line, and the permutation on the 2nd one.

examples:
input:
3 2
1 2
3 1
output:
2
3 1 2

input:
4 4
1 2
4 2
3 1
3 4
output:
6
2 1 4 3


•
• +75
•

By Noam527, history, 7 months ago, ,

I came up (I think, I just didn't see it anywhere) with this problem earlier today and I think it's better if I ask for help here as I still don't know its solution:

You have an array of N integers and in each step you can merge any 2 of them into a single integer (and then this integer is added to the array while the previous 2 are erased from it). The cost of merging two elements X and Y is max(X, Y).

You need to find the minimal cost you can get after merging all the integers into 1 (essentially, doing N — 1 merges).

Currently there's no constraint (not on N, nor on the limit of the integers) so just try to come up with the best complexity you can.

Examples:

input:
3
4 6 8
output:
16


(merging 4 and 6 to 10 with the cost of 6, and then merging 8 and 10 with the cost of 10, giving a total of 16).

input:
4
10 11 13 16
output:
55
(10->16) + (11->13) + (24->26) = 16 + 13 + 26 = 55.


•
• +12
•

By Noam527, history, 9 months ago, ,

I came up with the following problem a few days ago and I didn't manage to solve it in a better complexity than O(NlgN + QN), maybe you can help as I'm stuck and starting to think it's impossible:

You're given an array of N elements, and Q queries. Each query consists of a single integer X, and you're asked to determine if there's a pair of integers in the array whose sum is X, or if there isn't any.

I didn't determine any limits, but the less, the better. some bounds can be on the maximal value of an element in the array, I don't mind, as long as someone finds a solution better than mentioned earlier. Would also be better if the algorithms will be able to output the indicies of the 2 integers with sum X.

I'd also be happy if someone proves it to be impossible.