Блог пользователя kingofnumbers

Автор kingofnumbers, история, 9 лет назад, По-английски

hello guys

I was trying to solve problem EAGLE1 in spoj OJ

the problem gives you a weighted tree and ask you for each node , find farthest node from it

this is very standard dp problem but my code strangely always take runtime error , although I tried different coding styles.

I thought maybe there's something wrong with test cases but I tried to write code that check the validity of test case before processing it but it showed that nothing wrong with the test cases

I'm seeking for help to explain what's happening , here's my code

thank you in advance

Полный текст и комментарии »

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

Автор kingofnumbers, история, 9 лет назад, По-английски

Hello

I have a question that come to my mind but I'm not able to solve it:

Given N , you know there's an array of N integers but you don't know integers of the array , you only know N.

you want to find minimum integer of this array, in order to do that you can ask questions of form: L R

it means what's the maximum number among all integers from index L to R (inclusive)

you will know the index and the value of the maximum integer

in case we can ask O(N) questions then we can query every integer alone and get the minimum one

but is there's any way to know the minimum integer of this array using less than O(N) questions ?

if there's no way how to prove that formally?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

Автор kingofnumbers, история, 9 лет назад, По-английски

sometimes during a contest when I think a problem have tricky test case(s) I go to my room and start searching for solutions which doesn't handle those tricky cases but sometimes after I read about more than 15 codes I still can't find even single solution which doesn't handle one of these tricky cases then I start to think: am I unlucky because I am in a room where all its contestants are very careful for tricky cases?

but then after the contest I discover that all such test cases exist in the pretest so if a solution didn't handle one of them it will not pass the pretests, so I just realized that I wasted my time while reading the solutions.

that's why I want to suggest a new feature in codeforces round rules that makes us able to submit solutions to a problem even after locking it so we can submit solutions that doesn't handle those tricky cases so if it passed then we know those tricky cases doesn't exist in the pretests , ofcourse those submissions doesn't affect our points and only last solution submitted before locking is judged in the system testing.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +78
  • Проголосовать: не нравится

Автор kingofnumbers, 9 лет назад, По-английски

I want help to explain the behavior of this code

this code reads an undirected graph then store list of the edges in list vector, then in the adj vector I store adjacency list of the graph where I actually store pointers to the edges from list vector

but as you can see there's some random big numbers appear in the output but I don't know how, maybe I am making some undefined behavior some where? , any help would be appreciated.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

Автор kingofnumbers, 9 лет назад, По-английски

look at my chart in my profile my rating goes like this

where:

c=number of contests I participate

r=my rating

last three contests which I did , each one of them I thought I can reach red in that contest but my rating end up raised but without reaching red

Полный текст и комментарии »

  • Проголосовать: нравится
  • +26
  • Проголосовать: не нравится

Автор kingofnumbers, 9 лет назад, По-английски

Hello,

Syrian Collegiate Programming Contest 2014 (SCPC) was held as a multisite contest in both Damascus and Latakia between 21st and 23rd of September , I think it's the first ACM contest which take place in two sites in two different cities!

Forty four teams from eleven universities participated in the contest beside three other unofficial teams

I've uploaded the contest to GYM and I invite you to participate in this contest which I choosed this time for it , I hope I chose the time which suits as many coders as possible.

most problems may be easy for yellow and red coders but at least one problem will interest you.

it's the first time that I upload a contest to GYM so I hope everything is technically ok!

if you have coach rights please don't enter the contest before it starts.

By the way, today is the third day of Eid al-adha festival so Happy feast to all Muslims :D

UPD: Contest is finished , thanks for participation and Cogratulations to winners.

problem H is a traditional dynamic programming but allowing negative values tricked a lot of contestants because they didn't initialize the corner values of dp to -INF (i.e dp[i][0]=-INF and dp[0][i]=-INF)

problem I is very simple implementation problem the fault of many participants is not considering the case when there's no 5 different letters in the song.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +43
  • Проголосовать: не нравится

Автор kingofnumbers, 10 лет назад, По-английски

Hello

I would like to know about what is the criteria of choosing the team that will represent your country in IOI and what is the criteria of training students, is programming is studied in high schools in your country and details about this stuff.

I'll start by talking about Olympiad system in Syria:

in Syria there's one organization that is responsible for all science Olympiad (maths, informatics , chemistry , physics , biology) all events for all subjects happens in the same time.

each year there's mainly three events

1- Central national Olympiad (in January of every year):

