GLAYS's blog

By GLAYS, history, 5 weeks ago, In English,

Hello,

I recently found out about Zachtronics.They are basically problem solving games!

You can find some gameplay here.

Those are not free(though they are cheap), and so I'm looking for any other game like them.

I found lots of types by googling; there are:

  • ones that involve code(mostly javascript) to pass levels or defeat some kind of monsters
  • those that are on the browser and just involve some mouse moving
  • multiplayer ones; where you need to beat your opponent as fast as possible(mostly coding stuff too)
  • downloadable ones where you have a character and move objects to solve levels

They all involve some kind of problem solving, and from what I read they are all fun!

So I'm looking for ones to play at the moment and I'm interested to find what you guys tried.

Thanks!

Read more »

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

By GLAYS, history, 7 weeks ago, In English,

Hello!

When I need to stress-test a problem on trees, I usually find a random tree like this:

int n = random(1, 100);
for(int i = 2; i <= n; ++i){
    p = random(1,i - 1);
    addEdge(p, i), addEdge(i, p);
}

As in; to find a random tree of $$$N$$$ nodes, I just find a random sequence $$$P$$$(parents) of length $$$N-1$$$ with each $$$1<=Pi<=i-1$$$ for each $$$2<=i<=N$$$.

And it worked well, or so I believed at least.

But I remember watching an Errichto stream(I think it's the AtCoder DP contest one) where he showed how he stress tests and then said that the previous method only prints a specific kind of trees, and that he recommends using Prüfer Sequences. I kept thinking about why that's true but found no answer online.

Of course, Prüfer Sequences are clearly the best and most trusted choice since it's proved that any sequence represents a unique tree and that any tree can be represented by a sequence(more info here). And though it's not that complicated, I still don't want to keep writing it whenever I need to, unless there's an important difference between the two methods.

So if anyone would enlighten me on the difference if it exists, that would be great :D (It would be good if it's Errichto too xd)

Any other advices/tricks on stress-testing graphs or in general would be awesome!

Thankss ^^

Read more »

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

By GLAYS, 10 months ago, In English,

Hello!

I'm trying to solve problem D.Greedy Game from the SPb SU and SPb AU Contest of Pertozavodsk Winter Training Camp 2016.

Here are the problem statements.

I already searched for any solutions on the internet, I only found this.

The problem with it is that it's in chinese, the translation isn't understandable and I couldn't understand the code.

So can you give me some hints?

What I found so far is that to find the maximal possible sum of values taken by the second player that he can guarantee regardless of the first player’s moves we just have to find the maximal possible sum of values that the second player can take if the first player, when confronted by many items of the same biggest value Ai, picks the one with the biggest Bi value first.

Since that would be the worst case for the second player.

Otherwise all of the approaches I've found are O(n2) ..

Any help is appreciated.

Thanks!

Read more »

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

By GLAYS, history, 16 months ago, In English,

Here is the problem.

So basically you have an array of integers a[] of size n.

n <  = 1e5 and a[i] <  = 215 ( = 3, 2 * 104).

And you're given q <  = 5e4 queries of the form (x, l, r) for which the answer is the maximum value of x xor a[i] for l <  = i <  = r.

The editorial's solution is about persistent segment trees which I know nothing about.Before reading that I was trying to solve it using MO's algorithm + trie which has a complexity of O((n + q) * sqrt(n)) without counting the time to answer a query using the trie.Now q * sqrt(n) is fine but n * sqrt(n) is too much.Because n * sqrt(n) is caused by the movement of r to the right(which can reach n) I thought, is it possible to use the fact that all the numbers are <= 215 to improve the complexity?

If r moves to the right more than 215 times then at least one element is repeated right?

Is it possible to use this(or any other optimization) to get MO's algorithm to pass?

Here is my code.It passes 11 test cases out of 14 and the rest are getting TLE(actually it says segmentation fault but I think it's TLE).

Any other solution is welcome.

Thanks !

Read more »

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

By GLAYS, 17 months ago, In English,

Here is the problem statement.

First of all, I'm writing this because I didn't find the editorial for this round anywhere, or else I wouldn't have.

(I am counting on the fact that the expected average of ratings is the same as the expected sum of ratings divided by the number of ratings, so I'll be looking for the expected sum first.Correct me if I'm wrong.)

Here is my approach; there are two cases: (Let n = ceil(N/R)).

  • N is divisible by R or Elly's rating is in the last N % R ratings.So for each time I take R ratings(n times), I add the sum of them multiplied by 1/R because there's 1/R probability that I'll have any of them in Elly's room, if I don't encounter Elly's rating. Else I just add Elly's rating.Then I just divide this sum by n and return the result.

  • N isn't divisible by R and the last group of ratings we're going to take(N%R ratings) doesn't contain Elly's rating.There's p = (N % R)/R probability that we'll have n ratings in Elly's room, and q = 1-p probability that we'll only have n-1.So I calculate the expected averages in both cases and return avg1 * p + avg2 * q.

For avg1: there's 1/(N % R) probability that I'll take any rating in this last group.So I add their sum divided by N % R to the expected sum I already have(of the last N/R groups) and divide it by n. For avg2: I'm not going to add any other rating from this group so I just divide the sum I already have(from the previous groups) by n-1.

My solution fails on 3 of the 5 examples provided with the statement(+- 3 difference), specifically all the examples of the second case. Here is my code.

Can you help correct my reasoning or just propose another solution?

Thanks.

Read more »

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

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

Hello.

I'm stuck in this problem for a while now.(It reminded me with the "Berzerk" problem here)

To be honest; I never really understood this kind of problems nor did I ever understand why a solution is always possible(When the author says so).

When I think of it(or any similar problem) I always believe that it will go on forever..

Specially when the statement says; "If both the players play clever and cautious(or optimally)..

When I read the examples, an idea crossed my mind; the player will win if and only if he can get to the north-east,north-west,south-east,south-west cell of his opponent's.

However, I don't know whether that is the only possibility.

Please note that I don't need help with the first two subtasks which are: R=2 & C=2 and R <= 100 & C=1.

The real problem is with the other two subtasks: R,C <= 100 and R,C <= 1e9 ...

Any hints?

Thanks!

Read more »

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