BaeYong's blog

By BaeYong, 10 years ago, In English

Hi guys, As a future blast red coder I have faced a challenging problem. How do you guys put a distinct name for the problems of CF when you save them on your machine? Do they have a unique ID numbers like other OJ does? It is too annoying to put names like PashmakAndParmidasProblem.cpp.

Thanks for understanding my sense of humour. -Bay.

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

»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

As none even close to red I always simply used humourless names like cf235b.cpp.

»
10 years ago, # |
  Vote: I like it +129 Vote: I do not like it

This is a very good question. Although it seems that it can be solved by the simple algorithm of selecting a name and checking its uniqueness, careful analysis reveals a cost of O(k) per comparison -- and since each potential name requires up to n checks, and there may be up to n names tried, this results in O(n3k) worst case performance (over n insertions where each potential name has length k). If you've solved as many CF problems as I have, you'll quickly realize that a faster solution is needed.

Fortunately, we can speed up the name checking process to O(k) using a trie! Here is some sample code:

struct trie {
    trie* children[4294967296]; // Unicode support
    trie();
    virtual ~trie();
} root;

template<typename T>
bool isUnique(T* str)
{
    trie* t = &root;
    for (int i = 0; str[i]; t = t->children[str[i]], i++)
        if (t->children[str[i]] == nullptr)
            return true;
    return false;
}

I've left out a few details here but I'm sure you can fill them in. This yields an O(n2k) algorithm, which should be fast enough for your needs. If the trie structure takes up too much space in memory, you might find this site useful. Hope this helps!

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it problem

»
10 years ago, # |
  Vote: I like it +30 Vote: I do not like it

You don't actually need to make the comparisons. If you'd like to have some adrenaline rush, you can just select the filename at random. I find this code (Python) sufficient for my needs:

#!/usr/bin/python3

import random
print(''.join([random.choice("1lI") for i in range(20)]) + ".cpp")

A few example runs (I generated them for the upcoming contest):

1lI1IllllIlI1l1llIll.cpp
lll11Il1Il1111II1III.cpp
l11Il1I111IlI111l1Il.cpp
l11IIll1111lIllI1l1I.cpp
1l1ll1I1111lIIl11lll.cpp

As there are 320 ≈ 3.4·109 possible filenames, this should do well for about CF task solutions, which is much more than the number of past problems. If you don't use C++, you can substitute the .cpp extension with anything else. I hope I helped you :)

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

not sure if i should laugh at

As a future blast red coder

or at the question itself! :D

»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Sweeet! Thank you guys.

»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

A friend of mine (qazwsxedcrfvtg14) only use a file named lkk.cpp. Whenever he is solving a new problem, he clear the content of that file and reuse it!

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In my opinion qwe.cpp is more logical and faster to type than lkk.cpp. Anyway, I use qwe.cpp as I'm too lazy to create more files, directories etc.

»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

As a future gray coder, I create a special folder for contest, with files FIRST.cpp...FIFTH.cpp, which contain this code:

#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#include <string>
using namespace std;
int n,m;


int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
return 0;
}

So all the libraries are prepared and I should only write the code itself. (I'm not sure if I ever use FOURTH.cpp and FIFTH.cpp although)

»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

just cf.cpp :D

»
10 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I don't save them at all. I kind of depend on CF to store my solution for me. But I just realized what great mistake I have done.

At UVa, if you mail them requesting for your solutions, they send you all your solutions zipped in a file. Do you think it's possible here at CodeForces? Cause going through the solutions and storing them manually is going to be hard :(