this is the first step to enter the Olympiad world each student in first year of high school should choose only one subject to participate in, then they do elimination exams, so that the top 5 of every state in Syria is chosen to to participate in "Central national Olympiad", since programming is not teached in high schools the majority of students don't know programming thus, the exams are paper-wise which have many question ans puzzles which needs way of thinking similar to the one in competitive programming , after the top 5 is chosen from each state they are given some lessons about programming to get ready for "Central national Olympiad" that is held in Damascus (capital of Syria) , students have only one month to learn programming before "Central national Olympiad" , only top 10 will be members of "national team" students that fail of being in "national team" in first year of high school have no other chance to join it.

2- Selection contest (in march of every year):

only "national team" members are invited to this contest where top 4 in this contest are chosen to represent Syria in IOI

3- training camp (in June of every year):

all "national team" members are invited to this camp where they stay in Damascus for about 20 days to get training

What about your country?

sorry for my poor English

Полный текст и комментарии »

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

Автор kingofnumbers, 10 лет назад, По-английски

I would like to continue the funny animations started here with funny comments related to programming contests:

When I test my solution at the first time how it will work

When my solution fails on test #134 how do I look like

When I successful hack a solution , How do I feel

When a team at ICPC get AC on a problem on first try how do they feel

When a contest starts how do contestants look like

When my solution gets WA on test #1 , how I feel

When I discover that the algorithm I come up with doesn't suits the problem I'm solving, link

When the problem that I'm solving is actually much harder than expected , link

Полный текст и комментарии »

  • Проголосовать: нравится
  • +437
  • Проголосовать: не нравится

Автор kingofnumbers, 10 лет назад, По-английски

Why didn't they make ICPC challenge in ICPC 2014 like previous years? I think ICPC challenges are great!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +33
  • Проголосовать: не нравится

Автор kingofnumbers, 10 лет назад, По-английски

Hello.

APIO 2014 (Asia-Pacific Informatics Olympiad) will take place in 3-4 may 2014 , I wish good luck to all participants.

there is good news, Georgia, Russia, Tajikistan and Turkmenistan have joined APIO starting from this year, which makes getting a medal more challenging :)

Here is a message from APIO 2014 Host committee to our delegation:

