nitesh_gupta's blog

By nitesh_gupta, 13 days ago, In English,

Hello Everyone!

I would like to invite you to CodeCraft-19, which is a part of Felicity, the annual techno-cultural fest of IIIT Hyderabad. It will take place on Feb/03/2019 18:35 (Moscow time).

The round will be rated for Div 2 participants (whose ratings are lower than 2100). As usual, participants from the first division can participate in the contest out of the competition. You will be given 5 problems, all of which are based on the theme of our fest, "Superheroes".

I would like to thank the CodeCraft team -- nir123, additya1998, devanshg27, gaurav172, night_fury208, shaanknight, psaini, sharmaritvik60, swetanjal and vivace_jr -- for helping in preparation of the problemset. I would also like to thank KAN and 300iq for round coordination, osaaateiasavtnl., Aleks5d and mohammedehab2002 for testing the round and MikeMirzayanov for the great Codeforces and Polygon platforms.

Following the convention, score distribution will be announced shortly before the contest.

Good luck to all the participants!

UPD1: 500-1000-1500-2000-2500

UPD2 Editorial is published! We sincerely apologize for the weak pretests in B and for the difficulty gap from C to D which turned out to be harder than what we expected.

UPD3 Congratulations to the winners!

  1. prodakcin

  2. fastfurioustransform

  3. yww_AFO

  4. Mindstorm

  5. ThankGodItsFriday

  6. Issh

  7. hfctf0210

  8. Y.nnnnnnn

  9. Choopa_choops

  10. EtherLand

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

»
13 days ago, # |
  Vote: I like it +4 Vote: I do not like it

Auto comment: topic has been updated by nitesh_gupta (previous revision, new revision, compare).

»
13 days ago, # |
  Vote: I like it +12 Vote: I do not like it

Should we expect an interactive problem?

»
13 days ago, # |
  Vote: I like it -7 Vote: I do not like it

Just curious. Why not div1 this time?

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it +61 Vote: I do not like it

    There's less number of people who want to set problems for Div. 1 because they're harder.

»
13 days ago, # |
Rev. 2   Vote: I like it +52 Vote: I do not like it

Wishing everyone high ratings.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I like when people put up handle like these lol.

»
13 days ago, # |
  Vote: I like it +62 Vote: I do not like it

Some previous editions of CodeCraft:

  1. CodeCraft-18

  2. CodeCraft-17

  3. CodeCraft-16

  4. CodeCraft-15

»
13 days ago, # |
  Vote: I like it -39 Vote: I do not like it

Indian round?

»
13 days ago, # |
  Vote: I like it +2 Vote: I do not like it

TShirt? :/

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +164 Vote: I do not like it

    Prizes are not allowed for Div2 contests as it may lead to fake accounts by Div1 users.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      aryanc403 surely meant overall winners rather than Div 2 winners. There is no incentive for fake accounts in that case.

»
13 days ago, # |
  Vote: I like it -6 Vote: I do not like it

Good luck for all participants.

»
13 days ago, # |
  Vote: I like it +18 Vote: I do not like it

Maybe this contest is lucky for me to become pupil

»
13 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Hope this contest should not be unrated

»
13 days ago, # |
  Vote: I like it +36 Vote: I do not like it

Expect numerous hacks like last time.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I feel sorry for all the hacks, but I at least I can say I warned you beforehand.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

GL & HR Everyone.

»
12 days ago, # |
  Vote: I like it -10 Vote: I do not like it

you guys are copying minecraft

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Mancity & arsenal or codeforces :'(

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to be blue but it will never happen.

»
12 days ago, # |
  Vote: I like it +4 Vote: I do not like it

Were there alot of hacks last time?-

»
12 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Hope, problems have harder pretests to prevent so many hacks like the previous year!

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    The pretests are quite weak, and it seems there are more hacks than last year :C

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How long will contest held??? 2 hour or 2.5 hour ?? not mentioned in post.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

10 writers are here.

Hope to see a good contest.

»
12 days ago, # |
  Vote: I like it +22 Vote: I do not like it

Hope contest will be beautiful as it's id.
https://codeforces.com/contests/1111

»
12 days ago, # |
  Vote: I like it +3 Vote: I do not like it

