### meret's blog

By meret, 10 years ago, ,
Let me warmly welcome you to Codeforces Beta Round #11. I am the main problemsetter for this contest. I hope you'll have fun solving the prepared tasks :-)

Thanks to Mike Mirzayanov for making this possible and to Ania Piekarska for testing the problems.

Good luck,
Jakub Pachocki
Announcement of Codeforces Beta Round #11

• +30

 10 years ago, # |   +13 Thanks in advance to Jakub for the prepared problems and thanks Julia for translating of everything that it was possible to translate. =)
•  10 years ago, # ^ |   +1 ))) That was not me, who translated the problems this time. They were originally in English, and Mike translated them into Russian ;-) I have nothing to do with the coming contest. But thank you anyway for being so kind )))
•  10 years ago, # ^ |   -6 I guess that they are in English in original this time. =)
•  10 years ago, # ^ |   0 ohGods! minus 2, for what??
 10 years ago, # |   +1 Thanks for arranging this event.
•  10 years ago, # ^ |   +6 Better to thank after the round... :)
 10 years ago, # |   0 Thanks for the round!I really liked problem E. I haven't solved it and maybe even far from complete solution yet, but solving it was very interesting.
•  10 years ago, # ^ |   +1 Problem B is wonderful :)
•  10 years ago, # ^ |   0 I wonder what was your problem with B that leaded to so many incorrect attempts.
•  10 years ago, # ^ |   0 I'd tried to know what is 4th test by debug-submits. When I knew it, I'd tried to know what is correct answer for it. It takes about 15 submits.
•  4 years ago, # ^ |   0 after 6 years of you comment i want to said to you that i facing the same problem :D
•  6 months ago, # ^ | ← Rev. 2 →   0 Can you explain how to solve B? I saw people using logic while (sum
 10 years ago, # |   0 Ouch! Not being able to read bold text correctly for 40 minutes is something I experienced for the first time.
 10 years ago, # |   +12 Problem E is very nice :) I've got it accepted 3 minutes too late. The final solution is really short and cute, but it took a long time to get to.
•  10 years ago, # ^ |   0 About other problems: I believe problems B and D were too well-known :(
•  10 years ago, # ^ |   0 I invented B, D and E by myself (the other tasks were Mike's), so I'm surprised to hear B was well-known. As for D, it does look a bit classic, but I've never personally seen it in any contest, and I figured it requires a nice enough idea to deserve a place in the contest :)
•  10 years ago, # ^ |   0 With the idea being?I'm trying to find previous occurrences of B.
•  10 years ago, # ^ |   +1 Finding all cycles containing a vertex v in O(2^n * n^2), then removing v from the graph and repeating, so that the total number of operations is about is 2^n * n^2 + 2^(n - 1) * n^2 +... = O(2^n * n^2), instead of O(2^n * n^3) achieved by a simple DP approach.
•  10 years ago, # ^ |   +2 Oh yeah, that's a good point indeed. I take my words about D back :)
•  10 years ago, # ^ |   0 can you give some insight for how to solve E?  Thanks.
•  4 years ago, # ^ |   0 There seems to be no editorial for this round or description of how to do this problem, so I will post my solution here. SolutionMy solution involved adding X's so that every L and R in the original string was correct (if a character was bad I would add an X right before it). However, sometimes it is suboptimal to add this many. If I added two X's, and there was exactly one L or R between them, then removing them removes two bad characters (those X's), but changes one good character (the one between them) to a bad character, and leaves the rest of the string unaffected, which is a net decrease by one for both correct and incorrect characters, and this is a good move to make if the answer is above 50%. This can be done by just looking through the list of positions where I added X's, with a few extra checks to ensure that there are never two of the same step adjacent to each other. Code
•  18 months ago, # ^ |   -6 does petr reply only to red coders ?
•  18 months ago, # ^ |   0
•  18 months ago, # ^ |   0 but its very rare...
•  10 years ago, # ^ |   +1 Perhaps many people found A140358.
•  10 years ago, # ^ |   0 Hmm. Conjecture? Interesting... That's why I didn't cope to prove the idea during the contest :)
•  10 years ago, # ^ |   0 Yes ;-)
•  10 years ago, # ^ |   +2 I'm surprised it's just a conjencture on OEIS. The proof goes as follows:Let n be a positive integer. Consider any k such that 1 + 2 + ... + k >= n. Then n is reachable in k jumps if there is a subset A of {1, 2, ..., k}, such that when we make all jumps from A go left and all jumps not from A go right, we reach n. This is equivalent to k(k + 1)/2 - 2 * (sum of numbers in A) = n. It's very easy to prove that the sum of numbers in A can be any number between 0 and k(k + 1)/2, so it's possible to reach n iff the difference between k(k + 1)/2 and n is even.
•  10 years ago, # ^ |   0 Nice Problem indeed.
 10 years ago, # |   +6 Where can I read about problems like D? (Counting cycles, Hamiltonian paths etc)