Hello from Kazakhstan! We are proud to host APIO 2014 and already have some information for you. First of all, the olympiad will be hosted by one of the best technical universities in Kazakhstan — Kazakh-British Technical University (http://kbtu.kz). Thanks, KBTU! Secondly, here is the official website: http://olympiads.kz/apio2014 (it's still under construction, but some important information is already available). Thirdly, the competition date is fixed at May 3-4 (full schedule is available on the website). And at last, we have 4 new members in this APIO apart from those who joined at IOI 2013. These are: Georgia, Russia, Tajikistan, Turkmenistan.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +56
  • Проголосовать: не нравится

Автор kingofnumbers, 10 лет назад, По-английски

hello,

recently I started to learn the top down method of splay trees I found this pdf talking about it, I also found this code and I managed to understand it very well.

now I want for each node in splay tree let's say node A to store the number of nodes in its subtree let's call it sum(A), the hard part is to compute sum(A) for each node during top-down splaying since sum(A) depands on the values of sum(L) and sum(R) (where L and R are children of A) so sum values must be computed from bottom to up while the method of splaying is top-down that's my problem.

actually after I learnt top-down method of splaying I want to solve ORDERSET using this method so I need to store sum values for nodes so how it can be done?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

Автор kingofnumbers, 10 лет назад, По-английски

how to find leftmost 1-bit in C++ ?

in other word I want to find biggest k so that 2^k <= N for some given number N

for example if N=10 then k=3

I want an O(1) time and memory solution and also without using built-in functions that may not compile in ALL C++ compilers.

thank you in advance.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

Автор kingofnumbers, 10 лет назад, По-английски

Given coordinates of N points in 2D plane , you have to answer M queries in each query you are given a line (y=mx+p you are given m and p) find how many points of the N points that you are given are located under this line.

a point with coordinate (x0,y0) is located under line if (y0<m*x0+p)

N,M<=100,000

I think this problem is useful in some geometry problems so I want to know how it can be solved.

thank you.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

Автор kingofnumbers, 10 лет назад, По-английски

Please,when you see a spam blog on codeforces, enter this blog then vote it down then exit it this will take less than a minute.

because when a blog gets too many down votes it will disappear from "recent actions" menu (maybe about -16 I'm not sure)

so we can remove spam blogs even when administrators are not online.

thanks .

Полный текст и комментарии »

  • Проголосовать: нравится
  • +94
  • Проголосовать: не нравится

Автор kingofnumbers, 10 лет назад, По-английски

I think codeforces processors become very slower than before and here are some examples:

the code submited today 4764625 and the same code submited long time ago 3804344 ,you can see the big deference in running time

also this linear time code is unexpectedly TLE 4764479

this also O(n) getting TLE 4763637

I would like to know why this happens, thanks.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

Автор kingofnumbers, 11 лет назад, По-английски

if IOI2013 problems were codeforces problems what do think the most appropriate rank for those problems?

in my opinion:


Dreaming: Div1 B/Div2 D

Art Class: Div1 C/Div2 E

Wombats: Div1 D

Cave: Div1 B/Div2 D

Robots: Div1 C/Div2 E

Game: Div1 C/Div2 E


please share your opinion.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

Автор kingofnumbers, 11 лет назад, По-английски

Given a rooted tree with N nodes, nodes numbered from 1 to N node 1 is the root

you have to answer queries , in each query you are given a node in this tree and you should output all id's of all leafs in this node's subtree, each query in one line

example:

    1
   /|\
  2 4 3
   / \
  5   6
 /
7  

queries:

1
5
4
2

output:

2 3 6 7
7
6 7
2

expected time complexity O(N + number of queries + number of integers in output)

expected memory complexity O(N)

thanks for helping me.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

Автор kingofnumbers, 11 лет назад, По-английски

Hello,

this is to remind you by Code Jam Online Round 2 will held tomorrow 14:00 UTC

Good luck.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +64
  • Проголосовать: не нравится

Автор kingofnumbers, 11 лет назад, По-английски

I want to know how solve FLOWERS & FLOWERS2

thanks for helping me.

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор kingofnumbers, 11 лет назад, По-английски

Hi when I was trying to understand the solution for 293E - Close Vertices by reading AC codes.

I was reading this code 3689358 , but I can't understand the way he stores the tree.

for me I usually use adjecency list to store graphs or trees.

can you tell about this way to store the tree.

thanks for helping.

edit: is it Euler tour? if yes how is way that the code build the Euler tour?

Полный текст и комментарии »

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

Автор kingofnumbers, 11 лет назад, По-английски

Hi,

I want to know how to merge two AVL trees where elements of the first tree is smaller than all elements of second AVL tree how can I do that in O(log N) of course preserving the balance factor .

aslo how to split one AVL tree into two AVL trees where elements of the first is less than or equal K and elements of the second AVL tree is bigger than K also with preserving the balance factor.

thanks for helping me.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

Автор kingofnumbers, 11 лет назад, По-английски

APIO 2013 (Asia-Pacific Informatics Olympiad) will take place in 11 may 2013 , I wish good luck to all participants.

here is the official site: http://apio.comp.nus.edu.sg

here is the competition rules: http://apio.comp.nus.edu.sg/APIORules.pdf

Полный текст и комментарии »

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

Автор kingofnumbers, 11 лет назад, По-английски

Hi , where can I find the official solution for all USACO contests from 2002 to 2013 ?

thanks.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

Автор kingofnumbers, 11 лет назад, По-английски

Hi, I read in this article that Matrix chain multiplication problem can be solved with O(N log N) by transforming it into the problem of partitioning a convex polygon into non-intersecting triangles.

but how can this done? do you know the details of O(N log N) solution?

thanks.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

Автор kingofnumbers, 11 лет назад, По-английски

there is two countries A and B, the distance between them is 1200 km.

there is a company in country A wants to transport some goods to country B, so the company decided to hire a number of planes, each plane has a tank with Capacity 60 Liters initially all tanks are full of fuel, one liter of fuel can transport a plane only 10km.

unfortunately, a plane with full tank can fly 600km which is not enough to travel to country B.

a plane can be used to help another plane with fuel , if two planes are in the same point one plane can transfer any number of liters of fuel from its tank to the other plane's tank while they are in air ,take care that all planes must back safety to airport in country A before their tanks is empty, expect one plane should travel to country B.

help the company to find a strategy that transport goods to country B using minimum number of planes since hiring a plane is too expensive.

notes:

1- a plane cannot be used more that once so when a plane back to airport in country A cannot be used again.

2- one plane is enough to hold all goods so only one plane should arrive to country B.

3- if plane2 wants to transfer fuel to plane1 , both plane1 and plane2 need to be in the same distance from country A .

4- tank of a plane cannot hold more than 60 liter at any time

Полный текст и комментарии »

  • Проголосовать: нравится
  • -16
  • Проголосовать: не нравится