maximaxi's blog

By maximaxi, history, 3 years ago, In English,

I have seen some people's code to represent a trie in a 2D array. For example, this is my old code to solve Autocomplete. However, I forgot how it works!

Can someone explain how to code a 2D array that represents a trie? I know that one dimension of the array represents the alphabet, and that the values inside the trie array are the node numbers, where the first letter you add is node number 1. Still, I'm confused where to insert values into the trie array, and how strings with the same prefixes would be distinguished in the tire.

Thanks.

#include <bits/stdc++.h>
#define rd(s) freopen(s, "r", stdin);
#define wt(s) freopen(s, "w", stdout);
using namespace std;

const int MAX=1e6+2, ALF=26+2;
int t, trie[MAX][ALF];

int main()
{
    //rd("test.txt");

    scanf("%d", &t);
    for (int i=1; i<=t; ++i) {
        int ans=0, n, numm1=1;
        for (int _=0; _<MAX; ++_) for (int __=0; __<ALF; ++__) trie[_][__] = 0;
        scanf("%d", &n);
        for (int j=0; j<n; ++j) {
            int node=0, idx=0;
            string word; cin>>word;
            while (trie[node][word[idx]-'a'] && idx < word.length()) {
                node=trie[node][word[idx]-'a'];
                ++ans; ++idx;
            }
            if (idx != word.length()) ++ans;
            //printf("ans is %d\n", ans);
            for (; idx<word.length(); ++idx) {
                trie[node][word[idx]-'a'] = numm1;
                //printf("new path from %d to %d via %c\n", node, numm1, word[idx]);
                node=numm1;
                ++numm1;
            }
        }
        printf("Case #%d: %d\n", i, ans);
    }
}

Read more »

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

By maximaxi, history, 3 years ago, In English,

This is for basic, below-IOI level problemsets. If one knows the top-down, recursive segment tree, it should be sufficient to solve all segment tree problems that don't rely heavily on constant-time optimization, right?

Read more »

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

By maximaxi, history, 3 years ago, In English,

I'd like to know, what's the most memorable contest you've participated in? It could be due to theme, the problems or some other crazy thing. It doesn't have to be CodeForces, but if you could link it, that would be great.

It's pretty hard to remember contests from a year back... and yet the One Punch Man one was cool, and I remember Round #361 (Div. 2) by reality gave me a serious reality check (excuse me while I excuse myself now).

Also I'm 7-8% weeb so if there are other anime-themed problems that would be cool. I know there are a few on DM:OJ (there's way more than just those btw) because the head problemsetters for 2-3 years were all huge anime'ers who watched some Grisaia no Kajitsu "Special" Episode for a whole hour right before a contest, at the contest venue... but that's another story *cough* FatalEagle *cough*.

So I'd love to hear your most memorable contest or favorite problems.

I slept at 6AM so I'm sorry if this post is extra cancerous to read.

Read more »

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

By maximaxi, history, 3 years ago, In English,

Conclusion (Edit 2): The HE staff replied:

We understand your concern. It's a known issue and we are already in the process of fixing it. We will get back to you once it's fixed.

I have massive respect for these guys, I don't think I even waited a full day for the response. Anyway, mystery solved.


Edit: Since it seems there is no consensus on why the following is present on the site, I've sent the team an email and will update this post with information when they reply.


On a contest page, it seems that even post-contest, if there are incorrect test cases but at least one is correct, the problem is marked solved like so:

a

It's the same on the problem's My Submissions page.

a

However, if you look at my submission, I have nine incorrect test cases.

a

Is this a bug or a feature, speaking objectively?

If it's a bug, I'll report it, and if it's a feature I'd like to know its purpose as it seems misleading to think you may have solved a problem when there could be incorrect test cases.

Read more »

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

By maximaxi, history, 3 years ago, In English,

Just want to make a quick thank-you to the problemsetters. We've been getting a nonstop inflow of contests, and our competitive programming lives couldn't be better. But we shouldn't forget that that without many hours (I'm sure at least 20+ per contest) of collective effort on the part of CodeForces staff and problemsetters who contribute their own time for the community's benefit, we wouldn't be able to enjoy a constant influx of original problems. So, thank you.

I hope more and more people will contribute interesting problems, and once I reach a level where I can come up with cool new problems, I hope to become a problemsetter for you guys.

Read more »

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

By maximaxi, history, 3 years ago, In English,

Could anyone help me out with Permutation Encryption?

The following is my code so far. pastebin.com/DDfN5Syt

Read more »

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

By maximaxi, history, 3 years ago, In English,

If you haven't qualified for Round 2 by placing in the top 1000 for 1A or 1B, round 1C will be written at 9AM UTC at the CodeJam website. Good luck everyone!

Read more »

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

By maximaxi, history, 3 years ago, In English,

Hello! The Smash the Code Contest is LIVE NOW, and it would be great to have many eager participants from CodeForces!

a

It's a bot challenge that runs for 8 days, with 4 leagues to conquer! See you on the leaderboard!

Read more »

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

By maximaxi, history, 4 years ago, In English,

Hey everyone. I'm super-hyped to announce the second April 20 Contest on DMOJ, brought to you by me and some of my friends from Thornhill Secondary School.

Details are on the contest page, but essentially it's a 3-hour unrated contest and you can participate from April 20, 1AM to April 24, 11PM.

Hope to see you on the leaderboard!

Edit: This frustrates me more than anyone, but due to a higher-up's decision the contest has become unrated, thus continuing a trend I wish it didn't. Apologies, and I hope you still come and check out the problems. One of them will be very, very original.

Read more »

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

By maximaxi, history, 4 years ago, In English,