•  10 years ago, # ^ |   0 Rus:  где можно почитать про число гамильтоновых циклов и путей?
•  10 years ago, # ^ |   +3 нашел что то отдаленно напоминающееhttp://informatics.mccme.ru/moodle/mod/statements/view3.php?id=477&chapterid=77и разбор:http://informatics.mccme.ru/moodle/mod/book/view.php?id=489а вообще весьма странно что подобные вещи плохо в инете находятся... или я плохо ищу))
•  10 years ago, # ^ |   +3 и все таки не могу найти что почитать на эту тему оО только разве что порешать.самому что ли сделать доброе дело - накатать статью :D (а если потом ее кто нибудь переведет на английский - будет совсем замечательно)
•  10 years ago, # ^ |   0 хороша идея!)
 10 years ago, # |   +1 I have problem in my head or codeforce has problem in its head....my contest code of B got WA in test 4 using scanf and printfbut in practice same code got AC using cin and cout?is there any explanation anyone can give?here is my WA in test 4 codehttp://pastebin.com/cbBH5nzzif u replace scanf("%lld",&num)==1 with cin>>num and printf("%lld\n",i) with cout<
•  10 years ago, # ^ |   0 As you can see there is an 2005 MSVS compiler and it doesn't work with %lld, but with %I64d!Or you can just make all variable int (it's enough) and use %d.I tested it just now.
•  10 years ago, # ^ |   0 I'm wrong. (c)From 2005 version VS supports both %I64d and %lld.
•  10 years ago, # ^ |   0 Try to replace scanf("%lld",&num) with scanf("%I64d",&num) and printf("%lld\n",i) with printf("%I64d\n",i).
•  10 years ago, # ^ |   0 Beaten :)
•  10 years ago, # ^ |   0 I submited my code in GNU C++,,GNU supports long long ,right?
•  10 years ago, # ^ |   0 As you see, no.
•  10 years ago, # ^ |   0 then its a shame to me...I have been coding knowing that GNU C++ supports long long ...I haven't faced any problem except this.even in my windows pc GNU C++ compiler(CodeBlocks) supports long long well....If codeforce's GNU C++ doesn't support long long ,,then I have nothing to say. :)
•  10 years ago, # ^ |   0 Codeforces uses MinGW, which DOES support long long, but DOES NOT support %lld. %I64d should be used instead. Or you can simply submit using MSVC compiler, in most cases it will be fine.
•  10 years ago, # ^ |   0 Thanx. this thing really pissed me off in the contest time. I should have known it earlier.
•  10 years ago, # ^ |   0 But you wouldn't forget it in future. =)
•  10 years ago, # ^ |   +5 AFAIK, gcc actually uses the OS's C library to make the call to printf. That's why  on Windows the format for long long is %I64d because the Windows C library uses that format, even though the compiler is gcc.
•  10 years ago, # ^ |   0 If anyone wants to see my both code but cant see from the provided link..I will paste it here.
•  10 years ago, # ^ |   0 Btw 2008 VS works with %lld. So don't be uncertain.
•  10 years ago, # ^ |   0 yah,,
 10 years ago, # |   +11 Do all hadn't a respond from the site at the start of a contest?
