Alex7's blog

By Alex7, history, 2 years ago, In English,

Given 2 binary strings A and B of each with length at most 175, we want to combine them to produce a new string C the following way: As long as either one of strings A, B choose one of them (as long as it's non empty) add the first character in the chosen string to the end of C and then delete from that string. The task is for each distinct possible resulting C sum the square of the number of ways you can arrive at it with that procedure modulo some prime.

This problem was presented in a local IOI selection in 2012, we suspect it was ripped from some USACO related contest (since all other problems that year were also stolen from there), so I don't really have a link for it but I know it's possible to solve it. Any ideas? Thanks in advance.

Read more »

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

By Alex7, history, 2 years ago, In English,

I am trying to create a practice mashup and the gym page is very unresponsive, I get a ton of bad gateway errors and after grinding it out and succeeding in creating the mashup, it says that I don't have access to edit it. Admins, please take a look.

Read more »

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

By Alex7, 3 years ago, In English,

So I solved problem K using DP, but the tutorial video said that some contestants managed to solve it with regular expressions.

However, the K-quotation in general is a context free grammar not a regular expression. I guess if you fix K it will become a regular expression but the length will grow too fast as K grows and since matching it requires 2^(len of expression) preprocessing I don't see a realistic way of doing it.

How did they manage to use regular expressions to solve the problem??? problem link, solution video

Read more »

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

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

You're given a rooted tree with N nodes and Q queries in each query you have an integer K and you want to delete the nodes of the tree the only restriction of deleting some node is that it must be either the root or its parent must be deleted and you can delete at most K nodes each second, what is the minimum time for deleting all nodes?

N <= 10^6 Q <= 10^6

Problem Link

Read more »

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

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

So I'm very curious to see how those factors correlate to your codeforces rating and other competitive programming accomplishments.

I hope that enough people will answer those questions so we'd get a representative sample and see what works on average and what doesn't.

1- How old were you when you solved your first competitive programming problem?

2- What is your primary programming language?

3- How many hours do you (on average) train weekly?

4- How many hours do you estimate that you've trained your entire life?

5- How many minutes do you spend on average thinking about a problem before giving up and reading the tutorial?

6- How many hours do you sleep on average?

7- Do you drink coffee and/or other caffeinated beverages during competitions?

8- Do you drink coffee and/or other caffeinated beverages during training?

9- How many years have you been training?

10- How much did your school promote critical thinking Rate on the scale of 1-10 (1 being rote learning all memorization no thinking at all and 10 being awesome super genius teachers)

11- How many months did it take you to reach Div 1?

I know that those are a lot of questions but please answer them so I can prepare some wonderful graphs and stats.

Also feel free to suggest any other factors that might have some impact.

Please answer in this form because it will make the data much neater :D

Read more »

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

By Alex7, 4 years ago, In English,

Those 4 guys are going to be Syrias IOI team for 2016. Just look at their expressions as they're trying to solve the problems we prepared for them. :D :D

besher tweety samier_aldroubi

Read more »

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

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

Check this out 16507699 . It gets ok on the first 7 tests then CE. This stuff is weird :v :V

Read more »

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

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

So here is another installment of my step by step series, trying to solve 366D - Dima and Trap Graph :D please enjoy. Link here.

Read more »

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

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

So I just made this video, a tutorial for Tarjan's algorithm for finding bridges.

It's less than 6 mins long.

This video is an experiment, I tried a lot of new things and I'm waiting to see if you guys like it or not. I will continue to do my step by step videos, this might be a different series.

Read more »

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

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

So I just made my first video which is a step by step tutorial of this problem 634E - Preorder Test. The video link is Here. Please watch it and tell whether I should make more or improve anything. Your suggestions are welcome :D.

(P.S. Sorry for the terrible quality, somehow youtube converted my 720p to 360p for no reason. I'll try to fix it.)

Read more »

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

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

Here is a classic problem where you have a set N points on a straight line and you want to choose some point (from that set) such that the sum of the distances between that point and every other point is minimized.

A famous problem adopting this simple idea is IOI 2011 Ricehub.

It makes sense that the optimal point is the median of our N points. I usually prove it either by visualization or studying the how many times we end up summing the line segments between each two consecutive points.

Are there any simpler more elegant proofs ?

Show us how beautiful your minds are :D!

Read more »

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

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

So I just read this and I think it's cool porblem is I don't know anyone who's into AI. So if you're interested to make a team with me please tell me :D

Read more »

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

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

So codeforces hasn't been beta for a long long time now. So why the Beta sign?

Read more »

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

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

So since I discovered that I'm a friend of 149 users, I have been dying of curiosity. I want to know who they are.

Do you guys think it's a cool feature to have?

Read more »

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

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

Life is short, I don't want to spend years to get back to that beautiful yellow :D

Read more »

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

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

I need a few advice about math in general. I'm gonna start college sometime this year and I wanna work on my mathematical background.

What are the field of math required for computer science?

What are some good sources to learn math and solve math problems?

:D

Read more »

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

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

Is the test data of BOI 2014 and 2015 problems available somewhere?? Are the tasks available on some OJ?

  • I didn't find the test cases in the official sites -

Read more »

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

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

Unless IOI 2015 has an official site other than this . I think it may have some organizational problems.

No practice tasks and no schedule, we don't even know were the trips are going to be!!!

On the bright side, we know all about the food :D .

Have I some announcement somewhere?

Read more »

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

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

So we've been trying to contact IOI 2015 for a couple of days now, about the invitation letters and stuff so we can start working on the visa, but they aren't responding.

Do you know anyway of contacting them other than their emails which are listed on their site?

It's very urgent so any help would be appreciated.

Read more »

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

By Alex7, 4 years ago, In English,

Would it be practical to make a suggested list of problems for training based on rating ranges?

Read more »

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

By Alex7, 4 years ago, In English,

How much does pure mathematics help in competitive programming?

Will an IMO medalist get familiar with programming faster than a normal person?

What are the downsides for having a mathematical background in terms of coding and efficiency ( if there exists any )?

Competitive Programming is my first real authentic approach to science, (Yeah, our education system is that bad), so my mathematics is next to zero, what are the mathematical subjects that could help someone directly or indirectly in Programming in general?

Also, in ACM-ICPC style competitions, how does a mathematician contribute to the team exactly?

It would be very interesting to hear about real life examples and so-on :D.

Read more »

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

By Alex7, 4 years ago, In English,

I started searching for various OI problemsets so I could make myself I couple of contests so far I've only found: IOI, CEOI, Balkan/Baltic OI, Open JOI, POI, COI and USACO.

But the sad thing is that I've already seen most of the problems from the previous contests like IOI or COI.

Do you have any other contests to suggest?

P.S. Anything with an English statement and testdata would do :D

Read more »

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

By Alex7, 4 years ago, In English,

Participating in a big competition like IOI or ICPC can be intimidating, the worst thing that might happen to you is that you manage to get nervous enough to enter that adrenaline-fueled fight or flight state, you start feeling that you need to get out of the contest fast. An easy bruteforce solution that would take you 2 minutes to code in a normal environment suddenly requires 10 minutes, or at least that's what happened to me the last 3 major competitions I participated in (APIO 2014, IOI 2014 and APIO 2015), while it wasn't very noticeable in APIO 2014 -I quickly forgot about it because it was my first medal a bronze one- and I blamed that state on sickness in IOI 2014, after APIO 2015 it became clear to me that I'm making the mistakes over and over.

If you're really new to competitive programming, someone who doesn't really care much about the result, or someone who's trained since the age of 6 you probably won't relate to these issues, but after I've done some research I realized that this is more common than I expected. The same pattern happened to me every time: I had the right ideas, I got WA on my first submission, I panicked and then my brain basically stopped working (and of course all the known symptoms of the fight or flight state).

I remember talking to someone after day 2 in IOI 2014, he told me: "When I read the problems, my brain stopped working I didn't even understand them, after the contest I read them again and came up with 243 points worth solutions". And his solutions were very neat and differ to the tutorials that were given to us after the contest.

So the point that I'm trying to make is: If I and everybody who suffers from the same problem, could solve problems during a competition as big as IOI with the same level of problem solving skill we usually demonstrate in any other environment, our results would differ greatly.

Have you ever had those issues? Did you manage to fix them?

Also in case of IOI-like competitions, what is your general strategy?

UPD: I got a bronze medal in IOI, the advice bellow is really helpful

Read more »

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

By Alex7, 4 years ago, In English,

Where can I find IOI-Style problems??

Read more »

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

By Alex7, 5 years ago, In English,

I was just curious is there a codeforces Grandmaster who is also a chess Grandmaster ??

Read more »

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