contest 1111. It's really a nice number. woof woof woof.

比赛1111 这是一个非常美妙的数字 汪汪汪

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I hoped that there would be a real Lunor Year contest tomorrow... 我曾经希望明天会有一场除夕赛。。。

»
12 days ago, # |
  Vote: I like it +97 Vote: I do not like it

"Jarvis has to tell Iron Man the number of distinct colony arrangements he can create from the original one using his powers such that all villains having the same type as those originally living in x-th hole or y-th hole live in the same half and the Iron Man can destroy that colony arrangement."

This run on sentence is murdering my brain.

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

After doing ABC and not finding out the reason why D is failing, all I can do is my part

/ ___| _   _| |__  ___  ___ _ __(_) |__   ___  | |_ ___  
\___ \| | | | '_ \/ __|/ __| '__| | '_ \ / _ \ | __/ _ \ 
 ___) | |_| | |_) \__ \ (__| |  | | |_) |  __/ | || (_) |
|____/ \__,_|_.__/|___/\___|_|  |_|_.__/ \___|  \__\___/ 
                                                         
 ____                  _ _            _      
|  _ \ _____      ____| (_) ___ _ __ (_) ___ 
| |_) / _ \ \ /\ / / _` | |/ _ \ '_ \| |/ _ \
|  __/  __/\ V  V / (_| | |  __/ |_) | |  __/
|_|   \___| \_/\_/ \__,_|_|\___| .__/|_|\___|

»
12 days ago, # |
  Vote: I like it -56 Vote: I do not like it

I vote for unrated

»
12 days ago, # |
  Vote: I like it -53 Vote: I do not like it

Codecraft is one of the best contest created by India. It has a lot of learning stuff.

»
12 days ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

It's so nice to watch the solution go through 30 tests in a row in C

»
12 days ago, # |
  Vote: I like it +15 Vote: I do not like it

shit contest kys.

»
12 days ago, # |
  Vote: I like it +28 Vote: I do not like it

make it unrated or die

»
12 days ago, # |
Rev. 2   Vote: I like it +56 Vote: I do not like it

worst constest,shit pretest ,more than half of B'solutions in my room fail with the same testcase. pd: my code alse fail in that testcase :(

»
12 days ago, # |
  Vote: I like it +34 Vote: I do not like it

Is it HackForces?

»
12 days ago, # |
  Vote: I like it +58 Vote: I do not like it

Hackforces Round #537

»
12 days ago, # |
  Vote: I like it +10 Vote: I do not like it

I always wonder why 'Codecraft' is challenging every year. Each year you get to see challenging problems on some particular theme. I am sure we'll find some nice stuff to learn from its editorial too.

»
12 days ago, # |
Rev. 2   Vote: I like it -86 Vote: I do not like it

lol how did you manage to fail A and B? noobs

»
12 days ago, # |
  Vote: I like it +200 Vote: I do not like it

»
12 days ago, # |
  Vote: I like it +12 Vote: I do not like it

HackCraft-19

»
12 days ago, # |
  Vote: I like it +4 Vote: I do not like it

What is Test 6 of Prob C?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It's a test where probably there are one or more avengers on the same position. Think if your code works when you have duplicates.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    More than one stay in one place :) Lost 50 mins for this.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please share your approach?

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Reccurence.

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          will it not time out?

          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I think not time out...

            • »
              »
              »
              »
              »
              »
              »
              12 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              if possible can you please suggest a counter case for this

              • »
                »
                »
                »
                »
                »
                »
                »
                12 days ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

                Reccurence should work if you cut it immiedietly after current interval contains 0 avengers(result is A then).

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This test helped me

    1 2 1 2
    1 1
    Ans: 5
    
»
12 days ago, # |
  Vote: I like it +87 Vote: I do not like it

This round was so weird...

»
12 days ago, # |
  Vote: I like it +37 Vote: I do not like it

so weak tests...

»
12 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Really liked problem C :) But it was kinda a typing contest though :(

»
12 days ago, # |
Rev. 2   Vote: I like it +68 Vote: I do not like it

Classic shitty round

»
12 days ago, # |
  Vote: I like it +10 Vote: I do not like it

how to solve Problem D

»
12 days ago, # |
  Vote: I like it +71 Vote: I do not like it

Personally I dislike this contest.

Codecraft in two most recent years have been plagued with weak pretests, and to top it all off, this year has difficulty spike and incomprehensible + mistakeful statements along.

Well, honestly saying, the reduce from a Div.1+Div.2 combined to a Div.2-only is enough foreseeing a major drawback. Hope to see better attempt next year. ;)

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Why didn't it (49418380) get RE on test a ab ?

»
12 days ago, # |
  Vote: I like it +80 Vote: I do not like it

Problem D statement clearly looks like it is asking about something, while it seems that it is actually asking about an entirely different thing.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lol : )

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I got a solution after some time, then the clarification destroyed it. What was in the clarification wasn't clear in the statement.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      I have just noticed now that there was a clarification. LOL it added an entirely new condition that wasn't mentioned in the statement.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

5 4 2 4 7 9 11 100 problem B test XD sadly mine also failed...

»
12 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Pretests were a disaster! Many sentences in different questions were unclear and tricky, especially B.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What were the hacks for A and B

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    For A I mostly used:

    ab
    ba
    

    For B I only used:

    4 1 3
    1 1 1 1
    
    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks — what were you looking for in the code for those hacks to work?

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        For A it was easy. I just looked at code, quickly understood that someone is only counting occurrences of vowels and consonants and compare them, looked at the statement to make sure that it is wrong and created this simple counter example.

        For B the codes were generally harder to understand but when I found a 5 lines of code solution I realized that many people assumed that its optimally to firstly remove as many smallest elements as possible and then increase the biggest guy. This test is a counter example.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Some tests I used for B:

    3 1 2
    8 9 9
    
    7 1 1
    8 8 8 9 9 9 9
    
    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What did you notice in the solutions that made you know the hack would work?

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The first test I used was to counter a greedy solution, in which if m ≤ n - 1, such solution would delete all m smallest solutions.

        There might be an optimization, in which the deletion will stop when reaching all remaining elements have the same value equal to max. That's when my second test came to the play. ;)

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what is the ans for given 2 cases?

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        For the first test: 9.5000000
        For the second test: 8.7142857

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          what is the solution for B?

          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
            Rev. 2   Vote: I like it +8 Vote: I do not like it

            I approached it with a bruteforce solution ;)

            Obviously, if we're to remove an element, that must be the currently lowest element. We'll take that into regards, and sort the array in an ascending order.

            Now, iterate through all del within range [1, min(n - 1, m)] (inclusive), with del being the number of deleted elements.

            Let's denote sufsum(i) as the sum of i largest elements of the array.

            For each iteration, since we have used del operations as deletion, the number of increasing operation should be min(m - del, (n - delk) -- we'll denote this value as inc.

            Thus, the answer for each iteration would be .

            We'll take the maximum value throughout all iterations as our final answer. ;)

»
12 days ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

LOL I was not aware of the fact that u cannot resubmit a hacked problem :(

»
12 days ago, # |
  Vote: I like it +11 Vote: I do not like it

WORST CONTEST I HAVE EVER SEEN ON CF.

»
12 days ago, # |
  Vote: I like it +13 Vote: I do not like it

HACKERS!!! HACKERS!!! EVERYWHERE xD

»
12 days ago, # |
  Vote: I like it +6 Vote: I do not like it

How do I calculate ((a!)/(b!)) mod p, where p is prime?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    using the fermat's little theorem

    a == a ^ (p — 1) (mod p)

    therefore, we can find the modular inverse by

    a ^ -1 == a ^ (p — 2) (mod p)

    and the result is

    a! / b! == a! * b! ^ (p — 2) (mod p)

    Sorry for poor presentation, I just dun wanna type any latex

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You can use the Fermat-Euler theorem, which shows that xφ(p) - 1 always has remainder 1 when dividing by p, provided that x and p are coprime. φ(p) is Euler's totient of p.

    In this case, since 109 + 7 is a prime number, then φ(109 + 7) = 109 + 6, thus instead of dividing b!, you will multiply , taken modulo of 109 + 7. ;)

»
12 days ago, # |
  Vote: I like it +6 Vote: I do not like it

This is the contest with the weakest pretest I've ever participate

»
12 days ago, # |
  Vote: I like it +3 Vote: I do not like it

mistaken simulation task as greedy / DP for the last two rounds, solves it later than everyone else.

Life is sad

»
12 days ago, # |
  Vote: I like it +8 Vote: I do not like it

difficulty gap again too high ! even many yellow coder solved only 3 and that also in division 2 . division 2 is smoothly becoming div1 .

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Border Test Cases for B on which many solutions will fail ! 5 2 2 7 7 7 7 7

5 2 6 7 7 7 7 7

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Hack for B 5 4 3 2 2 3 3 4 Answer is 3.666666

»
12 days ago, # |
  Vote: I like it +3 Vote: I do not like it

can anyone explain problem B

»
12 days ago, # |
  Vote: I like it +6 Vote: I do not like it

As always, everyone solved the first n problems, and some unicorns solved the rest.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the intended complexity of D is O((52)^2*n) ???

»
12 days ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

So you tell me solving ABC gives you 2nd place, while solving ABCE gives you only 14th place? Not cool.

Edit: A(failed B)CE and 37th place

»
12 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Why didn't this(49426136) O(n2) algo get TL on max test (n = 105, m = 107, ai != aj for all i != j)?

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem D: can anybody tell me why my code is WA?

I used fast binomial coefficient calculation using precalculating factorials ans factorial inverse.

half = n/2, nx = number of char x in string s.

a, b, c, d ... is not targeted chars.

I just calculated 2 * C(h, nx) * C(h-nx, ny) * C(n-nx-ny, a) * C(n-nx-ny-a, b) ...

And I also treated s[x] == s[y]

PLEASE HELP ME!

http://codeforces.com/contest/1111/submission/49432460

»
12 days ago, # |
  Vote: I like it +59 Vote: I do not like it

The worst round ever

»
12 days ago, # |
  Vote: I like it +4 Vote: I do not like it

Hack for B

  • 5 4 3

  • 2 2 3 3 4

  • Ans is 3.666666

»
12 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Hackforces again.

»
12 days ago, # |
  Vote: I like it +88 Vote: I do not like it

When your solution was hacked in the last minutes

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nvm, it happens every time on codeforces

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    mine was after that contest : Prakash_Gatiyala 2019-02-03 20:36:37MSK(21:06:37IST) Announcement Hack announcement ***** Unfortunately, your solution on B has been hacked :(

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When one remember that all what he did in the life is keeping on brushing his teeth.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I hacked someone intentionally in the last minute

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve problem C?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

another hack round :(

»
12 days ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Hack Case for B:

3 3 1

9 9 10

Expected ans: 9.6666

»
12 days ago, # |
  Vote: I like it +58 Vote: I do not like it

Added setters to black list.

»
12 days ago, # |
  Vote: I like it +28 Vote: I do not like it

Y is not a vowel? And the pretests didn't test that??

I liked D/E, but their difficulty was more like div1 D/E :P

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    more than that , i couldn't get any wind until last what d is asking moved to e . get blown . lol : ) btw a good round with huge difficulty gap , even c was not easy

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's in the statement:

    In this problem, we consider the letters 'a', 'e', 'i', 'o' and 'u' to be vowels and all the other letters to be consonants.
    
  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, Y is not a vowel, at least in English. It can sometimes be considered a vowel but it is primarily a consonant. Sure, normally on codeforces 'y' seems to normally be classified as a vowel but it's slightly more correct to have it as just a,e,i,o,u if the statement is in English.

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

"where each position can be occupied by many avengers" i m not able to submit c because i didn't observe it

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In C, I was using feynwick tree to find number less than x(not binary search). Got TL on test case 5. TL seems be too strict.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    So you had a Fenwick tree of size 230? What's odd about that TLEing?

    • »
      »
      »
      12 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I stored map. Link. It was O(log^2(n)).

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your solution looks like it would be O(k·log3(2n)) which is like 2.7e9.

        Solve is called (k·log(2n)) times, and each call (discounting recursion) takes O(log2(2n))

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your method must be wrong, mine passes in 78ms.

»
12 days ago, # |
  Vote: I like it +22 Vote: I do not like it

The most imbalanced round I have ever seen, literally everything depends on speed and hacks.

»
12 days ago, # |
  Vote: I like it +142 Vote: I do not like it

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

1-based indexing caused 2 of my solutions to fail... (for I use C/++)

»
12 days ago, # |
  Vote: I like it +44 Vote: I do not like it

I found statement for D ambiguous.

"Iron Man can destroy a colony only if the colony arrangement is such that all villains of a certain type either live in the first half of the colony or in the second half of the colony."

I think something like this would've been better:

"... only if for every different type of villain, all of its occurrences are either in the first half or the second half of the arrangement."

Not specifying that the property should hold for every type of villain was misleading. I personally misunderstood the problem it until the clarification came up.

  • »
    »
    12 days ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    I second this. The entire contest, I understood the condition as "there exists a certain type, such that all villains of this type either live in the first half or in the second". Unfortunately, the samples did not differentiate between the two cases.

    When the clarification came up, I notified the authors of the possible ambiguity in the original statement. But I was not sure if it was just me or if the statement was indeed unclear. Glad to hear it wasn't just me :)

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, that makes the problem more clear :)

»
12 days ago, # |
  Vote: I like it +208 Vote: I do not like it

»
12 days ago, # |
  Vote: I like it +18 Vote: I do not like it

Really unfair for a guy(say x) who has solved 3 faster than another guy(say y). X and Y lock their solutions but X finds no hack in his room and Y finds a lot of hacks in his room. Its unfair on the side of X though. Pretests should be strong and Questions should be balanced a lot more than what it was today.

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    You are right in that pretests should've been stronger. I don't agree with the rest of your comment. Rooms are selected randomly, so everyone has the same chance of being the lucky Y guy. That's just how CF rounds work, sometimes luck is an important factor as well.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I would prefer getting ratings by solving rather than luck :)

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It sucks when someone beats you out of luck, I've been there too. But that doesn't mean it's unfair. He/she didn't break any rules, so we should accept it, even if it's hard. Moreover, if that lucky guy had been you, you still would've won and gotten your rating.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's how mafia works

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is question c can be done with the help of segment tree and dp with memo???

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I believe the complexity of my submission (in Java) for C is N * K * logK but it got TLE on pretest 8. https://codeforces.com/contest/1111/submission/49423653

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

someone can tell me : Is there any wrong in my way in C please : Firstly i add all the index of a1..ak and sort . After that i check whether i can put a 2^k number among them and sort again Now i can cut the array into many segments and count Number_use A = the number of bit 1 in subtract distance of 2 continuos index // and the rest is use B independently // Tk you so much

»
12 days ago, # |
  Vote: I like it +75 Vote: I do not like it

That jump of difficulty from C to D... It's like playing Dark Soul after learning how to use the computer.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It’s like asking barbarian to play dark souls actually

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what was your solution for D ?

    • »
      »
      »
      12 days ago, # ^ |
      Rev. 2   Vote: I like it +35 Vote: I do not like it

      The answer for each query is , where freqc is the frequency of character c in string s, K is the number of way to split the set of 52 characters into two subset, such that sum frequency of characters in each subset is equal to . If sx ≠ sy, there is an additional condition that sx and sy must belong to the same subset.

      Let fl[c][j] the number of ways to split the set of characters from 1 to c into two subset, such that sum of frequency of the first subset is j.

      If sx = sy, then K is simply fl[c][n / 2].

      Consider the case when sx ≠ sy. We need to precalculate cnt[c1][c2] — the number of way to split the set of characters into two subset when c1 and c2 must come together — then K is equal to cnt[sx][sy].

      Precalculating cnt can be done naively in O(n * ALPHA3) (ALPHA = 52 in this problem), which is not fast enough.

      A faster way to do this is as following:

      Iterate over all c2. For each c2, calculate fr[c][j] — the number of way to split the set of characters from c to ALPHA excluding c2 into two part, such that sum of frequency of first part is j. Then, one can iterate over all c1, combine fl[c1 - 1] and fr[c1 + 1] to get cnt[c1][c2]. Complexity is O(n * ALPHA2).

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Thank you, loved the trick.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        I had a different O(n * α2) solution, but it's more complicated than yours.

        Due to the way the DP is calculated, we can undo any character from the DP. So just calculate the DP in O(n * α), then for all pairs of characters, undo those characters, and check from the resulting DP-array the number of ways to split such that the difference is equal to the sum of their frequencies.

        To undo a character with frequency a, you set DPnew[j - a] = DPold[j] - DPnew[j + a], looping down from j = n, where DP[j] is the number of ways to get a difference of j to the sizes of the sides. We can undo two characters in O(n), so this algorithm is also O(n * α2).

        Code: 49428256. Here DP[n] is zero difference, and less than n is negative difference.

»
12 days ago, # |
  Vote: I like it +66 Vote: I do not like it

Feels like i accidentally enter to Codechef

»
12 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Failed to get up on time and it seems a typing&hack contest... Hope not to FST!!

»
12 days ago, # |
  Vote: I like it -12 Vote: I do not like it

In problem C, manual binary search code gave TLE on pretests while use of upper_bound and lower_bound passed the pretests! Shouldn't happen like that , very sad to see this. :(

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But that is not strange.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Doesn't your comment just reduce to "I wrote binary search incorrectly"?

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      how u solved c ? this was very weired conterst , ur a and b failed st , bcoz of so weak pretest .

      • »
        »
        »
        »
        12 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Well, my A and B in particular failed because of really dumb bugs that I should have caught myself. I won't blame the pretests for my poor implementation mistakes.

        As for C, I did DFS on trie, which afterward I realized was overkill lol.

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          many solved with recursive approach using lower & upper bound .

          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah, I realized that was possible after the contest.

          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            divide and conquer + purning

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      mujhe mat sikha bc

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    My Submission Link

    Please say what could i have done more

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved C using dynamic segment tree. Unfortunately couldn't code before time, as my B got hacked and spent lot of time finding the bug.
Have to wait till system testing to submit.
Can someone tell if dynamic segment tree is fine for AC?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yes, it is. It's unnecessary though. Since there are no updates, you could use a map for storing prefix sums. It's a lot easier to implement and has the same complexity.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it should be fine. But you can notice that you don't need that segment tree because there's no update. You can just do a binary search to find how many elements are there in this segment.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what is dynamic segment tree?

    • »
      »
      »
      12 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Usually in a segment tree, we initialize the whole tree with nearly 4*mx nodes and operate on it. Where mx is the maximum value of a[i].
      But what if a[i] takes values (1 <= a[i] <= 10^9), but there are only 10^5 elements in array a[].
      That time we can use dynamic segment tree.
      We only create a node of the tree if its going to be affected by our update() or range() query. Else we don't require it. Thus making it "dynamic".
      You can check my submission for problem C in today's contest for better idea.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks for explanation, i will try to understand

»
12 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Problem C just minced the JAVA users , as who keeps the TL for a problem with recursion to 1 secs ?

»
12 days ago, # |
  Vote: I like it +19 Vote: I do not like it

Hosted on wrong platform typical codechef contest

»
12 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Has anybody solved C with dynamic segment tree? My submissions got MLE #8

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    My dynamic segment tree got AC.
    I think you are doing too many unnecessary allocation of memory ( i.e ptr = new node(); ).
    Please check my simple implementation.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thank you for your code. Here is my AC submission 49472118. I got rid from the rec function and did all the calculations in the segment tree.

»
12 days ago, # |
  Vote: I like it +65 Vote: I do not like it

Hmmmmmmmmm

»
12 days ago, # |
  Vote: I like it -20 Vote: I do not like it

For like 90% of people y is a vowel and you don't even put a pretest that should get it wrong? Aww come on

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    For A, vowels were given in the statement.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Like 100% of people know how to read a statement.

»
12 days ago, # |
  Vote: I like it +4 Vote: I do not like it

Is Codecraft always like that?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    yup! ! , this yr , more difficult . one ques. why u didn't solved B ?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I doubt there were >EPS different pretests in B

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

POOR CONTEST .....DO YOU WANT TO JUDGE ON THE BASIS OF HACKS ....EXPECTED MUCH MORE FROM IIIT — H

»
12 days ago, # |
Rev. 3   Vote: I like it +81 Vote: I do not like it

Any verdict, system tests.

I doubt if mining bitcoins is a greater waste of electricity than running today's pretests on Codeforces machines.

»
12 days ago, # |
  Vote: I like it -31 Vote: I do not like it

Make this contest unrated, The codeforces site didnt respond for last 4-5 minutes. It was showing Error 403 Forbidden. Was not able to make submission.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, Ironman can destroy the colony if and only if first half or second half is "full of certain types"?

for example "aaabcd" and 'a' is a certain type, we can destroy it. but "aabcde" ans 'a' is a certain type, can we destroy it?

I can't understand problem...

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For the first question: No.

    For the aabcde:

    Yes we can, because all characters of each type lay in one of the two halves:

    Type 'a': each character that equals 'a' is in the first half.

    Type 'b': each character that equals 'b' is in the first half.

    And so on..

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Statement ambiguity for D is discussed in this thread

»
12 days ago, # |
  Vote: I like it -17 Vote: I do not like it
  1. Pretests were not properly framed.
  2. Except A problem, all problems were too hard.
  3. The contest was unfair,**useless**,and should be unrated.
»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Another hack for B

3 100 1

1 2 22

answer=12 there is test 15

»
12 days ago, # |
  Vote: I like it +48 Vote: I do not like it

Pls, someone teach the coordinators to say "No" to such tasks and tests. What were the testers doing during preparing the round? Make this shame unrated, and let no one ever remember about it

»
12 days ago, # |
Rev. 3   Vote: I like it +25 Vote: I do not like it

As system test proceeds, the contest is turning out to be a speed test for problem-A. This is unfair.
Please make it unrated.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    100+ test case in b , thats weired with so weak pt .

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      During system testing, they add all the hacks that other users submitted to the tests.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yeah so basically,
      For a not-pro coder like me:
      1) Solve A.
      2) See B, think too much.
      3) After a while, see number of submissions increasing fast.
      4) Guess a solution and get prestests passed.
      5) See C, think too much...
      6) Unfortunately your B has got hacked :(
      7) Try fixing B. Get it fixed somehow. But couldn't solve C because of time.
      8) Fail main-tests for B.
      9) Rank list = Speed test for A :)

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sometimes 6) is omitted.

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I meant in this contest particularly. Not in general :)

          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I meant that, too. -> (In this contest, somtimes~)

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Its turning out to be efficiency test for B. Obviously the ones who solved B thought better than others. And that's what should affect rating coz rating is all about how well you can solve a problem.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think its easy to talk without participating in the round.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well I participated in contest and solved first 3 successfully. I just didn't want my main ID to have negative contribution coz I knew people don't wanna hear truth.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In D , the lenght of S should be <=10^4 it will be more fair

»
12 days ago, # |
  Vote: I like it +16 Vote: I do not like it

Now I know that in iiit-h, h stands for hacks!

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Anybody has an idea for test 115 in problem B?

»
12 days ago, # |
  Vote: I like it -26 Vote: I do not like it

I propose that anybody who passes the first 100 test cases on problem B is automatically counted as Accepted.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hahhahaha . i got wa at tc 105+

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    But why? Their solution is wrong if it doesn't pass all tests.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      Sure, but if we get rid of all the tests past 100, then the solution will pass all tests and be correct.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +53 Vote: I do not like it

        Yeah, and if we have no tests for any question, then everyone can have AC.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So fair! What if you got the wrong answer on test case 90? :)))

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Ok, let's make it so that anybody who passes the first 89 is accepted then

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        those who passed examples only will get AC

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I like you got wrong on 111. Let's stop thinking about our ratings and getting accepted while our solutions are wrong. The explanations and pretests were really weak, don't kill the facts just for your sake!

»
12 days ago, # |
  Vote: I like it +29 Vote: I do not like it

Authors, stop doing contest please!

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    these are thhe signs of unexperienced setters. i got wa at 108th tc of b . just bcoz pt was soooooo weak , if b would have been c , people would have been more cautious

»
12 days ago, # |
  Vote: I like it +4 Vote: I do not like it

Shit just got real! IIIT-H Thanks for hackforces!

»
12 days ago, # |
  Vote: I like it +3 Vote: I do not like it

The Rating of Problem B will go up...

»
12 days ago, # |
Rev. 2   Vote: I like it +37 Vote: I do not like it
  • IIIT H : we dont have people who can set hard probs for div 1.
  • Also IIITH : * makes DIV 1 D/E instead of DIV2 D/E *
»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Yyyyeeeaahhh boooyyy!!!

4.3k for A -> 550 for B. The biggest jump I remember.)

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for weak pretests!

»
12 days ago, # |
  Vote: I like it +3 Vote: I do not like it

why so many WA on B ?

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    There should be much precision (I don't mean 0.000001 precision) in a solution of this problem, beside that, the weak pretests will result in these many WAs, because one will not pay attention that his solution has weak code when he gets Pretest Passed.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't think that precision had anything to do with it. But most people submitted an incorrect greedy solution.

»
12 days ago, # |
Rev. 5   Vote: I like it +4 Vote: I do not like it

For Problem B, the codes that are treated as Wrong Answer on test cases 109, 110, 111, or 115 appear frequently. Did the Problem Setter intentionally not include these test cases into the Pretest?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Maybe it's just people's hacks being added before system testing?

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Then the authors didn't have tests for those edge cases in system tests themselves? If so, does that mean they also didn't account for these edge cases (and maybe thought the problem was supposed to be easier).

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Seemingly. In fact, the situation where hacks actually filling into the gaps was known before.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Probably. Testcase 115 was my testcase for hacking.

»
12 days ago, # |
  Vote: I like it -17 Vote: I do not like it

This ought to be unrated.

»
12 days ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

its weird that no body is discussing problem E . only with some D . this condition i see in div1 rounds where only legends pass from c to d to e .

what is happening to div2 rounds .\ MikeMirzayanov

»
12 days ago, # |
  Vote: I like it -11 Vote: I do not like it

That round deserves and oughts to be unrated, or semi-rated, cause it's become truly unfair

»
12 days ago, # |
  Vote: I like it -10 Vote: I do not like it

Hello everyone, you know, there is such wisdom that the blue ones do not make up the rounds. Today I made sure that if they make up it is some kind of shit but a round is slop-top (sorry for my English)

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but problem setters were purple too ! what about them

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      The very fact that the blues were involved in it is already shit, although people who are divas 2 in my opinion have no right to compose a round

»
12 days ago, # |
  Vote: I like it +13 Vote: I do not like it

That feeling, when you know your solution will fail main-tests. But still is in system testing queue :)

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Make it unrated

»
12 days ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

The number of Accepted code for Problem B is far less than that of Problem C... And is about 13% of that of Problem A now. Isn't it abnormal?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yes.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    till now only 4 official(div2) submissions accepted for problem 4 and 0 for e . i think problems got swapped with div1d and e /

»
12 days ago, # |
  Vote: I like it +4 Vote: I do not like it

can anyone tell me why this is giving TLE ?? https://codeforces.com/contest/1111/submission/49428534

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Your algorithm complexity is O(N * 2^N)

    In the case : num == 0, you don't need to recurse because the answer will be automatically A This will stop recursion in all segments containing no elements :)

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish this contest would have been swapped with the previous one.
- The previous contest deserved to be on the day before chinese lunar new year and also being a very good round.
- And this contest deserves to have a long queue, leading to an unrated round.

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Was testcase 15(Problem B) intentionally not kept in pretest?

»
12 days ago, # |
  Vote: I like it +3 Vote: I do not like it

people who failed in B and blaming for weak pretests, better next time write proper code and don't complain. LOL

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hmmm people who didn't succeed just need to succeed next time.....

»
12 days ago, # |
  Vote: I like it -11 Vote: I do not like it

UNRATED!

»
12 days ago, # |
  Vote: I like it +9 Vote: I do not like it

System test on B was hell of a massacre.

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

my code of problem c is misjudged and given wrong answer but on different compilers it is giving right answer. My rating has been decreased. Submission link: **https://codeforces.com/contest/1111/submission/49432400** contest link: **https://codeforces.com/contest/1111** @nitesh_gupta

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Bad pretests destroyed good problems ...

»
12 days ago, # |
  Vote: I like it -6 Vote: I do not like it

The problem difficulty and acceptance rate are very similar to the contests that happen on codechef. This has been one of the major issues for codechef and now codeforces too. Hope they get done with it soon.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

why the answer of testcase # 115 is 5.500000 ?