Swistakk's blog

By Swistakk, history, 3 days ago, In English,

Hey, I recently managed to play with some small magnet balls and created a simple riddle:

https://www.dropbox.com/s/raleq3lsuhjr4pz/Riddle.mp4?dl=0

Question is: how many balls are there?

I didn't do anything sly, interior is filled as tight as it can be. Of course it is rather simple, but I find it entertaining. Please use 'hide' tags for answers.

UPD: Congratulations to pulgares on being first one to give correct answer :)! If you want to read my explanation and additional comment then look at my answer to rng_58's comment.

Read more »

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

By Swistakk, history, 2 months ago, In English,

Hello. I gathered some questions about older (2006-2008) problems. As commonly agreed, if you possibly plan to ever use these problemsets for training then please do not read this blog in order not to spoil valuable problemsets. But if you know these problems/solved them or whatever then maybe you can answer some of them.

Link to past problems is here: https://icpc.baylor.edu/worldfinals/problems

  1. Problem C 2006 "Ars Longa"
    How to solve it? We have an idea how to determine which of these 2 conditions hold: 1) non-static, 2) unstable or stable, however we do not know how to distinguish unstable and stable. Since every rod affects two balls on its ends with opposite forces (parallel to rod) we can create a variable on coefficient how this rod affects balls and create equations for every coordinate of every not glued to floor ball stating that resulting force is 0 and use Gauss to check whether such system has solution. If it has then construction is static. It seems that in order to check stability we should try using force on every ball (in 3 different directions) and check whether system still has solution, but if we are not mistaken this reasoning fails for a case of a cube (with one side lying on floor) with 4 main diagonals. It is stable, but I think there are no good coefficients for rods if we want to neutralize horizontal force applied to one ball. Did we assume wrong physics model? Or did we simply make some silly mistake along the way?

  2. Problem H 2006 "Pockets"
    I think this is algorithmically relatively simple problem, I coded it, but I keep getting WA/RTE and I came to the point when I suspect the test data is wrong. If I get RTE this is because of various asserts I put in my code. I deduced that my code thinks that resulting sheet has width 6 or 7 on test it fails on ejudge (thanks to asserts), but computing that width alone is relatively simple. I stress-tested my solution on many tests and that gave 0 errors, I have read that simple part many times and I see no errors. Is there anyone that got this problem accepted?

  3. Problem H 2007 "Raising the roof"
    I don't how to solve it faster than O(T3) (with significant constant) what clearly would get TLE. Solution in such complexity is pretty straightforward algorithmically, so I won't go into details. I have an idea that might result in faster program, but I don't know if it really does. For every pair of triangles we might compute whether one of them covers another one and in such case create a directed edge between them. Such graph is acyclic, so we can process these triangles in topological order, starting from highest ones. When considering some fixed trinalge in order to compute its visible part it suffices to look at this triangle from above and substract regions that are covered by already processed triangles. When done naively that is too slow, but if we store sum of already processed triangles as some set of boundaries maybe that will speed it up. If it would be allowed to give us many thin triangles such boundary will be of quadratic size, so no improvement is done, but maybe since those triangles have small amount of different vertices (at most V<=300) it is possible to give better bound? Or maybe there is a different approach?

  4. Problem C 2008 "Conveyor Belt"
    I coded simplest possible approach (backtrack considering all possibilities in every step) with some time-heuristics and got OK on my first submission. Then I removed all heuristics and it still gets OK. I can't bound running time by something better than O(n!) (n is up to 20), but I can't also construct a case when it needs a lot of work (worst I came up with was and I think higher constant may be achieved). Both proving better complexity bound than O(n!) and constructing cases worse than O(cn) for some constant c both seem to be challenging problems. Is someone able of doing either of these? Or maybe there is a completely different approach in better complexity (I doubt that)? Or did judges simply pose a problem that they have some solution for that simply empirically runs fast enough on their test data?

Read more »

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

By Swistakk, history, 13 months ago, In English,

Hello. It has proved to be not well known that there is currently going DCJ practice round! Everybody who is going to participate should take a part in it to familiarize with distributed environment! Here it is: https://codejam.withgoogle.com/codejam/contest/6264486/dashboard Info about it was written in a mail which looked like it doesn't contain any interesting info, so probably most users disregarded it and don't know about those rounds. Thanks to zholnin for letting me know!

Read more »

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

By Swistakk, history, 13 months ago, In English,

