RGAND (Different Method ? )

Hello Codechef Community !

In Yesterday’s Cookoff, I encountered a problem Range AND

And i read the editorial (partially) and i believe it can be solved it in more simpler way. I’ll explain my approach and also how i got the intuition.

First I made a simple brute force method.

Brute Force Code
int BruteForce(int l,int r){
    int res=0;
    for(int i=l;i<=r;i++){
        int cur=l;
        for(int j=l+1;j<=i;j++){
            cur=cur&j;
        }
        res+=cur;
        cout << cur << endl;
    }
    return res;
}

Now for each i=L to R, i printed the value i got against each i.

So lets say i choose L=600 and R=1500

See the output (Large)
i = 600 Value = 600
i = 601 Value = 600
i = 602 Value = 600
i = 603 Value = 600
i = 604 Value = 600
i = 605 Value = 600
i = 606 Value = 600
i = 607 Value = 600
i = 608 Value = 576
i = 609 Value = 576
i = 610 Value = 576
i = 611 Value = 576
i = 612 Value = 576
i = 613 Value = 576
i = 614 Value = 576
i = 615 Value = 576
i = 616 Value = 576
i = 617 Value = 576
i = 618 Value = 576
i = 619 Value = 576
i = 620 Value = 576
i = 621 Value = 576
i = 622 Value = 576
i = 623 Value = 576
i = 624 Value = 576
i = 625 Value = 576
i = 626 Value = 576
i = 627 Value = 576
i = 628 Value = 576
i = 629 Value = 576
i = 630 Value = 576
i = 631 Value = 576
i = 632 Value = 576
i = 633 Value = 576
i = 634 Value = 576
i = 635 Value = 576
i = 636 Value = 576
i = 637 Value = 576
i = 638 Value = 576
i = 639 Value = 576
i = 640 Value = 512
i = 641 Value = 512
i = 642 Value = 512
i = 643 Value = 512
i = 644 Value = 512
i = 645 Value = 512
i = 646 Value = 512
i = 647 Value = 512
i = 648 Value = 512
i = 649 Value = 512
i = 650 Value = 512
i = 651 Value = 512
i = 652 Value = 512
i = 653 Value = 512
i = 654 Value = 512
i = 655 Value = 512
i = 656 Value = 512
i = 657 Value = 512
i = 658 Value = 512
i = 659 Value = 512
i = 660 Value = 512
i = 661 Value = 512
i = 662 Value = 512
i = 663 Value = 512
i = 664 Value = 512
i = 665 Value = 512
i = 666 Value = 512
i = 667 Value = 512
i = 668 Value = 512
i = 669 Value = 512
i = 670 Value = 512
i = 671 Value = 512
i = 672 Value = 512
i = 673 Value = 512
i = 674 Value = 512
i = 675 Value = 512
i = 676 Value = 512
i = 677 Value = 512
i = 678 Value = 512
i = 679 Value = 512
i = 680 Value = 512
i = 681 Value = 512
i = 682 Value = 512
i = 683 Value = 512
i = 684 Value = 512
i = 685 Value = 512
i = 686 Value = 512
i = 687 Value = 512
i = 688 Value = 512
i = 689 Value = 512
i = 690 Value = 512
i = 691 Value = 512
i = 692 Value = 512
i = 693 Value = 512
i = 694 Value = 512
i = 695 Value = 512
i = 696 Value = 512
i = 697 Value = 512
i = 698 Value = 512
i = 699 Value = 512
i = 700 Value = 512
i = 701 Value = 512
i = 702 Value = 512
i = 703 Value = 512
i = 704 Value = 512
i = 705 Value = 512
i = 706 Value = 512
i = 707 Value = 512
i = 708 Value = 512
i = 709 Value = 512
i = 710 Value = 512
i = 711 Value = 512
i = 712 Value = 512
i = 713 Value = 512
i = 714 Value = 512
i = 715 Value = 512
i = 716 Value = 512
i = 717 Value = 512
i = 718 Value = 512
i = 719 Value = 512
i = 720 Value = 512
i = 721 Value = 512
i = 722 Value = 512
i = 723 Value = 512
i = 724 Value = 512
i = 725 Value = 512
i = 726 Value = 512
i = 727 Value = 512
i = 728 Value = 512
i = 729 Value = 512
i = 730 Value = 512
i = 731 Value = 512
i = 732 Value = 512
i = 733 Value = 512
i = 734 Value = 512
i = 735 Value = 512
i = 736 Value = 512
i = 737 Value = 512
i = 738 Value = 512
i = 739 Value = 512
i = 740 Value = 512
i = 741 Value = 512
i = 742 Value = 512
i = 743 Value = 512
i = 744 Value = 512
i = 745 Value = 512
i = 746 Value = 512
i = 747 Value = 512
i = 748 Value = 512
i = 749 Value = 512
i = 750 Value = 512
i = 751 Value = 512
i = 752 Value = 512
i = 753 Value = 512
i = 754 Value = 512
i = 755 Value = 512
i = 756 Value = 512
i = 757 Value = 512
i = 758 Value = 512
i = 759 Value = 512
i = 760 Value = 512
i = 761 Value = 512
i = 762 Value = 512
i = 763 Value = 512
i = 764 Value = 512
i = 765 Value = 512
i = 766 Value = 512
i = 767 Value = 512
i = 768 Value = 512
i = 769 Value = 512
i = 770 Value = 512
i = 771 Value = 512
i = 772 Value = 512
i = 773 Value = 512
i = 774 Value = 512
i = 775 Value = 512
i = 776 Value = 512
i = 777 Value = 512
i = 778 Value = 512
i = 779 Value = 512
i = 780 Value = 512
i = 781 Value = 512
i = 782 Value = 512
i = 783 Value = 512
i = 784 Value = 512
i = 785 Value = 512
i = 786 Value = 512
i = 787 Value = 512
i = 788 Value = 512
i = 789 Value = 512
i = 790 Value = 512
i = 791 Value = 512
i = 792 Value = 512
i = 793 Value = 512
i = 794 Value = 512
i = 795 Value = 512
i = 796 Value = 512
i = 797 Value = 512
i = 798 Value = 512
i = 799 Value = 512
i = 800 Value = 512
i = 801 Value = 512
i = 802 Value = 512
i = 803 Value = 512
i = 804 Value = 512
i = 805 Value = 512
i = 806 Value = 512
i = 807 Value = 512
i = 808 Value = 512
i = 809 Value = 512
i = 810 Value = 512
i = 811 Value = 512
i = 812 Value = 512
i = 813 Value = 512
i = 814 Value = 512
i = 815 Value = 512
i = 816 Value = 512
i = 817 Value = 512
i = 818 Value = 512
i = 819 Value = 512
i = 820 Value = 512
i = 821 Value = 512
i = 822 Value = 512
i = 823 Value = 512
i = 824 Value = 512
i = 825 Value = 512
i = 826 Value = 512
i = 827 Value = 512
i = 828 Value = 512
i = 829 Value = 512
i = 830 Value = 512
i = 831 Value = 512
i = 832 Value = 512
i = 833 Value = 512
i = 834 Value = 512
i = 835 Value = 512
i = 836 Value = 512
i = 837 Value = 512
i = 838 Value = 512
i = 839 Value = 512
i = 840 Value = 512
i = 841 Value = 512
i = 842 Value = 512
i = 843 Value = 512
i = 844 Value = 512
i = 845 Value = 512
i = 846 Value = 512
i = 847 Value = 512
i = 848 Value = 512
i = 849 Value = 512
i = 850 Value = 512
i = 851 Value = 512
i = 852 Value = 512
i = 853 Value = 512
i = 854 Value = 512
i = 855 Value = 512
i = 856 Value = 512
i = 857 Value = 512
i = 858 Value = 512
i = 859 Value = 512
i = 860 Value = 512
i = 861 Value = 512
i = 862 Value = 512
i = 863 Value = 512
i = 864 Value = 512
i = 865 Value = 512
i = 866 Value = 512
i = 867 Value = 512
i = 868 Value = 512
i = 869 Value = 512
i = 870 Value = 512
i = 871 Value = 512
i = 872 Value = 512
i = 873 Value = 512
i = 874 Value = 512
i = 875 Value = 512
i = 876 Value = 512
i = 877 Value = 512
i = 878 Value = 512
i = 879 Value = 512
i = 880 Value = 512
i = 881 Value = 512
i = 882 Value = 512
i = 883 Value = 512
i = 884 Value = 512
i = 885 Value = 512
i = 886 Value = 512
i = 887 Value = 512
i = 888 Value = 512
i = 889 Value = 512
i = 890 Value = 512
i = 891 Value = 512
i = 892 Value = 512
i = 893 Value = 512
i = 894 Value = 512
i = 895 Value = 512
i = 896 Value = 512
i = 897 Value = 512
i = 898 Value = 512
i = 899 Value = 512
i = 900 Value = 512
i = 901 Value = 512
i = 902 Value = 512
i = 903 Value = 512
i = 904 Value = 512
i = 905 Value = 512
i = 906 Value = 512
i = 907 Value = 512
i = 908 Value = 512
i = 909 Value = 512
i = 910 Value = 512
i = 911 Value = 512
i = 912 Value = 512
i = 913 Value = 512
i = 914 Value = 512
i = 915 Value = 512
i = 916 Value = 512
i = 917 Value = 512
i = 918 Value = 512
i = 919 Value = 512
i = 920 Value = 512
i = 921 Value = 512
i = 922 Value = 512
i = 923 Value = 512
i = 924 Value = 512
i = 925 Value = 512
i = 926 Value = 512
i = 927 Value = 512
i = 928 Value = 512
i = 929 Value = 512
i = 930 Value = 512
i = 931 Value = 512
i = 932 Value = 512
i = 933 Value = 512
i = 934 Value = 512
i = 935 Value = 512
i = 936 Value = 512
i = 937 Value = 512
i = 938 Value = 512
i = 939 Value = 512
i = 940 Value = 512
i = 941 Value = 512
i = 942 Value = 512
i = 943 Value = 512
i = 944 Value = 512
i = 945 Value = 512
i = 946 Value = 512
i = 947 Value = 512
i = 948 Value = 512
i = 949 Value = 512
i = 950 Value = 512
i = 951 Value = 512
i = 952 Value = 512
i = 953 Value = 512
i = 954 Value = 512
i = 955 Value = 512
i = 956 Value = 512
i = 957 Value = 512
i = 958 Value = 512
i = 959 Value = 512
i = 960 Value = 512
i = 961 Value = 512
i = 962 Value = 512
i = 963 Value = 512
i = 964 Value = 512
i = 965 Value = 512
i = 966 Value = 512
i = 967 Value = 512
i = 968 Value = 512
i = 969 Value = 512
i = 970 Value = 512
i = 971 Value = 512
i = 972 Value = 512
i = 973 Value = 512
i = 974 Value = 512
i = 975 Value = 512
i = 976 Value = 512
i = 977 Value = 512
i = 978 Value = 512
i = 979 Value = 512
i = 980 Value = 512
i = 981 Value = 512
i = 982 Value = 512
i = 983 Value = 512
i = 984 Value = 512
i = 985 Value = 512
i = 986 Value = 512
i = 987 Value = 512
i = 988 Value = 512
i = 989 Value = 512
i = 990 Value = 512
i = 991 Value = 512
i = 992 Value = 512
i = 993 Value = 512
i = 994 Value = 512
i = 995 Value = 512
i = 996 Value = 512
i = 997 Value = 512
i = 998 Value = 512
i = 999 Value = 512
i = 1000 Value = 512
i = 1001 Value = 512
i = 1002 Value = 512
i = 1003 Value = 512
i = 1004 Value = 512
i = 1005 Value = 512
i = 1006 Value = 512
i = 1007 Value = 512
i = 1008 Value = 512
i = 1009 Value = 512
i = 1010 Value = 512
i = 1011 Value = 512
i = 1012 Value = 512
i = 1013 Value = 512
i = 1014 Value = 512
i = 1015 Value = 512
i = 1016 Value = 512
i = 1017 Value = 512
i = 1018 Value = 512
i = 1019 Value = 512
i = 1020 Value = 512
i = 1021 Value = 512
i = 1022 Value = 512
i = 1023 Value = 512
i = 1024 Value = 0
i = 1025 Value = 0
i = 1026 Value = 0
i = 1027 Value = 0
i = 1028 Value = 0
i = 1029 Value = 0
i = 1030 Value = 0
i = 1031 Value = 0
i = 1032 Value = 0
i = 1033 Value = 0
i = 1034 Value = 0
i = 1035 Value = 0
i = 1036 Value = 0
i = 1037 Value = 0
i = 1038 Value = 0
i = 1039 Value = 0
i = 1040 Value = 0
i = 1041 Value = 0
i = 1042 Value = 0
i = 1043 Value = 0
i = 1044 Value = 0
i = 1045 Value = 0
i = 1046 Value = 0
i = 1047 Value = 0
i = 1048 Value = 0
i = 1049 Value = 0
i = 1050 Value = 0
i = 1051 Value = 0
i = 1052 Value = 0
i = 1053 Value = 0
i = 1054 Value = 0
i = 1055 Value = 0
i = 1056 Value = 0
i = 1057 Value = 0
i = 1058 Value = 0
i = 1059 Value = 0
i = 1060 Value = 0
i = 1061 Value = 0
i = 1062 Value = 0
i = 1063 Value = 0
i = 1064 Value = 0
i = 1065 Value = 0
i = 1066 Value = 0
i = 1067 Value = 0
i = 1068 Value = 0
i = 1069 Value = 0
i = 1070 Value = 0
i = 1071 Value = 0
i = 1072 Value = 0
i = 1073 Value = 0
i = 1074 Value = 0
i = 1075 Value = 0
i = 1076 Value = 0
i = 1077 Value = 0
i = 1078 Value = 0
i = 1079 Value = 0
i = 1080 Value = 0
i = 1081 Value = 0
i = 1082 Value = 0
i = 1083 Value = 0
i = 1084 Value = 0
i = 1085 Value = 0
i = 1086 Value = 0
i = 1087 Value = 0
i = 1088 Value = 0
i = 1089 Value = 0
i = 1090 Value = 0
i = 1091 Value = 0
i = 1092 Value = 0
i = 1093 Value = 0
i = 1094 Value = 0
i = 1095 Value = 0
i = 1096 Value = 0
i = 1097 Value = 0
i = 1098 Value = 0
i = 1099 Value = 0
i = 1100 Value = 0
i = 1101 Value = 0
i = 1102 Value = 0
i = 1103 Value = 0
i = 1104 Value = 0
i = 1105 Value = 0
i = 1106 Value = 0
i = 1107 Value = 0
i = 1108 Value = 0
i = 1109 Value = 0
i = 1110 Value = 0
i = 1111 Value = 0
i = 1112 Value = 0
i = 1113 Value = 0
i = 1114 Value = 0
i = 1115 Value = 0
i = 1116 Value = 0
i = 1117 Value = 0
i = 1118 Value = 0
i = 1119 Value = 0
i = 1120 Value = 0
i = 1121 Value = 0
i = 1122 Value = 0
i = 1123 Value = 0
i = 1124 Value = 0
i = 1125 Value = 0
i = 1126 Value = 0
i = 1127 Value = 0
i = 1128 Value = 0
i = 1129 Value = 0
i = 1130 Value = 0
i = 1131 Value = 0
i = 1132 Value = 0
i = 1133 Value = 0
i = 1134 Value = 0
i = 1135 Value = 0
i = 1136 Value = 0
i = 1137 Value = 0
i = 1138 Value = 0
i = 1139 Value = 0
i = 1140 Value = 0
i = 1141 Value = 0
i = 1142 Value = 0
i = 1143 Value = 0
i = 1144 Value = 0
i = 1145 Value = 0
i = 1146 Value = 0
i = 1147 Value = 0
i = 1148 Value = 0
i = 1149 Value = 0
i = 1150 Value = 0
i = 1151 Value = 0
i = 1152 Value = 0
i = 1153 Value = 0
i = 1154 Value = 0
i = 1155 Value = 0
i = 1156 Value = 0
i = 1157 Value = 0
i = 1158 Value = 0
i = 1159 Value = 0
i = 1160 Value = 0
i = 1161 Value = 0
i = 1162 Value = 0
i = 1163 Value = 0
i = 1164 Value = 0
i = 1165 Value = 0
i = 1166 Value = 0
i = 1167 Value = 0
i = 1168 Value = 0
i = 1169 Value = 0
i = 1170 Value = 0
i = 1171 Value = 0
i = 1172 Value = 0
i = 1173 Value = 0
i = 1174 Value = 0
i = 1175 Value = 0
i = 1176 Value = 0
i = 1177 Value = 0
i = 1178 Value = 0
i = 1179 Value = 0
i = 1180 Value = 0
i = 1181 Value = 0
i = 1182 Value = 0
i = 1183 Value = 0
i = 1184 Value = 0
i = 1185 Value = 0
i = 1186 Value = 0
i = 1187 Value = 0
i = 1188 Value = 0
i = 1189 Value = 0
i = 1190 Value = 0
i = 1191 Value = 0
i = 1192 Value = 0
i = 1193 Value = 0
i = 1194 Value = 0
i = 1195 Value = 0
i = 1196 Value = 0
i = 1197 Value = 0
i = 1198 Value = 0
i = 1199 Value = 0
i = 1200 Value = 0
i = 1201 Value = 0
i = 1202 Value = 0
i = 1203 Value = 0
i = 1204 Value = 0
i = 1205 Value = 0
i = 1206 Value = 0
i = 1207 Value = 0
i = 1208 Value = 0
i = 1209 Value = 0
i = 1210 Value = 0
i = 1211 Value = 0
i = 1212 Value = 0
i = 1213 Value = 0
i = 1214 Value = 0
i = 1215 Value = 0
i = 1216 Value = 0
i = 1217 Value = 0
i = 1218 Value = 0
i = 1219 Value = 0
i = 1220 Value = 0
i = 1221 Value = 0
i = 1222 Value = 0
i = 1223 Value = 0
i = 1224 Value = 0
i = 1225 Value = 0
i = 1226 Value = 0
i = 1227 Value = 0
i = 1228 Value = 0
i = 1229 Value = 0
i = 1230 Value = 0
i = 1231 Value = 0
i = 1232 Value = 0
i = 1233 Value = 0
i = 1234 Value = 0
i = 1235 Value = 0
i = 1236 Value = 0
i = 1237 Value = 0
i = 1238 Value = 0
i = 1239 Value = 0
i = 1240 Value = 0
i = 1241 Value = 0
i = 1242 Value = 0
i = 1243 Value = 0
i = 1244 Value = 0
i = 1245 Value = 0
i = 1246 Value = 0
i = 1247 Value = 0
i = 1248 Value = 0
i = 1249 Value = 0
i = 1250 Value = 0
i = 1251 Value = 0
i = 1252 Value = 0
i = 1253 Value = 0
i = 1254 Value = 0
i = 1255 Value = 0
i = 1256 Value = 0
i = 1257 Value = 0
i = 1258 Value = 0
i = 1259 Value = 0
i = 1260 Value = 0
i = 1261 Value = 0
i = 1262 Value = 0
i = 1263 Value = 0
i = 1264 Value = 0
i = 1265 Value = 0
i = 1266 Value = 0
i = 1267 Value = 0
i = 1268 Value = 0
i = 1269 Value = 0
i = 1270 Value = 0
i = 1271 Value = 0
i = 1272 Value = 0
i = 1273 Value = 0
i = 1274 Value = 0
i = 1275 Value = 0
i = 1276 Value = 0
i = 1277 Value = 0
i = 1278 Value = 0
i = 1279 Value = 0
i = 1280 Value = 0
i = 1281 Value = 0
i = 1282 Value = 0
i = 1283 Value = 0
i = 1284 Value = 0
i = 1285 Value = 0
i = 1286 Value = 0
i = 1287 Value = 0
i = 1288 Value = 0
i = 1289 Value = 0
i = 1290 Value = 0
i = 1291 Value = 0
i = 1292 Value = 0
i = 1293 Value = 0
i = 1294 Value = 0
i = 1295 Value = 0
i = 1296 Value = 0
i = 1297 Value = 0
i = 1298 Value = 0
i = 1299 Value = 0
i = 1300 Value = 0
i = 1301 Value = 0
i = 1302 Value = 0
i = 1303 Value = 0
i = 1304 Value = 0
i = 1305 Value = 0
i = 1306 Value = 0
i = 1307 Value = 0
i = 1308 Value = 0
i = 1309 Value = 0
i = 1310 Value = 0
i = 1311 Value = 0
i = 1312 Value = 0
i = 1313 Value = 0
i = 1314 Value = 0
i = 1315 Value = 0
i = 1316 Value = 0
i = 1317 Value = 0
i = 1318 Value = 0
i = 1319 Value = 0
i = 1320 Value = 0
i = 1321 Value = 0
i = 1322 Value = 0
i = 1323 Value = 0
i = 1324 Value = 0
i = 1325 Value = 0
i = 1326 Value = 0
i = 1327 Value = 0
i = 1328 Value = 0
i = 1329 Value = 0
i = 1330 Value = 0
i = 1331 Value = 0
i = 1332 Value = 0
i = 1333 Value = 0
i = 1334 Value = 0
i = 1335 Value = 0
i = 1336 Value = 0
i = 1337 Value = 0
i = 1338 Value = 0
i = 1339 Value = 0
i = 1340 Value = 0
i = 1341 Value = 0
i = 1342 Value = 0
i = 1343 Value = 0
i = 1344 Value = 0
i = 1345 Value = 0
i = 1346 Value = 0
i = 1347 Value = 0
i = 1348 Value = 0
i = 1349 Value = 0
i = 1350 Value = 0
i = 1351 Value = 0
i = 1352 Value = 0
i = 1353 Value = 0
i = 1354 Value = 0
i = 1355 Value = 0
i = 1356 Value = 0
i = 1357 Value = 0
i = 1358 Value = 0
i = 1359 Value = 0
i = 1360 Value = 0
i = 1361 Value = 0
i = 1362 Value = 0
i = 1363 Value = 0
i = 1364 Value = 0
i = 1365 Value = 0
i = 1366 Value = 0
i = 1367 Value = 0
i = 1368 Value = 0
i = 1369 Value = 0
i = 1370 Value = 0
i = 1371 Value = 0
i = 1372 Value = 0
i = 1373 Value = 0
i = 1374 Value = 0
i = 1375 Value = 0
i = 1376 Value = 0
i = 1377 Value = 0
i = 1378 Value = 0
i = 1379 Value = 0
i = 1380 Value = 0
i = 1381 Value = 0
i = 1382 Value = 0
i = 1383 Value = 0
i = 1384 Value = 0
i = 1385 Value = 0
i = 1386 Value = 0
i = 1387 Value = 0
i = 1388 Value = 0
i = 1389 Value = 0
i = 1390 Value = 0
i = 1391 Value = 0
i = 1392 Value = 0
i = 1393 Value = 0
i = 1394 Value = 0
i = 1395 Value = 0
i = 1396 Value = 0
i = 1397 Value = 0
i = 1398 Value = 0
i = 1399 Value = 0
i = 1400 Value = 0
i = 1401 Value = 0
i = 1402 Value = 0
i = 1403 Value = 0
i = 1404 Value = 0
i = 1405 Value = 0
i = 1406 Value = 0
i = 1407 Value = 0
i = 1408 Value = 0
i = 1409 Value = 0
i = 1410 Value = 0
i = 1411 Value = 0
i = 1412 Value = 0
i = 1413 Value = 0
i = 1414 Value = 0
i = 1415 Value = 0
i = 1416 Value = 0
i = 1417 Value = 0
i = 1418 Value = 0
i = 1419 Value = 0
i = 1420 Value = 0
i = 1421 Value = 0
i = 1422 Value = 0
i = 1423 Value = 0
i = 1424 Value = 0
i = 1425 Value = 0
i = 1426 Value = 0
i = 1427 Value = 0
i = 1428 Value = 0
i = 1429 Value = 0
i = 1430 Value = 0
i = 1431 Value = 0
i = 1432 Value = 0
i = 1433 Value = 0
i = 1434 Value = 0
i = 1435 Value = 0
i = 1436 Value = 0
i = 1437 Value = 0
i = 1438 Value = 0
i = 1439 Value = 0
i = 1440 Value = 0
i = 1441 Value = 0
i = 1442 Value = 0
i = 1443 Value = 0
i = 1444 Value = 0
i = 1445 Value = 0
i = 1446 Value = 0
i = 1447 Value = 0
i = 1448 Value = 0
i = 1449 Value = 0
i = 1450 Value = 0
i = 1451 Value = 0
i = 1452 Value = 0
i = 1453 Value = 0
i = 1454 Value = 0
i = 1455 Value = 0
i = 1456 Value = 0
i = 1457 Value = 0
i = 1458 Value = 0
i = 1459 Value = 0
i = 1460 Value = 0
i = 1461 Value = 0
i = 1462 Value = 0
i = 1463 Value = 0
i = 1464 Value = 0
i = 1465 Value = 0
i = 1466 Value = 0
i = 1467 Value = 0
i = 1468 Value = 0
i = 1469 Value = 0
i = 1470 Value = 0
i = 1471 Value = 0
i = 1472 Value = 0
i = 1473 Value = 0
i = 1474 Value = 0
i = 1475 Value = 0
i = 1476 Value = 0
i = 1477 Value = 0
i = 1478 Value = 0
i = 1479 Value = 0
i = 1480 Value = 0
i = 1481 Value = 0
i = 1482 Value = 0
i = 1483 Value = 0
i = 1484 Value = 0
i = 1485 Value = 0
i = 1486 Value = 0
i = 1487 Value = 0
i = 1488 Value = 0
i = 1489 Value = 0
i = 1490 Value = 0
i = 1491 Value = 0
i = 1492 Value = 0
i = 1493 Value = 0
i = 1494 Value = 0
i = 1495 Value = 0
i = 1496 Value = 0
i = 1497 Value = 0
i = 1498 Value = 0
i = 1499 Value = 0
i = 1500 Value = 0

