Lakshi4h's blog

By Lakshi4h, history, 3 years ago, In English

I was trying to solve jelly from last year(and this year) practice contest. First 4 subtasks are very easy but i don't have any idea about the last 2 subtasks. Can anyone share their solution.

Thank you in advance.

Current Progress: (if it matters)

Full text and comments »

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

By Lakshi4h, history, 4 years ago, In English

Jack and Jill play a game called Hotter, Colder. Jill has a number between 1 and N, and Jack makes repeated attempts to guess it.

Each of Jack's guesses is a number between 1 and N. In response to each guess, Jill answers hotter, colder or same. For Jack's first guess, Jill answers same. For the remaining guesses Jill answers:

hotter if this guess is closer to Jill's number than his previous guess colder if this guess is farther from Jill's number than his previous guess same if this guess is neither closer to nor further from Jill's number than his previous guess. You are to implement a procedure HC(N) that plays Jack's role. This implementation may repeatedly call Guess(G), with G a number between 1 and N. Guess(G) will return 1 to indicate hotter, -1 to indicate colder or 0 to indicate same. HC(N) must return Jill's number.

Full text and comments »

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

By Lakshi4h, history, 4 years ago, In English

Today I wrote a solution for IOI 2010 Traffic

But It exceeds the memory limit.

code

Graph is a tree and has $$$n$$$ $$$(<1e6)$$$ nodes. Therefore i think the total memory will be

  • $$$n$$$ for array p

  • $$$n$$$ each for s and d arrays

  • $$$2*(n-1)$$$ for adjacency vector

  • $$$2*(n-1)$$$ for map m

Complexity is $$$O(n)$$$

But how does this exceeds 250MB? Can someone point me to my mistake.

Thank you.

Full text and comments »

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

By Lakshi4h, history, 4 years ago, In English

Here's the list of IOI problems from 2006 sorted by their difficulty (average score)

Spoiler

Here's the average score for a single problem per year

Spoiler

Another useful thing will be to classify problems by tags. But i don't think i'm qualified enough to tag problems. So i prepared a google forms so others can contribute. If it doesn't becomes successful i'll try to do it myself and share :D .

Google form

Note: Form is only for a single problem. You can submit another responses again. Please don't spam or provide fake tags.

Full text and comments »

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

By Lakshi4h, history, 4 years ago, In English

This is my code to solve 229B - Планеты

my code

107892710

But it get TLE on test 66. It's just a dijsktra with a simple modification. I can't figure out a way to make this any more faster.

Here's another code i found from top of the standings. It's almost the same as mine but passes in a very small time. I've been comparing two codes but have no idea for a reason for TLE.

2276080

Can someone help me figure out the problem?

Thank you.

Full text and comments »

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

By Lakshi4h, history, 4 years ago, In English

I've been trying to solve this problem for few days now but can't think of a solution.

Here's the statement,

In case you need to read the full statement: Problem Link

What I observed so far:

  • worst case is in the form of $$$a^{1} , a^{2} , a^{3} , ... $$$ for some integer $$$a > 1$$$

  • in the worst case $$$i$$$ th element has $$$i-1$$$ in degree and $$$n-i$$$ out degree (1 based indexing)

That's all :(

I can't even prove that there's a solution for the worst case. Can someone help me solve this?

Thank you in advance

Full text and comments »

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