I have observed that many topics definitely not violating rules are disappearing from Codeforces. Examples of that are:
1) yesterday's blog with discussion about programming environments and editors (I couldn't even read two replies to my comments which were posted after I fell asleep, because at morning topic was already not existing),
2) "copy" of http://codeforces.com/blog/entry/23612 which I found pretty funny,
3) topic with my comment with >800 upvotes ;__;.
These are just few of them which came to my mind, but that happens definitely too often. What is the reason behind it? Are they disappearing because of nasty CF moderators which simply didn't like them? Or is it because their authors decided to delete them (more likely than previous one :P)? If that is the second case then I think that authors should not be given option to delete their blog entry. Option to change their post (already existing option) sounds much more reasonable and completely sufficient if author wants his post to be no longer visible. When deleting blog entry they delete not only their entry, but also whole discussion which is often much more valuable than entry itself thus deleting input from community and at the same moment cutting vivid discussion.

Read more »

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

By Swistakk, history, 13 months ago, In English,

Hi. Near the Le Meridien hotel (and also probably all around the Phuket) you can meet unfriendly homeless dogs. If you don't want them to attack you, try avoiding them and hold big stone in your hand (to make them afraid of you, not to throw at them :f). One of them bite me yesterday in the leg from behind (2 mins walk from hotel) even though I didn't tease him or anything and I needed to go to hospital to take rabeis and tetanus vaccinations. So don't worry about me, but be careful about yourself, I don't want any of you to experience similar troubles.

Read more »

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

By Swistakk, history, 15 months ago, In English,

Yay, that time has finally come! The list of TopCoder's contests is so long that I am unable to normally enter whichever practice room I want, because corresponding buttons are shown by arena in a place that is not visible on my screen :). For some time just dragging arena to top of screen was doing the job, but it is no longer sufficient :P. Am I the only one facing this issue or maybe it is device-specific or maybe I am just a retard and I am missing some easy solution? In order to enter practice room for SRM 686 I used navigation by arrows, but it is just a temporary hacky workaround.

Read more »

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

By Swistakk, history, 16 months ago, In English,

Hi!
On recent OpenCup — Makoto Soejima Contest 4, problem "Random Walk" was posed. We were requested to determine the expected number of visited cells after n steps of random walk on a plane — in each move from (i, j) we go either to (i+1, j), (i-1, j), (i, j+1) or (i, j-1) — all with prob 1/4. More precisely, we needed to output , where M was some integer. In this problem constraint was n ≤ 5000. Actually, this problem becomes much more interesting if we try to solve it for n ≤ 105 in a reasonable time (assume M = 109 + 7 for simplicity). Can you see the solution (if I'm not mistaken — it exists)?

Read more »

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

By Swistakk, history, 20 months ago, In English,

Qualifcations already happened :). Let's discuss problems.

Read more »

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

By Swistakk, history, 20 months ago, In English,

Yesterday at SRM 670 I got a funny story which I want to describe. During challenge phase I noted that one solution of medium problem in my room uses Floyd-Warshall. I thought "Oh, why haven't I thought about it during coding phase? Much shorter than those DFSes!", but then I noted that unexpectedly this infamous order of loops is not correct. It went like this:

FOR(x, n) FOR(y, n) FOR(z, n) dis[x][y] = min(dis[x][y], dis[x][z] + dis[z][y]);

while everyone should know that FOR(z,n) should be the outer loop, not the inner one. I tried to hack this solution, so I inputted graph 0-3-2-1, however my test was rejected, because problem was about trees and there was a constraint that parent of vertex i should be less than i and I didn't have time to come up with another testcase. Unexpectedly, this solution passed systests! I thought that its author is very lucky. However it turns out that for trees with this constraint this order of loop result in computing correct distances!

What we need to ensure is that we will somehow detect this one particular path during execution of that algorithm. With this order of loops it consecutively tries to compute distances dis[0][0], dis[0][1], ... dis[0][n — 1], dis[1][0], etc. in lexicographical order. Initialization consists of conditions dis[i][i] = 0, dis[x][y] = dis[y][x] = 1 iff <-> x-y is an edge. We will inductively (on lexicographical order) prove that it computes correct distances. Assume that x-y is not an edge.

Consider two cases:

  1. y is not a descendant of x
    Let z be parent of x. We have z < x, so (x, y) > (z, y) (lexorder of pairs), so dis[z][y] was already computed and x-z is an edge, so both dis[x][z] and dis[z][y] are valid values, so we will detect that path when looking at z.
  2. y is descendant of x
    Let z be parent of y. We have z < y, so (x, z) < (x, y), so dis[x][z] was already computed and z-y is an edge, so both dis[x][z] ad dis[z][y] are again valid values and we are done.

Funny how bugged version of Floyd-Warshall turns out to be correct on trees with this weird constraint on parents :P.

Read more »

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

By Swistakk, 2 years ago, In English,

Hi.

