hriss95's blog

By hriss95, 11 years ago, In English

Hello to everybody! I've been solving 305B - Цепные дроби and decided to just calculate the fractions. I know it's not the correct way, but I just wanted try in see what's going to happen, because as we all know — when there is precision, it's always interesting :D . So, I wrote a solution and indeed an interesting thing occurred. When I saw the test case on which my solution failed, I immediately copied it and tried it on my computer and it actually produced the correct answer. So I cheated on this test in order to see what's going to happen on the others. The exact same thing happened and that's why I'm writing this post. Does anybody have an idea why this happens. I think that it would be good for all of us who are not familiar with dealing with such situations if we discuss it here

Here is my submission: 4039640

PS: I tried to use some eps values in case of some small error but it still didn't work

Full text and comments »

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

By hriss95, 11 years ago, In English

Hey guys, I've been trying to solve 1076 in Timus and I'm familiar it can be done with Hungarian algorithm or using flows, but can someone explain to me or give me a link(in English preferably) for Hungarian algorithm with O(n^3) complexity. And also, can someone tell me how to transform this problem to a flow problem. I would be very thankful if there is any response :)

Full text and comments »

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

By hriss95, 11 years ago, In English

Hey guys, I've been solving this problem for a while but I still can't figure it out completely. So all we have given is the sum of the digits of a K-digit number and we have to find the smallest such number which when multiplied by D is a new number with sum of digits P. So the input is K,S,P,D where S is the sum of the digits of the number we are searching for. We have to print the smallest such number or print that there is no such number at all

Edit: Forgot to say that K is up to 100 and 1<=D<=9

Full text and comments »

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

By hriss95, 11 years ago, In English

Hi guys, I've encountered an interesting problem. We are given a tree with N vertices and with its edges. All edges are with length 1 and we need to find for every edge the sum of the lengths of all paths in the tree that go through this edge. As you probably assume N can be large so N^2 is not good enough.

Full text and comments »

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

By hriss95, 11 years ago, In English

Hey guys, I have been solving this simple on first thoughts problem. I have been learning segment trees and I have some issues solving this:

We have an array of elements which are all 0 at first. Than we have 2 operations:

1) get sum f(l,r) of elements a[l], a[l+1], .... a[r-1], a[r]

2) change all elements in the interval L to R by value V

So I have solved the problem when the second operation is changing value of 1 element but when it is a range I have difficulties implementing that. So I hope some of you who are into segment trees will find that interesting and will be willing to help :)

Full text and comments »

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

By hriss95, 11 years ago, In English

Hey guys, I have ran across a very interesting geometry problem(at least for me). However, I am not that good at geometry and I want to ask for some help!

So the statement is the following:

We have N squares in the xy-plane given by their left bottom and right top corners. We have to count the number of visible and partially visible squares looking from the point (0,0). A square is visible(the same is for partially visible) if at least one of its segments is visible. A segment AB is visible from point O if there are no other points in the triangle OAB. So you can easily deduct that a segment is partially visible if some part of that segment is visible. Note that if a segment is visible it is partially visible too! So, anyways, I hope the problem will be interesting to solve for those have an idea and thank you in advance for your help! PS: I have an idea for full visibility but not for partial one.

Let's just give you some restrictions: N<=1000 and all coordinates given are integers and are smaller than 30 000

Full text and comments »

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

By hriss95, 11 years ago, In English

Hey guys, do you know if there is any memory limit for the hacks' size. I am asking this because during contest #149 I tried to hack a solution which used an array of 10^4 elements while the problem's restrictions showed that there can be up to 10^5 numbers which have to be stored. So, of course I decided to hack the solution, but I was unhappy to see that my hack couldn't be processed and I should try again. I tried several times uploading the file or directly copying the data, but I would always get the same answer. My test was with 20001 rows. Later I saw that this solution had run-time error. I was upset to see that. Actually it doesn't matter so much because I joined this website to learn and practice, but I am just eager to know why this happened to me. I would be grateful if there is someone who can explain :) Thank you in advance guys :)

Full text and comments »

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