fresher96's blog

By fresher96, history, 5 years ago, In English

Disclaimer: this blog doesn't have to do anything with competitive programming.

I may have the chance to study in Russia next year. I am willing to pursue a master's degree in big data and data mining. I can apply to most universities like ITMO, MIPT, HSE, Bauman, Innopolis, Saint Petersburg, ...

I want to take your opinion on which universities are best in this case. can you please provide an ordering, or give your advice.

Happy New Year!

Full text and comments »

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

By fresher96, history, 8 years ago, In English

hi all, i have two simple questions if anyone can help.

first, please see this submission 20349642 and press the compare button. it will be compared with this submission 20349625. the code is long so don't be distracted.
what i want to know is why the first code gets AC while the second one gets Time limit exceeded on test 10. i even tested the second submission in gym and it got Time limit exceeded on test 39 (i set the time limit to 30 seconds).
i can't really see where does this huge difference come from.

second, there exists a huge difference between using vectors and static arrays. here, the size of the vector is fixed and i use passing with reference (even that the sizes of the vectors are very small 2×2). so there shouldn't be a big difference with using arrays. when i used the same code with arrays there was about 500 ms difference.
is there something to do that will make vectors faster (like using reserve function for push_back) or one simply should use arrays for a better performance?

thanks in advance. any help is appreciated :)

Full text and comments »

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

By fresher96, 8 years ago, In English

problem

i think the intended solution for this problem is O(n lg^2(n))

i used fenwick tree and two multi sets in each node to represent the number of additions and deletion of each number in the input data. i think the complexity of this solution is O(n lg^2(n)) which is pretty much acceptable by problem constrains. however, this solution gets TL on test #11

link

after seeing other fenwick tree based solutions i noticed that the difference is using one map instead of two multi sets. i rewrote the code and indeed it was accepted!

link

can anybody help me with this issue. i don't know where i have gone wrong. switching set to map reduced a TL to a 420 ms AC solution. any help would be appreciated.

btw, what's the problem with codeforces judging system. it seems to be significantly slow.

Full text and comments »

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

By fresher96, history, 8 years ago, In English

does this equation hold for all positive integers

floor( z / (x*y) ) = floor( floor(z / x) / y )

if so, how to prove it?

i have already tested it on randomly generated numbers. also, i have previously used it in a problem and it worked fine

Full text and comments »

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

By fresher96, history, 9 years ago, In English

can any one see when the next SRM will be held

it's been a long time since the last one (661) :/

Full text and comments »

Tags tc, srms
  • Vote: I like it
  • +36
  • Vote: I do not like it

By fresher96, 9 years ago, In English

hey guys ! i need some tips to organize my methods to study after my little experience in competitive programming, i'm now upon some ways to continue they are just 4 as i think, here they are from the most i follow

  1. watching videos, then solve problems related to the watched video (usually the video refers to some problems at the end)

  2. solving about 100 Div 2-A problem, in case of getting stuck with a problem read the editorial and and if something new is mentioned (data structure, algorithm, ...) go and read about it, then moving to Div 2-B and so on...

  3. reading books, like Competitive Programming 3, and solve some of the listed problems

  4. read editorials & tutorials from here (GYM) or Top Coder or somewhere else, then trying to solve the problems mentioned at the end

and of course once a while participate in contests to keep fit with time pressure these are the methods i follow, now i have a good knowledge in dynamic programming and the basics of graph traversals, i think that's all. because of some problems in Code Forces especially for the last certain rounds i think i'm very weak to come up with a greedy approach so i might start learning greedy by method 1 or start doing method 2.

due to your experience what do you suggest ? or any new ideas ?

any help would be appreciated.

Full text and comments »

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