As we all know, when hacking, plain black code on a white background written in faint font is shown to us. It is a pain in the insert here your favourite part of body to read such codes, I think that supposed difficulty in hacking shouldn't be telling "1" apart from "l" or coping with tediously looking code. In my opinion syntax should be highlited appropriately and hacking window should be much larger. I think this would be very noticeable for all users of Codeforces and will make hacking much more fun and less repulsive. Do you agree with me in this matter?

Read more »

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

By Swistakk, 2 years ago, In English,

Hi. BOI (Baltic Olympiad in Informatics) will be held on Thursday and Friday. I just learnt that organizers provide possibility of participation in an online mirror of that contest. Enjoy: https://sio2.mimuw.edu.pl/en/c/boi2015-online/dashboard/ !

Read more »

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

By Swistakk, 2 years ago, In English,

Hi. Can someone shed some light on that mysterious mirror? It's in the schedule but there are no other informations in English CF... How it will be conducted, like a normal CF round or some ACM style contest? Can anyone knowing more than I share his knowledge? I guess that this round won't follow typical CF round, so it would be great to know something more and I suppose that our russian colleagues know pretty much.

P.S. When registering I got to know that it will be rated, but before that I didn't know even this.

Read more »

Tags vk, cup
 
 
 
 
  • Vote: I like it  
  • +19
  • Vote: I do not like it  

By Swistakk, 2 years ago, In English,
 
 
 
 
  • Vote: I like it  
  • +95
  • Vote: I do not like it  

By Swistakk, 2 years ago, In English,

Hi. I got a problem with TC Arena and I described it here: http://apps.topcoder.com/forums/?module=Thread&threadID=849024&start=0&mc=1#1991748 but since I need a quick help I decided to put this also here because more people will see this. If somebody could help it would be great.

Read more »

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

By Swistakk, 2 years ago, In English,

Hi. I think that title of that blog entry somehow explains what I want to tell. I just think that since problems point values can be multiplies of 250 now, then dynamic scoring should be adjusted accordingly, so that we get intermediate state 750 between "1000 one AC more -> 500".

Read more »

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

By Swistakk, 3 years ago, In English,

Hi. Today I got an exam on "Algorithms and data structures" for people which learnt sorting month ago and there was a problem that neither me nor marcin_smu and few other good guys didn't solve and I'm interested in a solution, so maybe you can help?

We are given an array of integers a[1..n] and an integer k ≤ n1 / 2 such that at least k different values are present in a. We need to swap some elements so that first k elements are pairwise different, they are sorted in increasing order and everything is changed in a stable way, which means that for a fixed value our changes preserved order among elements within that value. Moreover everything needs to be done inplace, that means we can use at most constant additional memory. Whole algorithms has to run in .

Read more »

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

By Swistakk, 3 years ago, In English,