Now It’s easy to see that the from L to R the value decreases for every increasing i and also repeats a certain amount of time

It started from 600 at i=600 then became 576 at i= 608 then became 512 at i=640 and finally 0.

So value of L where change occurs is like, 600 -> 608 -> 640 --> 1023 -> 1500

Also you can try many values it’ll always become a perfect power of 2 before becoming 0 for all other i.

Now the next step, consider the series 600 -> 608 -> 640 --> 1023 -> 1500

Let’s write the numbers in their Binary Form.

600  -> 01001011000 
608  -> 01001100000
640  -> 01010000000
1024 -> 10000000000

Observe something ?

The set consecutive set bits are disappearing and add 1 set bit to their left !

So i can say there will be some answer

ans_1 for i=600 to i=607
ans_2 for i=608 to i=639
ans_3 for i=640 to i=1023
ans_4 for i=1024 to i=1500

If you observer the number of time the ans wil contribute can be easily obtained by taking the difference of (608-600) and (640-608) and (1024-640) and etc

and we can calculate values for each of the ans_i seperately and multiply with the count to get the answer !

Here is my solution

C++ Code

Solution

Python Code

Will Upload Soon…

6 Likes

hi… I used same the approch as you but got wrong answer please help me. whats wrong with my code
https://www.codechef.com/viewsolution/29092520

