mbrc's blog

By mbrc, history, 11 months ago, In English,

According to the blog about languages, the -Xmx option for Java is set to 512M. So consider 1097F - Алексей и телешоу from Hello 2019, with a ML of 256M. In this problem, my submission 47948716 takes > 200M memory. With n = 1e5, q = 1e6, t = 1, x = <cycle through 1 .. n>, v = 1,the code takes ~207M on Custom Test. But by setting -Xmx130M, this still runs on my system in time (without -Xmx it took ~270M on my system). This probably means that Java doesn't garbage collect as it still has memory left.

Also according to the following StackOverflow answer: ...Java will use as much memory as it is allowed to, at which point it will garbage collect. To work around this, you can specify a smaller max heap size in the JVM settings. You do this with the -Xmx setting....

Since Codeforces sets the -Xmx to 512M and many problems have ML 256M, is it possible that a piece of code continues to take up memory (since it can go upto 512M) without garbage collecting, and consequently gets MLE verdict, when it could have actually done with 256M and some garbage collection?

Read more »

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

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

I was trying to solve 618E - Robot Arm from the last contest using 15683254. But (strangely?) I suffer a MLE on (pre)test 5. I thought I was using only static memory (each of the 3 arrays has fixed size), so any memory limit exceed error must occur right on the first test, if it occurs later.

I'm new to Java, so can anyone explain why I'm getting a MLE on #5? Where is the extra memory I'm using being allocated?

Thanks in advance!

Read more »

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

By mbrc, 5 years ago, In English,

I am trying to learn 2D Segment trees, and I'm having problems implementing it. Especially when there are 2 points with same y-coordinate. Actually, the approach is to make a segment tree on the x-coordinates, and for the node with x-range [x1,x2] keep a segment tree with all y such that there exists a point (X,y) with x1<=X<=x2. Now suppose we have to update points and find maximums in a rectangle. So if I have to update point (X,Y), I go to the leaf with range [X,X], update the Y in its segment tree. But if I then come up to the parent, and try to update Y in its seg tree too, then I won't make any difference between two different points in that range with same y-coordinate Y. Please tell me if I'm incorrect, and correct me. And please provide me with a clean implementation of 2D segment trees, if you can.

If you want a clean formulation, here it is:

Given N (N<10^5) points each with an associated value, and Q queries (Q<10^5), each either a query or an update. The update operation gives you x,y,k and asks you to update the value at point (x,y) to k. The query operation gives you x1,y1,x2,y2 and asks you for the maximum in the rectangle (x1,y1)-(x2,y2). The update points are among the initially given points.

Read more »

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

By mbrc, 7 years ago, In English,

Hello!

The problem is about this problem: 239C - Not Wool Sequences :)

I couldn't solve this problem during the contest. So today I decided to look back at the problem once more to see whether I could solve it. But I couldn't and read its editorial.

I denote XOR by

The editorial states that for every sequence a ,

a1, a2, ..., an

we can create a sequence b,

b0, b1, b2, ..., bn

which is defined by :

b0 = 0

and hence

Since

all bi are distinct integers within range 0... 2m - 1 , or something like that.

So we count the number of such b and that is our answer.

Now my question is that, the above reasoning means that there must exist a bijective relationship between all a and all b.

Is it true that for each such a there always exists a unique b ?

I couldn't understand this part so I asked you all about this. Thank you!

Read more »

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

By mbrc, 7 years ago, In English,

Here's a site that has mathematical problems to solve, (many are easy, tough are being added), feature of adding problems, discussing problems and other related material. It also has a Ranklist! Okay..here's the site address MathWizard

Sign up, and have fun. It's being developed rapidly. I'll update this post from time to time to notify of other changes.

I've already told my friends about it, so its not blank atleast.

And, another request, when you sign up, please tell us about yourself, (your name) on the Disqus there.

Tell me about how you liked the site ,here!

Please note the site's address has been changed, to reduce pop-ups. Previous accounts are not destroyed, you'll find them there.

Hitrez,maha1192 and rdik, who had scored points on the previous (old) site... now have their accounts copied in the new site. You may checkout the rank-list now.

I feel the first few problems are computational, but the problems towards the end are better in my opinion. You may try them out.

Thank you!

UPD: A latest submissions list has been added.

UPD: A top 10 list is added.

UPD: A badges feature has been added. Badge qualifications will be detailed on the site shortly.

UPD: Country names feature is up. Please add your country name on the site on the problems page.

UPD: A much needed feature, ie discussions for individual problems, has been now added. You can access it by opening the desired problem and by clicking on the link there.

UPD: MathML (using MathJax) support has been added.

UPD: A problem search facility has been added.

UPD: MathWizard Admin (Problem Setting) Board established. You can also participate, if you wish to contribute good problems!

UPD: Editorial feature added. After solving a problem you'll get the editorial by clicking on the tick mark that appears beside it (provided it has been written). For problem-setters: Please write the editorials for your problems as soon as possible. You can do this, by opening the problem. Then click on the Write/Edit The Editorial option to write/edit the editorial for the problem. :)

UPD: Relative Difficulty Score for problems has been added.

Read more »

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

By mbrc, 7 years ago, In English,

I am a beginner in coding and algorithms. Can anyone recommend me some books to read to improve my skills? Till now, I have only solved 1 Div 2 C problem and no higher. Any good sites for help? I have searched but found none :( . Many thanks in advance!

And ... I can read only english! :)

Read more »

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

By mbrc, 7 years ago, In English,

I am a beginner in algorithms and coding contests. Can anyone tell me how to solve 259E - Little Elephant and LCM. I am completely ignorant of a suitable solution. Please help me by telling me the details. Thanks in advance!

Read more »

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

By mbrc, 7 years ago, In English,

I found a soln. for 253B - Physics Practical which is 2726248 during the contest-it got error for test 14. But on my computer, when I tested the program for test 14 (given there), the answer was correct (the answer was also provided). In custom test, it gave wrong answer, but on my computer it gave correct answer. Why so?

Read more »

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