Hi. In this entry I want to discuss the score distribution and drain of points (by that term I mean how fast points value of problem is becoming smaller) in longer contests (joint ones like #270 or ZeptoLab). In my opinion everything (drain + typical distribution) works fine in regular contests, but not in those longer ones.

Due to standard habits adjusted to regular contests, distribution in longer ones (typically 7 tasks with difficulty similar to Div2A, Div2B, Div1A, ..., Div1E and 2,5/3h) is similar to 500-1000-1500-2000-2500-3000-3500. Also, contests are longer, so task submitted in the end of 3h contest is worth only 30% of its original value (drain is 0,4% of original value with every minute, but resulting in not lower value than 30% of original one, even when wrong submissions are taken into account). Then, having accepted problem worth 3500 pts after 2h and 55 mins without any previous wrong submissions is worth 1050 pts, while D submitted after 0,5h is worth 1320pts — much more than 1050 pts (even after 1h it will still be 1140pts) — it is clearly unreasonable! Then, if someone made a small bug in D or received random TLE, he will likely end up in a very bad position even though he did the hardest problem!

In my opinion, joint contests need special treatment for them to be fair. In my opinion ideal score distribution should be like 250-500-750-1000-1500-2000-2500 and drain should be smaller, scaled in such a way that if someone submits something in the end of contest it is worth 52% of original value (like in regular contests). There is a sufficient number of joint contests to make this issue important (for example — CF #270, MemSQL Round 1, MemSQL Round 2, upcoming Bayan Warmup, ZeptoLab, Rockethon). I hope that proposed solutions are not a problem from technical point of view (at least changing typical distribution should be no problem, adjusting drain may be more complicated).

What do you think about this? Share your opinion.

Read more »

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

By Swistakk, 3 years ago, In English,

I just wanted to share with you that image :P.

Read more »

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

By Swistakk, 3 years ago, In English,

Hi. Both of those great competitions for high school are upcoming, so this may be a good time to discuss about them and probably make some comparisons.

Firstly, some backstory of my experiences (if you will get bored you can jump to next paragraph :P). When I was in high school I was definitely much more mathematician than algorithmist, I was doing math for my whole life but started algorithmics in high school. I considered algo as a very interesting field and devoted it much time, but math was for me more important and I was simply better at it. I took top spots in math contests when I couldn't perform well in any algorithmic contest (it was a very often case for me that I solved problem, but received very little points, because of some bugs, because in POI there was very little feedback). In my last year in high school I managed to qualify to the IMO (it would have been a tragedy for me if I wouldn't have make it) and also to the IOI, which was a big surprise for me. At IMO I did very well in 1st day, but on 2nd day I messed some cases in one problem and got completely stuck in a geometry problem for sth like 3h. Up to high school, I think that I devoted more time to geometry alone than to algorithmics and couldn't solve problem, which was solved by ~100 other contestants. I was really confident about my math skills and I got an impression like I'm surrounded by loads of really outstanding geniuses (not to mention Teodor Von Burg and Jeck Lim :) ). In final result, despite my really good performance on 1st day, I got 25 pts, 64th place and silver medal. In IOI I solved 3 problems and I considered them as really easy, thought that I didn't really do anything smart and even more, I messed up bruteforces to problems on 2nd day, because of some childish problems, which could be solved in a second using valgrind/gdb. I got an impression like there were few smart guys on IOI, but most of those people didn't know really basic stuff. In result I got 360pts, 28th place and silver medal, which was in fact significantly better position than that in IMO, because 28 is much less than 64 and I was just 4/600pts short from gold medal. So comparison of those performances is somehow weird. I was significantly better in math than in algo, on IMO performed rather well (beside receiving 3/7 because of not being careful in functional equation, but that is another long story :P), got stuck on hard problems only and took not that good place, while on IOI I performed not really well, got really stupid bugs, but took much better place. (By the way that is really something weird, but you can go to results of IOI 2012 and find some really outstanding guys, who got really small amount of points, for problem "Rings" which seemed quite easy :P).

As a conclusion, this might cause some negative feedback, since this is algo site not a math one, but I consider IMO as a much bigger deal than IOI and gold medal on IMO as a significantly bigger achievement than gold medal on IOI. Comparing to CF rating system I think that "rating cut-offs" for IOI medals would be something like 1500/1750/2000, while at IMO it would be something like 1700/2000/2300 if we will treat this as a corresponding math skills to algo skills of people with these ratings. Moreover, on IMO there are often some extremely hard problems, and they are always solved by 10-20 people, while in IOI there are some definitely easier problems which are solved by ~6 people (check Last Supper from IOI 2012). One reason of that is that on IOI you also have to code your solution without a single mistake, but either way it is still a big difference. If you're disagreeing with me (or agreeing :) ) I invite you to explain your opinion.

By the way this feeling (in short that IMO >> IOI) was strenghtened by organisations of those events. IMO organisation was really great, we were placed in a really luxury hotel and there were many events like tournaments in a football, table-tennis and many many more, there was a recreation hall where there was a big amount of things to do, karaoke, many games, video games, drums and much more, it is hard to describe how this place was awesome, in short recreation hall = delight overload (and what is most important, I was very surprised by presence of my favorite video game — Pump It Up, you can see me playing here https://fbcdn-sphotos-e-a.akamaihd.net/hphotos-ak-xap1/t1.0-9/46120_4940025175001_299353650_n.jpg :D) and IOI organisation was the exact opposite. There were 2 good things on IOI — problems (which is of course the most important thing) and food, but everything else was really bad. There were very little activities we can do, and we were really often forced to wait for an for nothing. Organizers even managed to make a trip to Venice a horrible one, which is a really hard achievement.

Read more »

Tags imo, ioi
 
 
 
 
  • Vote: I like it  
  • +108
  • Vote: I do not like it  

By Swistakk, 3 years ago, In English,

I wish there was a timeline on CF. If someone forgot to log out, there would be something to troll on his account ;)

Read more »

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

By Swistakk, 3 years ago, In English,

Hi. My post is about problem tags. Usually a sneak peek into them tells us nothing, but sometimes they can spoil us a solution or at least tell us which direction we should follow, which is in my opinion a bad thing. And if tags are visible next to the problem statement it's rather hard not to look at them even once. This happened to me with this problem: http://codeforces.com/contest/286/problem/E where tags really tell much.

Is it possible to make tags default hidden? What do you think about making them hidden?

UPD: Solved. I haven't knew that there is an option in settings which allow me to hide them.

Read more »