What should be the output of

1
15 16

Shouldn’t it be 15? (15+ 15^16) =15+0=15

Yup

but your code is giving ans as 30

Lol seriously ? ! I’ll have to check… If that’s true then maybe test cases need to be improved… My (probably) bugged solution got accepted

Actually i tested your code for some test cases since your solution was accepted one and i am getting WA. I think i am close to correct logic but i am not able to figure out what is going wrong.

Here is my code.

Input
8
28 35
24 56
21 76
16 17
30 32
15 15
15 16
29 31

My output
112
192
191
32
60
15
15
87

Your output
112
192
189
32
90
15
30
85

Maybe you are not considering leading 0 that should be prefixed with 2^n -1 while doing and operation with 2^n.

I think…buggy part is adding r+1 to values, cause it is increasing value of range by 1 (which cause 17-15=2, so this part is making ans = 15*2 = 30), instead remain it r and handle l==r case by using an if statement.

@balrams @humblejumbo

The incorrect answer was coming due to line 92

            if(cur<r)
                values.push_back(binToDec(res));

It should be

            if(cur<=r)
                values.push_back(binToDec(res));

Now it gives correct output 15

for

1
15 16

But this was close, had this been a CF Round, my solution would have got hacked lol

also this proves that Test Cases were weak

1 Like