Блог пользователя BaeYong

Автор BaeYong, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -23
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +129 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it problem

»
10 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

not sure if i should laugh at

As a future blast red coder

or at the question itself! :D

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Sweeet! Thank you guys.

»
10 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

just cf.cpp :D

»
10 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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 :(