•  10 years ago, # ^ |   +6 I couldn't open any page for about 5 minutes, but judging by the standings page, many people submitted A at 0:03-0:04...
•  10 years ago, # ^ |   0 It's strange.
•  10 years ago, # ^ |   0 Same problem here.  But I guess that doesn't really make a big difference.
•  10 years ago, # ^ |   +1 I think it does make a big difference. If you lost 5 minutes in the beginning and solved N problems then you'll get 5*N extra penalty time. If I could access the site immediately from the beginning I'd be 1 or 2 positions higher in the ranklist, and will probably be red today.
 10 years ago, # |   +8 Thank you, Jakub, for interesting problems. It is an essential aid for Codeforces. I'm very glad to work with you.
 10 years ago, # |   0 Does anyone knows why I'm getting "Denial of judgement" ? :)
 10 years ago, # |   0 Does anybody want to share the solution of problem D and E?
 10 years ago, # |   +3 Thanks for the problems, but I'd like to pay attention to some inaccuracies in them. 1. B: "He can go either left or right with each jump." One may think that Jack can go either left or right from his point of view. For example, going left and then right would move him (0,0) -> (-1,0) -> (-1, 1). That will make the problem two-dimensional and thus much more complicated. A friend of mine spent much time until he realized his mistake. It would be better to write something like "He can go either back or forth with each jump."2. C. What is a diagonal of a non-square matrix? It is a rarely used term, at least I've hardly found a mention of it only on the second page of Google's result. It would be much better if the definition of this term was given in the problem. It requires only a sentence or two, but clarifies the problem.3. C. "a square must contain at least one 1 and can't touch (by side or corner) any foreign 1". What does "foreign" mean here? Is it a "1" which doesn't belong to this square or to any square? 4. Also "a square must contain at least one 1", but earlier "A square should be at least 2×2". I understand, that there is no contradiction, but why increasing the confusion?Thanks.
•  10 years ago, # ^ |   0 I think the authors should explain the examples for all the problems in the contest. For example: the authors should explain why the result is 1 for the 1st  test case, 2 for the 2nd test case... for the problem C.
•  10 years ago, # ^ |   0 Look, there are 3 squares in the first example, but two of them (2x2 in the left bottom corner and big square of type 2) are "touching" each other, so they don't count. There is also a single "1" in the top right corner, but  "A square should be at least 2×2". So only one remains - the 2x2 square of type 1, which is located in the bottom right corner of the matrix.As for the 2nd test case in the 1st example, there are 4 squares, but two of them are touching each other, so the answer is only two small squares, which are located inside the big square.But it took much time and even a discussion with my friend to explain these examples. The authors should have left some comments on them.
•  10 years ago, # ^ |   0 Look, there are 3 squares in the first example, but two of them (2x2 in the left bottom corner and big square of type 2) are "touching" each other, so they don't count. There is also a single "1" in the top right corner, but  "A square should be at least 2×2". So only one remains - the 2x2 square of type 1, which is located in the bottom right corner of the matrix.As for the 2nd test case in the 1st example, there are 4 squares, but two of them are touching each other, so the answer is only two small squares, which are located inside the big square.But it took much time and even a discussion with my friend to explain these examples. The authors should have left some comments on them.
•  10 years ago, # ^ |   0 Sorry for duplicate comment. It is a bug of the site.
•  10 years ago, # ^ |   0 You mean explain withit problem statement?If yes, I'll agree with you.
•  10 years ago, # ^ |   +1 yes, this is exact what i want. Hope the problem setter will do it next contest.
 10 years ago, # |   0 Did anyone solve problem B using DP solution?I want to do but I can't...I hope someone show me the code.Thanks.
•  10 years ago, # ^ |   0 I don't know a DP solution.For example. If you want to reach 10^9 position, in some you'll be near it. Let it be a 10^8 position (of course the real position place will be close to 10^9, you can prove it yourself). So we need to compute 10^8 cells. It takes more than 1 sec time. :(And you need about 120 MB to store billion length bool array.Maybe there is a much better DP solution, and maybe even it got AC, but i solved that with little formula and very little bruteforce (most of participants use only brute).If you request a code you can get it there - http://codeforces.ru/contest/11/status/B?order=BY_ARRIVED_ASC
•  6 years ago, # ^ |   0 I am new to programming. The people have solved problem D quite easily as it is quite trivial for them. I am not able to understand how they are solving using DP. what is the subproblem. I have spent 3-4 days trying to understand the solutions but no success. Can anyone help ? I will be grateful for the same
•  6 years ago, # ^ |   -8 The comment removed because of Codeforces rules violation
 » 6 years ago, # |   0 After participating in the contest,I learnt I also had had so much to learn since the day.
 » 4 years ago, # |   0 This blog link explains problem 11-D.http://codeforces.com/blog/entry/337
•  » » 18 months ago, # ^ |   0 thanks!
 » 6 months ago, # |   0 Can someone explain how to solve B? I saw people using logic while (sum