ADJA's blog

Codeforces Round #294 (Div. 2)
By ADJA, 10 years ago, translation, In English

Hello, Codeforces!

My name is Adilet Zhaxybay, and together with Bekzhan Kassenov (BekzhanKassenov) we are authors of Codeforces #294, which will be held on 28th of February at 16:00 MSK. This is our first Codeforces round and we are happy to invite all of you to participate in it. The round will be rated for the second division, however, participants from the first division can, as usually, participate in it unofficially.

As far as we know, it is the first Codeforces round, which was completely prepared by the authors from Kazakhstan. We are very honored by this fact and hope that everything will go great. We are encouraging other participants from our country to join us — I am sure, that you can prepare a lot of very nice problems. Preparing Codeforces round is possible ;)

We want to thank all the people, who helped us to prepare the contest: Max Akhmedov (Zlobober), who helped us with the problems, Nurlan Kanapin (kt-9) and Mansur Kutybaev (mexmans), who tested the round, and Maria Belova (Delinur), who translated problem statements.

Also we want to say great thanks to Mike Mirzayanov (MikeMirzayanov) for creating Codeforces and Polygon. We want to congratulate Codeforces with its fifth anniversary. We, authors of the round, were very lucky to start competitive programming at the time, when Codeforces already existed, and it helped us really a lot!

We love, when authors of the round write a bit about themselves (we encourage everybody to do so) — this helps to feel that there are real people behind the problems. Thus, we will write a bit about ourselves. We are students from Nazarbayev University (nu.edu.kz). NU is a new university with English as a language of teaching, which is located in the capital of Kazakhstan, Astana. Our university participates in ACM-ICPC only from 2012, but the team from NU already qualified to World Finals twice — in 2014 and 2015. We hope that we will do only better in the future!

Good luck to all!

UPD Score distribution will be standard (500 — 1000 — 1500 — 2000 — 2500)

UPD2 Editorial is available here

Congratulations to winners!

  1. AkashiSeijuro

  2. fmzbtf937

  3. mxh3777

  4. IGandWFin2019

  5. ruozha2 & i_hate_t0nzuk

Round is over, thanks to everybody, who took part in it!

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

Comments Comments (128)
| Write comment?
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Hope for finally become blue :)

→ Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Congrats for being first in country to prepare a codeforces round. Hoping your efforts will inspire many people in your country.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    For the sake of fairness: azizkhan was one of the authors of Codeforces Round #202. We are just first, who prepared complete round.

    → Reply
»
10 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Wahhey, first complete round from my country!

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

This contest overlaps with Challenge24 :(

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +33 Vote: I do not like it

As far as we know, it is the first Codeforces round, which was completely prepared by the authors from Kazakhstan.

I am really sorry bekzhan29)

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Why isn't this page on the frontpage? Isn't this an official contest?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's an official contest. Just appeared on the front page.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

hope we enjoy the problems

→ Reply
»
10 years ago, # |
  Vote: I like it -57 Vote: I do not like it

In this world, winning is everything; winners are validated and losers are denied. Until now, I've never lost at anything, and I won't in the future. Since I always win, I'm always right. If you oppose me... I'll kill you, no matter who you are.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    miay teeworlds?

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Ya, we know that by looking at the time you created your account at.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    teach me how to spout nonsense without getting embarrassed please because the things you just said made laughing a medicine for me =))

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I'm pretty sure everyone is so much concerned with their lives and won't dare to oppose you. But I was just wondering what if the Online Judge oppose you and give you a verdict other than Accepted!

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -32 Vote: I do not like it

      That cant happen because i am always right, i make no mistakes

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I think he is just acting like the character Akashi Seijuro... Those words were all originally from the anime....

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    look for help bro :)

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @Akashi: Sorry but you will loose both in the anime and in div1 soon :)

    → Reply
»
10 years ago, # |
  Vote: I like it -23 Vote: I do not like it

I am ze ghamat very very sorry pictureato bede for yadegari

pls dis like me for kossher haye bala

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wanted to take a walk today. Maybe I will do it tomorrow. Priority has codeforces :P

→ Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Usually I ignore large post, blog and announcement. But this one is so much encouraging that I can't ignore. May be one day I will be an author like you :). Best wishes to you guys.

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I thought contest would be delayed for 10 min, but registrants 4965!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I missed the contest :-(. I thought it was at 16:00 local time.

→ Reply
»
10 years ago, # |
  Vote: I like it +46 Vote: I do not like it

I think problems were easier than standard for a Div. 2 contest IMHO.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Yes... of course that was first contest of ADJA we hope next contest be better :-"

    → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I'm wondering... What's the test case for problem A that got all these hacks?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    People thought knight was K lololol

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    I use something like this: ....K... ........ ........ ........ ........ ........ ........ ........ (the code will fail this test case if they add 1 for 'K' or 'k')

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it 
    mymap['K'] = mymap['k'] = 3; //this case
    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Also some people / not in my room :( / use 9 instead of 8 for Q.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wait... Aren't you supposed to use 9 for Q?

      → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

how to solve E??

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I missed the contest but I guess it's related to LCA.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    Preprocessing: LCA preprocessing and making an array of heights of nodes (h[]), quantities of nodes in the subtrees (sub[]), ancestors of levels 1,2,4,8,16... If we have ancestors of these levels, we can find ancestor of any level with O(log(N)) time.

    Solution: if a==b, the answer is n. Else find LCA(a,b)=c. If heights of a and b are the same, the middle is c. We can find ancestors of a and b that are childs of c (call them e and f), because we know that they are a and b ancestors of the (h[a]-h[c]-1)th level (complexity O(log(N))). Then the answer is n-sub[e]-sub[f]. If heights of a and b are not the same, then either h[a]-h[b] is odd — then answer is 0, or is even — then we know where the middle node e is situated. If its child closer to a or b is f, the answer is sub[e]-sub[f].

    → Reply
»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

C looks easier, than A for me.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do I do E? I know its a tree.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do C problem.I solved it recursively but dont know how to optimize it for large test case .Thanx

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    my solution is to print the minimum of (n+m)/3 and n and m

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Greedily, whichever out of n or m is larger subtract 2 from it and subtract 1 from the other until one of them is smaller than 2 and the other smaller than 1.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Easiest solution i found was:

    Ans=(a+b)/3

    Ans=min(Ans,min(a,b))

    I doubt this tho

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    ans=min(n,m,(n+m)/3) :)

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i did something like this 1+max(solve(n-1,m-2),solve(n-2,m-1));where solve is my function.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Did it work? Looks like exponential time to me. Or n^2 if memorized.

      → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Can anyone tell me how to solve D? I can't wait till Editorial

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Who can say 5 pretest of C?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How is D solved?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    i did this:

    keep this : array[ each partial sum amount ][ each character ] = number of occurences of that character with the amount of partial sum.

    (by partial sum i mean sum of all values from the first to the i'th character) since the amount of partial sum can be large and also negative you need map ( or unordered_map )

    when you want to add a new partial sum you must see how many of the previous partial sum and the current character had occured and add this amount to the ans.

    → Reply
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

what's the meaning of "Validator 'validator.exe' returns exit code 3 [FAIL Expected EOLN (stdin)]" when hack others' code?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think for prob C it will be more challenging if the input range is bigger, something like 0 <= n, m <= 5.10^9. with 10^5, even brute force implementation can pass. But, overall, nice contest!

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    min(n,m,(n+m)/3) is not very challenging even 10^18. if this solution is correct...

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know, but at least brute force implementation will not pass (and maybe can gives more hacks.)

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        let's wait system testing, and look at solutions 1500 score problem.)))

        → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

This is so unfair. They skipped my solution to problem C. It was a super simple 10 line solution. How can it be skipped ? It may be due to coincidence that my solution is similar to someone else since it involved only 3 variables and simple commands!

→ Reply
»
10 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Erm... About problem A...

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for very fast system testing!

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Let's hope for fast rating updates too :D

    UPD. It was very fast :) Thank you!

    → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I don't understand why my submission is not any giving output. For the same case my solution is giving output in my codeblocks.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I don't understand it either. I submitted your code without any modifications and got AC 10086878

    Try to write admins about that.

    → Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Editorial is published here

→ Reply
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

There are a lot of people who unrated joined this contest. I think they are from DIV1... Not fair play

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't have this efficiency in Div. 1 contests :( :-"

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Please explain problem D?

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Speed contest

→ Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

It's another swarm of unrated competitors...

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello programmers! How I an quicly find general parent of two vertex on tree? For O(1) or O(logn) ?

→ Reply
»
10 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Thank you all who participated in the contest! We enjoyed it. Hope you too :)

I have written small blog post about what is like to be problemsetter: link. I will be happy, if this helps you to have a feeling of what is going on behind the scenes.

See you in the next contests ;)

→ Reply
»
10 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Top 8 participants are unranked... Are you shi'in me?

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

Seems like AkashiSeijuro used his Emperor's eye this time...

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice!!! I became purple :P But I'm banging my head: stupid mistake on problem D, not using long long catch me again :(

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    say goodbye to int try typedef long long ll; and use ll everytime !

    → Reply
»
10 years ago, # |
  Vote: I like it +20 Vote: I do not like it

How this submission passed system tests?

Sum of all numbers in first array must be maximum 1e5 * 1e9 = 1e14

1e14 > 2^31-1

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's the same as performing all operations modulo 2^32

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      How about this case:

      3
1000000000 1000000000 147483648
1000000000 147483648
147483648

      that code gives wrong answer. The variables needed to be long long.

      → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

http://codeforces.net/contest/519/submission/10066478

Hi Java fans. Don't forget that it's not right to compare Integers by ==. Use equals instead:)

http://codeforces.net/contest/519/submission/10085682

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

When I submitted my code, the verdict was AC. But when I open my submission page, the verdict has been WA.

my source code is here -> http://codeforces.net/contest/519/submission/10067289

Everything has changed after a few hours. What's the matter with test 6 ?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    When you submit a solution during the contest, it's checked only on a small number of cases (pretests). Only after the contest ended, it's run on a larger number of cases (system tests). Your solution is incorrect because it considers only 4 rows of the chessboard. It passed pretests but failed system tests.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is there a tutorial for this contest? I can't find it. Somebody provides me with the link, please.

→ Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

all unrated guys have won,, u konw what i mean

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you have a seizure when you were writing the second half?

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

English Editorial please.

Need editorial to 5th ques.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for this round. Finally become purple after 15 contests. :)

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Really thank this round, I finally became blue!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could not solve problem C just for missing the line "Furthermore, they agree that the total number of teams should be as much as possible." :( :(

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I mean that is a pretty crucial line, it states the goal of the problem. If after reading a statement you do not know the goal of the problem you should reread statement. Overall I thought it was a very clear description of the problem.

    → Reply