Do you have any tips, or would you like to share your process? For example, do you start with a problem you have solved and add to it? Or do original ideas just pop into your head when you concentrate, and you put those together and you have a problem? I'm helping my team prepare a contest on another platform, probably contributing problems of Div2C or Div2D level (it's the extent my abilities allow).

Also, do you prefer problems that are based on concepts, or more on thinking and reasoning? Personally I prefer a mix (but mostly thinking problems). These thinking problems are also the hardest to come up with, it seems. Am I right in believing that they can only come from a flash of insight (or discussion with peers)?

Finally, do you have any topics, concepts, theories etc. that you think are underrepresented or would be interesting in the context of a programming problem?

In terms of general problemsetting advice, what I know is brevity and clarity are well worth the effort.

Thanks for spending your time on this open-ended question.

Read more »

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

By maximaxi, history, 4 years ago, In English,

Hey guys, so this past HackerEarth March Easy was rated. However, on the profiles of participants (I checked five or so), I couldn't find a rating score. (For example, say hello to lalit and notice how ctrl+f rating only returns a TopCoder rating.) Does anyone know where the rating can be found? Apologies if this was previously asked and answered.

Read more »

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

By maximaxi, history, 4 years ago, In English,

CodinGame's AI Challenge, Coders Strike Back is up now, and will be for about a week. I look forward to seeing you on the leaderboards!

Find it here.

Read more »

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

By maximaxi, history, 4 years ago, In Russian,

Hey everyone,

I don't know why but my entire display is now in Russian. I have not changed my settings prior to this. Can anyone help me change my language back?

Thanks, Max

Read more »

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

By maximaxi, history, 4 years ago, In English,

Hello everyone, could you provide some ideas for this problem? I think it might use sparse table.

Thanks!

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By maximaxi, 4 years ago, In English,

UPD: The contest will not be rated.

Hey everyone, I'd like to welcome you to the Thornhill Selection Contest on DMOJ.ca.

Basically, our school decided to make our selection process public so hopefully a larger audience can enjoy our work over the past weeks. It will be available to write for a week from Jan 7 to Jan 13. (UTC-5:00 time) You can check your own timezone here. You will have a 3 hour window with which to read the statements and submit solutions, and you can choose when your own personal timer starts counting down by when you join the contest.

The contest will have a nice difficulty curve and is mostly designed to be challenging to Cyan, Green, and Grey coders, although it has a few unique [although not necessarily difficult] problems for more advanced competitors as well. The overall difficulty is probably best described as belonging to Division 2 A-D. It will not be rated (not on CodeForces, on DMOJ :D). You can join the contest by registering an account at DMOJ.ca and clicking Join Contest on the contest page when it begins.

Thanks to the DMOJ crew and the problem setters.

Happy New Year!

Read more »

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

By maximaxi, history, 4 years ago, In English,

Hey, this is a humor post because it's New Year's. I appreciate your time here and I hope this will brighten your day a little. :) It's a chronicle of my first adventure on Yandex Contests.

a

Cool, so this is what Yandex Contests looks like.

a

Wait, mother of god... I'M A LEGENDARY GRANDMASTER!!

a

a

a

a

YESSSSSSSSSSSS

W-wait a minute...

Why am I suddenly a legendary grandmaster, exactly?

... looks to the upper-left corner

a

a

a

a

a

Read more »

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

By maximaxi, history, 4 years ago, In English,

Hello everyone,

Just a suggestion. Could more contests be scheduled on the weekend if possible? This would allow more people around the world to participate as many work or study from Mon-Fri on a regular basis. Unless there is a certain reason for why we shouldn't have contests on the weekend, it seems like a good idea to improve participation.

Thanks for your consideration, and I hope this message can reach the contest moderators.

Max

Edit: Great points have been made in the comments section. While I do hope for more weekend contests, it is completely understandable that there has been a recent shortage in them. Thanks to all of the people who replied.

Read more »

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

By maximaxi, 4 years ago, In English,
 
 
 
 
  • Vote: I like it
  • +22
  • Vote: I do not like it

By maximaxi, 4 years ago, In English,

For the purposes of these calculations, we will only consider the top ten countries in order of decreasing participating members in the past six months. (Prepare yourself, my geography is terrible.)

  • India is UTC+05:30.
  • Russia is from UTC+03:00 to UTC+07:00 (the most densely populated areas).
  • China is UTC+08:00.
  • Bangladesh is UTC+06:00.
  • Egypt is UTC+02:00.
  • Iran is UTC+03:30 and UTC+04:30.
  • Ukraine is UTC+02:00 and UTC+03:00.
  • Vietnam is UTC+07:00.
  • USA is from UTC-08:00 to UTC-04:00 (the most densely populated areas).
  • Belarus is UTC+03:00.

We now round the :30 timezones for simplicity. The most convenient times in general are colored green, okay times are colored orange, and inconvenient times due to a a typical work/school day are colored red. These are generally negated on the weekends.

img

If the image on CodeForces is blurry please see this link.

So it seems that the best times to start contests would be between UTC 11:00AM to UTC 07:00PM and from UTC 12:00PM to UTC 5:00AM. In MSK, that's 2:00PM to 10:00PM and 3:00AM to 8:00AM.

I hope this has helped, and if you catch any mistakes, feel free to drop a comment.

Read more »

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

By maximaxi, history, 4 years ago, In English,

Hello, I'm just getting started with Segment Trees and I'm curious as to what they can be used for in terms of programming competitions. I know the basic RMQ, GCD, and cumulative sum concepts but I'm not sure what else they can be used for, and what types of problems I should look out for to apply segment trees with.

Any applications and/or problem links would be appreciated.

Thanks for this amazing community,

Max

Edit: Thanks for your responses.

Read more »

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